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

[Robert Eachus <rieachus@comcast.net>]

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.