How best to Implement naked single and hidden single in scheme

Question

I am writing a sudoku solver in scheme. I represent the board cells as a 3x3 vector of 3x3 vectors with a list of the candidates numbers in each cell. So for example a blank board and updating one of its cells is

    (define blank-board-cell (for/list ([x 9]) (add1 x)))
    (define blank-row (make-vector 9 blank-board-cell))
    (define blank-board (make-vector 9 blank-row))

     (define (board-ref b row col)
           (vector-ref (vector-ref b row) col))

     (define (board-update b target-row target-col new-cell)
           (for/vector ([row (vector-length b)])
               (for/vector ([col (vector-length b)])
                  (cond [(and (= row target-row)
                       (= col target-col))
                       new-cell]
                        [else (board-ref b row col)]))))

I would like to implement the naked single and hidden single strategies for solving the board. Naked single: find empty cells whose value can be deduced from looking at the contents of its row, column and 3x3 block. If 8 numbers have already been assigned to these neighboring cells then the empty cell must house the last remaining number and that number must be removed from the cells in the same row, column and 3x3 block.

In Java/imperative style for example this would look like

boolean nakedSingles()  
{
   for (int row = 0; row < 9;  row++)   
   {
      for (int col = 0; col < 9; col++) 
      {
          HashSet<Integer>  cellCandidates = board[row][col].candidates;
          if  (cellCandidates.size()==1)    
          {
              board[row][col].setValue(cellCandidates.iterator().next());
              //remove candidate from neighboring cells
              return true;
           }
       }
     }
     return false;
 } 

The "translation" to scheme "pseudocode" I am heading to

(define (naked-single b)
    (for*/vector ([row (in-range (vector-length b))] 
              [col (in-range (vector-length b))])
           (if (= 1 (length (board-ref b row col)))
               ; set candidate and remove it from cells in row/col
               ; and return #t
               #f)))

Does this look sensible/correct?

Hidden Single: By looking at the row, column and 3x3 block it is clear that there is only one candidate possible although the cell itself might have several candidates. We assign that candidate to the cell and remove it from the cells in the same row, column and 3x3 block.

In Java/imperative style for example this would look like

boolean hiddenSingles() 
{
    int []  unitCandidates = new int[10];
    // For each row, column or boxID
    for  (int  unitSelect = 0;  unitSelect  < 3;  unitSelect++) 
    {
       for (int i = 0; i < 9; i++)  
       {
            if  (unitSelect == 0)   
            {
               unit  =  getRow(i);
             }
             else if (unitSelect  == 1) 
             {
               unit =  getCol(i);
             }
             else if (unitSelect ==  2) 
             {
                unit = getBox(i + 1);
              }
             for (int n = 1; n <=  9;  n++) 
             {
                 unitCandidates[n] = 0;
             }
             for (Integer[] elem:unit)  
             {
                int row = elem[0];
                int col  = elem[1];
                if (board[row][col].getValue() == 0)    
                {
                   for (int cand:board[row][col].candidates)    
                   {
                       unitCandidates[cand] +=  1;
                    }
                 }
             }
             int foundDigit = 0;
             for (int n  = 1; n <= 9; n++)  
             {
                 // Check for hidden single
                 if (unitCandidates[n] == 1)    
                 {
                     // Found  hidden single
                     foundDigit = n;
                     break;
                  }
              }
              // If a hidden single was found, check what cell
              // contained that hidden single and set cellvalue
              if (foundDigit != 0)  
              {
                 for (Integer[] elem:unit)  
                 {
                    int row = elem[0];
                    int col = elem[1];
                    if (board[row][col].getValue() == 0)    
                    {
                        if  (board[row]col].candidates.contains((Object)
                                              foundDigit))  
                        {
                             board[row][col].setValue(foundDigit);
                             removeDigitfrom(row,col);
                             return true;
                         }
                     }
                }
             }
         }
     }
     return false;
}

This one is slightly more complicated to translate into scheme not sure what the more elegant way is? (I can brute force it with nested for loops).

Answer 1

You can simplify and speed up your approach with a little bit of redundancy.

---

The board cells should only contain 2 types of values - a number or a special value indicating that the value still needs to be determined. This way you can quickly find all cells that haven't been determined yet.

At the same time, keep a set of possible values

• per row
• per column
• per cell

all initialised with all possible values (1 to 9) when creating a blank board.

---

Create a procedure that sets a cell's value (used either when initially reading a board from an external format, or when you found a value to set, and make sure that

• you set the cell's value on the board
• remove that value from the row's set of values
• remove that value from the column's set of values
• clear the cells set of possible value (optional)

---

Iterate over the board (I call this "pass 1"), and for each cell that hasn't been determined yet, compute the set intersection of row, column and cell. If there's only one value left you're good, use the previously described procedure. If no value is left the board is unsolvable. There's no difference between "naked single" and "hidden single".

Iterate until you made on pass and didn't find anything.

Keep the number of cells to be determined, and decrement whenever you set a cell to a certain value. This way you will know when the board has been solved.

---

Many Sudoku puzzles can be solved this way, but for some you need a "pass 2" where you recursively try all values for one cell and see if that helps you find the other ones. Whenever you "try" one value, fall back to pass 1, that will be quicker. Be aware that you need to make copies of your board in pass 2 where the copy shares no structure with the original.