创建数独谜题时出现重复问题

Question

我正在尝试创建自己的普通 9x9 数独谜题。

我将问题分为两部分 -

1. 创建一个完全填充的数独，并
2. 从中删除不必要的数字 网格

现在，我被第一部分困住了。

---

这是我简要使用的算法：

a）首先，我选择一个数字（例如 1），生成一个随机单元格位置，如果

• 该单元格尚未被占用，并且
• 该行还没有 现在我检查在一行、
• b )
• 一列或一个框中只有一个地方是空的

情况我填写

c) 我检查是否有一个数字不存在于某个框中，但存在于同一行和同一列的框中（我在这里谈论的是 3x3 框），则该数字的位置是固定的我填满它。

d) 重复上述步骤，直到每个数字在网格上出现九次。

---

我面临的问题是，我经常遇到这样的中间情况：

 0  1  0 | 0  0  3 | 0[4/2]0 
 0 [2] 0 | 0 [4] 1 | 3  0  0 
 3  0 [4]|[2] 0  0 | 0  0  1 
---------+---------+---------
 2  0  3 | 0  5  4 | 0  1  0 
 0  0  1 | 3  0  2 |[4] 0  0 
 0  4  0 | 0  1  0 |[2] 3  0 
---------+---------+---------
 1  0  2 | 0  3  0 | 0  0 [4] 
 4  3  0 | 1  0  0 | 0  0 [2] 
 5  0  0 | 4  2  0 | 1  0  3

看到写有[4/2]的地方吗？这是 2 和 4 的位置，因为框标记为 []。

我该怎么做才能避免陷入这种情况（因为这种情况是僵局 - 我无法进一步前进）

Answer 1

还有另一种生成数独谜题的方法：从一个已知的良好网格开始 - 任何一个都可以 - 然后通过应用不破坏不变量的操作来随机“洗牌”它。有效操作包括：

• 交换块内的行
• 交换块内的列
• 交换块的整行（例如，前 3 行、中间 3 行、最后 3 行）
• 交换块的整列 将
• 一个数字的所有实例与另一个数字交换
• 反映棋盘
• 旋转棋盘board

通过这些操作，您可以生成非常大范围的可能的板。然而，您需要小心如何应用操作 - 就像简单的洗牌一样，很容易编写一种算法来使某些棋盘比其他棋盘更有可能出现。类似于 Knuth shuffle 的技术可能会有所帮助。

编辑：评论中指出，仅这些操作不足以创建每个可能的网格。

Answer 2

你总会遇到这种情况。您需要递归回溯搜索来解决它。

基本上，确定特定数字对于单元格是否确实有效的唯一方法是继续搜索并查看会发生什么。

回溯搜索通常使用递归调用来完成。每次调用都将迭代一个单元格的（可能）仍然有效的选项，递归地评估下一个单元格的所有选项。当您无法继续时，回溯意味着从当前呼叫返回 - 当然，首先删除您为该单元格测试的任何数字。

当您找到有效的解决方案时，要么保存它并回溯以继续（即找到替代方案），要么中断所有递归调用以完成。递归回溯搜索的成功是一种特殊情况，在我看来，成功抛出异常是一个好主意 - 对于特定的调用成功来说是例外，并且代码会更清晰。

如果生成随机板，请按随机顺序迭代特定递归调用（对于特定单元格）中的选项。

相同的基本算法也适用于部分完成的棋盘（即解决现有数独） - 当评估已经有数字的单元格时，这是该单元格的唯一选择，因此递归到下一个单元格。

这是我曾经编写过的求解器的回溯搜索 - 很多内容都被抽象出来，但希望这能让原理更清晰......

size_t Board::Rec_Search (size_t p_Pos)
{
  size_t l_Count = 0;

  if (p_Pos == 81)  //  Found a solution
  {
    l_Count++;

    std::cout << "------------------------" << std::endl;
    Draw ();
    std::cout << "------------------------" << std::endl;
  }
  else
  {
    if (m_Board [p_Pos] == 0)  //  Need to search here
    {
      size_t l_Valid_Set = Valid_Set (p_Pos);

      if (l_Valid_Set != 0)  //  Can only continue if there are possible digits
      {
        size_t  l_Bit = 1;  //  Scan position for valid set

        for (size_t i = 1; i <= 9; i++)
        {
          if (l_Valid_Set & l_Bit)
          {
            Set_Digit  (p_Pos, i);
            l_Count += Rec_Search (p_Pos + 1);
          }

          l_Bit <<= 1;
        }

        Clr_Digit (p_Pos);  //  Ensure cleared properly for backtracking
      }
    }
    else  //  Already filled in - skip
    {
      l_Count += Rec_Search (p_Pos + 1);
    }
  }

  return l_Count;
}

Answer 3

如果你已经达到了一个矛盾的状态，其中一个单元格同时是 2 和 4，那么你的其他一些 2 和 4 一定放置错误。您需要回滚并尝试一些不同的解决方案。

听起来您可能遇到算法问题？ 这里有一些好东西。