Arrays, slices, case, and ‘in’ strategies

Arrays, slices, case, and ‘in’ strategies

[Mace Ayres]

I have a two dimensional array, gird, 1..9, 1..9 index of integer and array of a record type named cell and array is named grid.  So, a grid is a 9x9 array of record type ‘cell, Cell has some properties, and functions in the containing package to enter, change, values in a field called ‘value. So I can traverse the array named grid with
for row in 1..9 loop
   for column 1..9 loop
     grid(row,column).x := y;      — x is some attribute of the cell/record/object that the array is type of
   end loop; — column loop.     — and y is some value I assign to the x field, of the object cell in the array location (row, column)
 end loop;   — row loop

When attempting to assign a y value to the cell’s x field, I want to to check that the y that is to be assigned to the cell’s x field does not adready exist anywhere adready in all the columns of the row, or all the rows of the target column. Easy enough with function: 

Check_row.(r,c, numb: Integer  ... boolean ..
  begin
   for c in 1..9  loop.              — traverse the row in grid that is passed in with parm r
        if grid(r).value = numb — if if grid(r,c).value = numb.     — numb is passed in also a parm
           then bad.                  — proposed value numb already exists in proposed row to put it in
           return false — not ok
.....
function check_column uses some logic. Both work and are fast enough on my 64bit Mac OS x.

Now, challenge is: besides checking to see if a proposed value (integer 1..0) already exists in the proposed row and column to put it in,
I also have an abstraction of triads superimposed (mentally) on the grid, giving 9 triads layer on top of the 9x9 array called ‘grid.’ The 9x9 grid nicely
holds 9 of these imaginary triads,, ie, first 3 rows and first 3 columns are in triad 1 and first 3 rows and columns 4 to 6 are conceived as triad 2,

I need to check, in addition to whether the proposed ingteger value is already in any cells in that row, or column,  whether the proposed value already
exists in any cell.value field for any cell in triad. The in parameters of r,c can reveal what triad is in question, but it looks like some fat code to to
traverse the abstract 3x3 triads.

I know I could create some triad types of arrays, but I am wondering if I can slice the array grid into 9 collections and then check
loop.. if numb (proposed number) already exists in the triad [this would be determined by row, column in parameters) OR also, the cell/record has a field with its triad,
a constant property.

If this is too convoluted and or not clear, I can just delete the question, but if it’s understandable, best approach recommended appreciated.

           

Re: Arrays, slices, case, and ‘in’ strategies

[Jacob Sparre Andersen]

Mace Ayres wrote:

[ A problem description which sound very much like a part of a Sudoku
  solver. :-) ]

You could make the two dimensional array a container with three
different iterators, one for iterating over a selected column, one for
iterating over a selected row, and one for iterating over a block.

Greetings,

Jacob
-- 
»Saving keystrokes is the job of the text editor, not the
 programming language.«                    -- Preben Randhol

Re: Arrays, slices, case, and ‘in’ strategies

[Jeffrey R. Carter]

On 12/30/2017 01:51 AM, Mace Ayres wrote:
> 
> I know I could create some triad types of arrays, but I am wondering if I can slice the array grid into 9 collections and then check
> loop.. if numb (proposed number) already exists in the triad [this would be determined by row, column in parameters) OR also, the cell/record has a field with its triad,
> a constant property.

You could create a function:

function Block (Row : Row_Number; Column : Column_Number)
return Block_Number;

or a map:

type Block_Map is array (Row_Number, Column_Number)
of Block_Number;

Block : constant Block_Map := ...;

both of which would be used as

Block (Row, Column)

-- 
Jeff Carter
"C's solution to this [variable-sized array parameters] has real
problems, and people who are complaining about safety definitely
have a point."
Dennis Ritchie
25

Re: Arrays, slices, case, and ‘in’ strategies

[Simon Wright]

Mace Ayres <mace.ayres@gmail.com> writes:

> if ... OR also, the cell/record has a field with its triad, a constant
> property.

Don't understand this.

Re: Arrays, slices, case, and ‘in’ strategies

[Mace Ayres]

Thanks Simon:  I meant to say that in addition to using the array indices to determine the cell location, the array types, (cell) have a triad property too. It is a fixed constant of course. 
Maybe I could use that some how:  - if gird(3,3).triad = 3 then I am in grid 3 - but I still have to search each of the 9 locations in any triad to see it already has 
an instance of the proposed number to enter.

Better yet, can I somehow select just the cells with .triad = N ( not using the grid indices) and check if any cell with triad = N already have the numb value proposed for entry.
But, at first blush that means searching all 81 locations, cells, if I have not already reduced the search space.

In SQL it might look like .. Select cell.triad as evall from grid
                                                     where eval = N ...
returning a subset (slice) of cells with indices r=1..3 and c=1..3

Re: Arrays, slices, case, and ‘in’ strategies

[Mace Ayres]

Jacob, yes it’s a Sudokus problem I call Sukodus. Already solved many times over, I am doing it as a personal assignment I gave myself to learn Ada better. Also,
I am curious to see if after developing clean and direct algorithmic mechanical solution, if any AI or machine learning could be applied. There are lots of patterns involved I think. 
Also, I want to gather statistics, as game is played, on remaining possible solutions, amount of each of the 9 digits are used and remaining, etc.

Though, it still boils down to a algorithmic, more or less mechanical problem, like checkers or tic-tac-toe.

Thanks for your suggestions

Re: Arrays, slices, case, and ‘in’ strategies

[Mace Ayres]

Jacob, 3 iterations may be answer. My Ada mind is limited to Array indices being limited to the dimensionality of the array. 1 D array has 1 index. 2 D array has 2 indices.

Forgot to mention that I have a 1 D array of the 2 D grid array, netting a 3 D array effect, but as an array of arrays, rather than a single 3 D array. My 1 D array of the 2 D grid
array is called layer. So I have 10 layers (1 each for each of the 9 digits, that will show only 1 of the digits) and then 1 10th layer to show all entries.

This array of array rather than a single 3 D array, an early disign decision. I also thought of just a linked list with access types, but choose this array approach for initial attempt.

Re: Arrays, slices, case, and ‘in’ strategies

[Mace Ayres]

Thanks Jeffrey.

Re: Arrays, slices, case, and ‘in’ strategies

[Simon Wright]

Simon Wright <simon@pushface.org> writes:

> Mace Ayres <mace.ayres@gmail.com> writes:
>
>> if ... OR also, the cell/record has a field with its triad, a constant
>> property.
>
> Don't understand this.

Oh, I see, it's Sudoku, and those are the given cells.

Anyway, this looks simple enough for checking whether the value is
already in the block:

   function Check_Block (For_Value : Integer;
                         At_Row : Grid_Coordinate;
                         At_Column : Grid_Coordinate;
                         In_Grid : Grid) return Boolean
   is
      Row_First : constant Grid_Coordinate := ((At_Row    - 1) / 3) * 3 + 1;
      Col_First : constant Grid_Coordinate := ((At_Column - 1) / 3) * 3 + 1;
   begin
      for Row in Row_First .. Row_First + 2 loop
         for Col in Col_First .. Col_First + 2 loop
            if In_Grid (Row, Col).X = For_Value then
               return False;
            end if;
         end loop;
      end loop;
      return True;
   end Check_Block;

Re: Arrays, slices, case, and ‘in’ strategies

[Mace Ayres]

On Saturday, December 30, 2017 at 9:41:56 AM UTC-8, Simon Wright wrote:
> Simon Wright <simon@pushface.org> writes:
> 
> > Mace Ayres <mace.ayres@gmail.com> writes:
> >
> >> if ... OR also, the cell/record has a field with its triad, a constant
> >> property.
> >
> > Don't understand this.
> 
> Oh, I see, it's Sudoku, and those are the given cells.
> 
> Anyway, this looks simple enough for checking whether the value is
> already in the block:
=============

Thanks Simon. This is exactly what I needed. My thoughts were moving toward the rythm of threes and increments  in start and length of each block, but it would have taken me a while toga to the parenthesized leitmotif you capture.
Excellent!

Are you a professional Ada programmer?

=====================
> 
>    function Check_Block (For_Value : Integer;
>                          At_Row : Grid_Coordinate;
>                          At_Column : Grid_Coordinate;
>                          In_Grid : Grid) return Boolean
>    is
>       Row_First : constant Grid_Coordinate := ((At_Row    - 1) / 3) * 3 + 1;
>       Col_First : constant Grid_Coordinate := ((At_Column - 1) / 3) * 3 + 1;
>    begin
>       for Row in Row_First .. Row_First + 2 loop
>          for Col in Col_First .. Col_First + 2 loop
>             if In_Grid (Row, Col).X = For_Value then
>                return False;
>             end if;
>          end loop;
>       end loop;
>       return True;
>    end Check_Block;

Re: Arrays, slices, case, and ‘in’ strategies

[Simon Wright]

Mace Ayres <mace.ayres@gmail.com> writes:

> Are you a professional Ada programmer?

Was, now retired

Re: Arrays, slices, case, and ‘in’ strategies

[Robert Eachus]

On Friday, December 29, 2017 at 7:51:49 PM UTC-5, Mace Ayres wrote:
> I have a two dimensional array, gird, 1..9, 1..9 index of integer and array of a record type named cell and array is named grid... 
> I need to check, in addition to whether the proposed ingteger value is already in any cells in that row, or column,  whether the proposed value already
> exists in any cell.value field for any cell in triad. The in parameters of r,c can reveal what triad is in question, but it looks like some fat code to to
> traverse the abstract 3x3 triads.
> 
> I know I could create some triad types of arrays, but I am wondering if I can slice the array grid into 9 collections and then check
> loop.. if numb (proposed number) already exists in the triad [this would be determined by row, column in parameters) OR also, the cell/record has a field with its triad,
> a constant property.

I would do this by putting the Triad number in each cell, and having a set type:

   type Sudoku_Set is array(Integer 1..9) of Boolean;
   Reset: constant Sudoku_Set := (others => False);
   Set_Array: array(Integer 1..9) of Sudoku_Set;
   Row_Array, Col_Array, Triad_Array: Set_Array := (others => Reset);

Now your tests for whether a number is already used is some ors:

   if not (Row_Array(Row) or Col_Array(Column) or
      Triad_Array(Cell(Row, Column).Triad)(Candidate) then...

Oring the three arrays together then chosing a candidate should be faster than indexing them separately.  I didn't attempt to compile the above so it probably includes a syntax error or two.  The reason I didn't is that once you have the Ah Ha! moment of oring the sets together, you are likely to change your tree search to do the oring into a local variable, then do something like:

    function Recur(Row, Column: in Integer) is
      Local_Set: Sudoku_Set := Row_Array(Row) or Col_Array(Column) or
      Triad_Array(Cell(Row, Column).Triad;
    begin
      if Cell(Row, Column) = 0
      then -- set as part of conditions.
        if Row < 9
        then return Recur(Row+1, Column);
        elsif Column < 9
        then return Recur(1, Column+1);
        else return True;
      end if;

      for I in Integer range 1..9 loop
        if not Local_Set(I)
        then
          Grid(Row_Column).Value := I;
          Row_Array(Row)(I) := True;
          Col_Array(Column)(I) := True;
        end if;     
        if Row < 9
        then return Recur(Row+1, Column);
        elsif Column < 9
        then return Recur(1, Column+1);
        else return True;
        end if; 
      end loop;
    end Recur;

This does a brute force search, but it should be fast enough.  You can add bells and whistles like filling in a row column or triad cell when eight numbers have been used.  I don't think that would make things any faster.  Using an access value instead of an index for triads might make it faster, but that's the type of optimization best left until last.