0

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

我将问题分为两部分-

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

现在，我坚持第一部分。

这是我简要使用的算法：

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

  • 该单元尚未被占用，并且
  • 如果该行还没有编号，并且
  • 如果该列还没有编号，并且
  • 如果 3x3 框还没有编号

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 的位置。

我能做些什么来避免陷入这种情况（因为这种情况是一个僵局 - 我无法继续前进）

4

3 回答 3

4

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

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

通过这些操作，您可以生成非常大范围的可能板。但是，您需要注意如何应用这些操作 - 就像天真的 shuffle 一样，很容易编写一种算法，使某些板比其他板更有可能。类似于 Knuth shuffle 的技术在这里可能会有所帮助。

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

于 2009-10-15T09:13:01.737 回答
1

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

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

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

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

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

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

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

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;
}
于 2009-10-15T09:49:40.437 回答
0

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

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

于 2009-10-15T08:29:31.920 回答