Sudoku求解算法 C++

Question

我几天前开始尝试编写数独求解程序，但是我卡在了算法上。我在这里找到了一个算法，但我并不真正理解它：

1. 从第一个空格开始，将数字1放入其中。
2. 检查整个数独面板，看是否存在任何冲突。
3. 如果数独面板存在冲突，则将当前单元格中的数字增加1（即将1改为2、2改为3等）。
4. 如果数独面板干净，重新开始第一步。
5. 如果给定单元格的所有九个可能数字都导致数独面板冲突，则将此单元格设置为空，并返回到上一个单元格，从第3步重新开始（这就是“回溯”的过程）。

以下是我的代码。我认为我的Help_Solve(...)函数有问题。你能帮我找出问题吗？

    #include <iostream>
#include <iomanip>
#include <time.h>
#include <cstdlib>
#include <windows.h>
using namespace std;

class Sudoku
  {
    private:
    int board[9][9];
    int change[9][9];
    public:
    Sudoku();
    void Print_Board();  
    void Add_First_Cord();  
    void Solve();
    void Help_Solve(int i, int j);
    bool Check_Conflicts(int p, int i, int j);
  };

Sudoku Game;  

void setcolor(unsigned short color)                 //The function that you'll use to
{                                                   //set the colour
    HANDLE hcon = GetStdHandle(STD_OUTPUT_HANDLE);
    SetConsoleTextAttribute(hcon,color);
}

Sudoku::Sudoku()
  {
    for(int i = 1; i <= 9; i++)
      for(int j = 1; j <= 9; j++)
        board[i][j] = 0;            
  }

void Sudoku::Print_Board()
  {
    for(int i = 1; i <= 9; i++)
      {
        for(int j = 1; j <= 9; j++)
          {
            if(change[i][j] == 1) 
              {
                setcolor(12);
                cout << board[i][j] << " ";
                setcolor(7);           
              }
              else cout << board[i][j] << " ";  
              if(j%3 == 0) cout << "| ";
          }
        cout << endl;
        if(i%3 == 0) cout << "------+-------+---------" << endl;

      }                    
  }

void Sudoku::Add_First_Cord()
  {
    board[1][1] = 5; change[1][1] = 1;
    board[1][2] = 3; change[1][2] = 1;     
    board[1][5] = 7; change[1][5] = 1;      
    board[2][1] = 6; change[2][1] = 1;  
    board[2][4] = 1; change[2][4] = 1;       
    board[2][5] = 9; change[2][5] = 1;  
    board[2][6] = 5; change[2][6] = 1; 
    board[3][2] = 9; change[3][2] = 1;      
    board[3][3] = 8; change[3][3] = 1;   
    board[3][8] = 6; change[3][8] = 1;     
    board[4][1] = 8; change[4][1] = 1;    
    board[4][5] = 6; change[4][5] = 1;    
    board[4][9] = 3; change[4][9] = 1;    
    board[5][1] = 4; change[5][1] = 1; 
    board[5][4] = 8; change[5][4] = 1;  
    board[5][6] = 3; change[5][6] = 1;  
    board[5][9] = 1; change[5][9] = 1;   
    board[6][1] = 7; change[6][1] = 1; 
    board[6][5] = 2; change[6][5] = 1;   
    board[6][9] = 6; change[6][9] = 1;  
    board[7][2] = 6; change[7][2] = 1;  
    board[7][7] = 2; change[7][7] = 1;  
    board[7][8] = 8; change[7][8] = 1;  
    board[8][4] = 4; change[8][4] = 1; 
    board[8][5] = 1; change[8][5] = 1;   
    board[8][6] = 9; change[8][6] = 1; 
    board[8][9] = 5; change[8][9] = 1;   
    board[9][5] = 8; change[9][5] = 1;  
    board[9][8] = 7; change[9][8] = 1;  
    board[9][9] = 9; change[9][9] = 1;  
  }

bool Sudoku::Check_Conflicts(int p, int i, int j)
  {
    for(int k = 1; k <= 9; k++)
      if(board[i][k] == p) return false;

    for(int q = 1; q <= 9; q++)
      if(board[q][j] == p) return false;

    /*
      *00
      000
      000
    */
    if((j == 1 || j == 4 || j == 7) && (i == 1 || i == 4 || i == 7))
      {
         if(board[i][j+1] == p || board[i][j+2] == p || board[i+1][j] == p || 
             board[i+2][j] == p || board[i+1][j+1] == p || board[i+1][j+2] == p || 
                 board[i+2][j+1] == p || board[i+2][j+2] == p)return false;     
      } 


    /*
      000
      000
      *00
    */  
    if((j == 1 || j == 4 || j == 7) && (i == 3 || i == 6 || i == 9))
      {
         if(board[i-1][j] == p || board[i-2][j] == p || board[i][j+1] == p || 
             board[i][j+2] == p || board[i-1][j+1] == p || board[i-1][j+2] == p || 
                 board[i-2][j+1] == p || board[i-2][j+2] == p)return false;   
      }

    /*
      000
      *00
      000
    */            
    if((j == 1 || j == 4 || j == 7) && (i == 2 || i == 5 || i == 8))
      {
         if(board[i-1][j] == p || board[i+1][j] == p || board[i-1][j+1] == p || 
             board[i][j+1] == p || board[i+1][j+1] == p || board[i+1][j+2] == p || 
                 board[i][j+2] == p || board[i+1][j+2] == p)return false;  
      } 


    /*
      0*0
      000
      000
    */            
    if((j == 2 || j == 5 || j == 8) && (i == 1 || i == 5 || i == 7))
      {
         if(board[i-1][j] == p || board[i+1][j] == p || board[i-1][j+1] == p || 
             board[i][j+1] == p || board[i+1][j+1] == p || board[i+1][j+2] == p || 
                 board[i][j+2] == p || board[i+1][j+2] == p)return false;  
      }

    /*
      000
      0*0
      000
    */            
    if((j == 2 || j == 5 || j == 8) && (i == 2 || i == 5 || i == 8))
      {
         if(board[i-1][j] == p || board[i-1][j-1] == p || board[i-1][j+1] == p || 
             board[i][j+1] == p || board[i][j-1] == p || board[i+1][j+1] == p || 
                 board[i][j] == p || board[i+1][j-1] == p)return false;  
      }


    /*
      000
      000
      0*0
    */            
    if((j == 2 || j == 5 || j == 8) && (i == 3 || i == 6 || i == 9))
      {
         if(board[i][j-1] == p || board[i][j+1] == p || board[i-1][j] == p || 
             board[i-1][j+1] == p || board[i-1][j-1] == p || board[i-2][j] == p || 
                 board[i-1][j+1] == p || board[i-2][j-1] == p) return false;  
      }  

    /*
      00*
      000
      000
    */            
    if((j == 3 || j == 6 || j == 9) && (i == 1 || i == 4 || i == 7))
      {
         if(board[i][j-1] == p || board[i][j-2] == p || board[i+1][j] == p || 
             board[i+1][j-1] == p || board[i+1][j-2] == p || board[i+2][j] == p || 
                 board[i+2][j-1] == p || board[i+2][j-2] == p) return false;  
      } 

    /*
      000
      00*
      000
    */            
    if((j == 3 || j == 6 || j == 9) && (i == 2 || i == 5 || i == 8))
      {
         if(board[i-1][j] == p || board[i-1][j-1] == p || board[i-1][j-2] == p || 
             board[i][j-1] == p || board[i][j-2] == p || board[i+1][j] == p || 
                 board[i+1][j-1] == p || board[i+1][j-2] == p) return false;  
      }

    /*
      000
      000
      00*
    */            
    if((j == 3 || j == 6 || j == 9) && (i == 3 || i == 6 || i == 9))
      {
         if(board[i][j-1] == p || board[i][j-1] == p || board[i-1][j] == p || 
             board[i-1][j-1] == p || board[i-1][j-2] == p || board[i-2][j] == p || 
                 board[i-2][j-1] == p || board[i-2][j-2] == p) return false;  
      }      

    return true;                          
  }

void Sudoku::Help_Solve(int i, int j)
  {
    if(j <= 0) 
      {
        i = i-1;
        j = 9;
      }
    if(change[i][j] == 1) return Game.Help_Solve(i, j-1);
    for(int p = 1; p <= 9; p++)
      if(Game.Check_Conflicts(p, i, j)) 
        {
          board[i][j] = p;
          return;
        }
    return Game.Help_Solve(i, j-1);

  }

void Sudoku::Solve()
  {                          
      for(int i = 1; i <= 9; i++)
        {
          for(int j = 1; j <= 9; j++)
            {
              if(board[i][j] == 0 && change[i][j] == 0)
                {
                  Game.Help_Solve(i, j);           
                }      
            }      
        }

      for(int i = 1; i <= 9; i++)
        for(int j = 1; j <= 9; j++)
          if(board[i][j] == 0) Game.Help_Solve(i, j);

  }


int main()
{
  Game.Add_First_Cord();
  Game.Solve();
  Game.Print_Board();  

  system("pause");
  return 0;
}

编辑：我需要使用递归，对吗？但也许我给函数的参数是错误的。在Add_First_Cord()中，我声明了每个数独在开始时具有的起始值。以下是我使用的值：http://bg.wikipedia.org/wiki/%D0%A4%D0%B0%D0%B9%D0%BB:Sudoku-by-L2G-20050714.gif。我期望看到像维基百科中显示的已解决的数独。但有些已解决的值是正确的，而其他的则不是。这是我在控制台中得到的结果

- Sinan Zikri

---

你需要给我们更多的信息。为什么你认为你的 Help_Solve 函数是错误的？你给它什么输入？你得到了什么输出，你期望得到什么？ - simonc

如果您不告诉我们您认为有什么问题，我们怎么能帮助您解决呢？如果您希望我们帮助您，请[编辑]您的问题并给出一些指示，告诉我们应该寻找什么。谢谢。 - Ken White

它有助于尽可能地简化您的代码以定位问题。人们不喜欢阅读非常长的代码摘录。 - glts

使用CSPs和回溯法解决问题 - T.T.T.

Answer 1

建议的方法

1. 实现通用图搜索算法
   • 可以使用IDFS或A*图搜索
   • 我更喜欢第二个
   • 为一个一般的有向图完成该操作
     • 节点类型为TNode
     • 节点后继函数为TNode => vector<TNode>
2. 定义数独状态
   • 一个状态是一个9x9的数组，每个位置有数字1、2、...、9或空白
3. 定义目标数独状态
   • 所有81个单元格都填满
   • 所有9行中都有数字{1, 2, ..., 9}
   • 所有9列中都有数字{1, 2, ..., 9}
   • 所有9个3x3方格中都有数字{1, 2, ..., 9}
4. 定义有效数独状态的后继函数
   • 如果以下条件成立，则可以在行I、列J中添加数字N：
     • 单元格(I,J)为空
     • 在行I中没有其他数字N
     • 在列J中没有其他数字N
     • 在包含(I,J)的3x3方格中没有其他数字N
   • 状态后继函数将状态S映射到满足这些规则的状态vector

将通用的图搜索算法（1）应用于数独状态图（2-4）

（可选）如果您选择使用A*图搜索，您还可以在数独状态空间上定义一个启发式算法，以潜在地大幅提高性能

• 如何设计启发式算法是另一个完整的问题，更多的是艺术而不是科学

当前方法

您当前的方法混淆了要搜索的图形规范和搜索算法的实现。如果混合这两者，您将会遇到很多困难。此问题自然分为两个不同的部分——算法和图表——因此，您可以利用它们在实现中，并且应该这样做。这将使它变得简单得多。

如果您采用此分离方法，您将能够在大量问题上重复使用您的图搜索算法-非常酷！

- Timothy Shields

---

这个问题也可以被重新表述为一个SAT问题，然后您可以使用通用的SAT求解器来解决它。 - Adam Rosenfield

我还不知道如何使用图表 :/ 你能否建议另一种解决方案，就像我尝试使用的那种？ :) - Sinan Zikri

@SinanZikri 我不知道你试图使用的算法除了图搜索之外还能叫什么。回溯的概念字面意思是沿着搜索图往回走。 - Timothy Shields

谢谢回答，但我仍然无法弄清楚我的错误:/ - Sinan Zikri

@SinanZikri - 你的错误在于概念上。没有有效的算法，创建可工作的代码将非常困难。 - Bill Weinman

@SinanZikri 如果你唯一不采取我的建议的原因是你不理解图形数据结构，我强烈建议你去学习它们！这将是值得花时间的。 :) - Timothy Shields

Answer 2

以下假设您正在尝试解决给定的棋盘，而不是生成一个难题。

基本（简单）方法

创建一个类，其对象可以保存一个棋盘（在这里称为board_t）。该类可以在内部使用数组，但必须支持复制棋盘。

有一个函数void solve(board_t const& board);，它对每个数字n重复执行以下操作：

- 复制您的输入。 - 将n输入到复制的棋盘的第一个空单元格中。 - 如果复制的棋盘是解决方案，则打印解决方案并返回。 - 否则，如果棋盘仍然可行（例如没有冲突）： - 调用solve(copied_board)

性能

这是一种递归回溯解决方案，对于困难问题表现非常糟糕。通过适当修剪或推理步骤（例如，如果插入一个数字后您最终得到8个数字在一行中，您可以立即输入第九个数字，而无需进行任何搜索），可以显着加快速度。

推理

虽然这种技术并不令人印象深刻，但它有很高的正确性概率，因为您只会修改一个副本以添加单个值。这可以防止数据结构的损坏（您的想法之一是，在回溯时它将破坏找到的数字，这些数字不一定是您刚刚插入的数字，而可能是初始谜题的一部分）。

提高性能非常简单，一旦开始选择更智能的启发式方法（例如，而不是按顺序测试正方形，您可以选择剩余移动最少的那些正方形并尝试将它们放在路边 - 或者反过来...）或开始进行一些推断和修剪。

注意：算法设计手册使用Soduko求解器展示了这些技术对回溯的影响。

- danielschemmel

---

这只是一个DFS图搜索，其中“搜索算法”是使用语言的递归函数。你可以这样做，但可能会非常慢... - Timothy Shields

当然可以。实际上，您可以轻松地修改隐式深度优先搜索算法以利用A*或迭代加深算法。（如果基本技巧不足够，我个人会首先考虑对称性。）明确表示这不是一个显式图问题是为了不让OP更加困惑，因为他似乎已经很难准确表达这个算法。 - danielschemmel

Answer 3

递归算法有一个非常重要的修改：使用最受限制的先前方法。这意味着首先解决可能候选者数量最少的单元格（当直接行/列/块冲突被移除时）。

另一个修改是：原地更改棋盘；不要复制它。在每个递归调用中，您只修改棋盘上的一个单元格，并且该单元格以前为空。如果该调用没有在递归调用树中的某个位置结束为已解决的棋盘，则在返回之前再次清除该单元格-这将使棋盘恢复到原始状态。

您可以在以下地址中找到C＃中非常简短且快速的解决方案：Sudoku Solver。由于最受限制的先发启发式，它仅在大约100步内解决任意数独板。

- Zoran Horvat

Answer 4

这是一个经典的约束满足问题。我建议你在这个主题上做一些研究，找出成功的策略。你需要使用AC-3（弧一致性3）算法以及回溯技术来解决这个问题。

- s.n