scheme - 方案中如何最好的实现裸单和隐单

Question

我正在方案中编写一个数独求解器。我将棋盘单元表示为 3x3 向量的 3x3 向量，并在每个单元中列出候选数字。例如，一 block 空白板并更新其一个单元格是

    (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)]))))

我想实现裸单和隐藏单策略来解决棋盘问题。 裸单:找到空单元格，其值可以通过查看其行、列和 3x3 block 的内容来推断。如果已将 8 个数字分配给这些相邻单元格，则空单元格必须容纳最后剩余的数字，并且必须从同一行、列和 3x3 block 中的单元格中删除该数字。

例如，在 Java/命令式风格中，这看起来像

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;
 } 

我要去的方案“伪代码”的“翻译”

(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)))

这看起来合理/正确吗？

隐藏单个:通过查看行、列和 3x3 block ，可以清楚地看出，尽管单元格本身可能有多个候选，但只有一个可能的候选。我们将该候选分配给单元格，并将其从同一行、列和 3x3 block 中的单元格中删除。

例如，在 Java/命令式风格中，这看起来像

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;
}

这个转换成方案稍微复杂一些，不知道更优雅的方法是什么？ (我可以使用嵌套 for 循环来暴力破解它)。

Answer 1

您可以通过一点冗余来简化和加速您的方法。

---

棋盘单元格应仅包含 2 种类型的值 - 数字或表示该值仍需要确定的特殊值。这样您就可以快速找到所有尚未确定的单元格。

同时，保留一组可能的值

• 每行
• 每列
• 每个单元格

在创建空白板时使用所有可能的值(1 到 9)初始化所有内容。

---

创建一个设置单元格值的过程(在最初从外部格式读取板时或在找到要设置的值时使用，并确保

• 您在板上设置单元格的值
• 从该行的值集中删除该值
• 从列的值集中删除该值
• 清除可能值的单元格集(可选)

---

迭代整个棋盘(我称之为“pass 1”)，对于每个尚未确定的单元格，计算行、列和单元格的集合交集。如果只剩下一个值就可以了，请使用前面描述的过程。如果没有留下任何值(value)，那么棋盘就无法解决。 “裸单”和“隐单”没有区别。

迭代，直到成功并且没有发现任何东西。

保留要确定的单元格数量，并在将单元格设置为特定值时递减。这样你就会知道棋盘何时被解决。

---

许多数独谜题都可以通过这种方式解决，但对于某些谜题，您需要“第 2 遍”，在其中递归地尝试一个单元格的所有值，看看这是否可以帮助您找到其他值。每当你“尝试”一个值时，就回退到传递 1，这样会更快。请注意，您需要在第 2 步中复制电路板，其中副本与原始版本不共享结构。