数独求解算法 C++

Sudoku solving algorithm C++

提问by Sinan Zikri

I'm trying to make a Sudoku Solving program for a couple of days but I'm stuck with the methods. I found this algorithm here but I don't really understand it:

我正在尝试制作一个数独求解程序几天，但我坚持使用这些方法。我在这里找到了这个算法，但我不太明白：

1. start at the first empty cell, and put 1 in it.
2. Check the entire board, and see if there are any conflicts
3. If there are coflicts on the board, increase the number in the current cell by 1 (so change 1 to 2, 2 to 3, etc)
4. If the board is clean move, start at step one again.
5. If all nine possible numbers on a given cell cause a conflict in the board, then you set this cell back to empty, go back to the previous cell, and start again from step 3 (this is where the 'backtracking' comes in).

1. 从第一个空单元格开始，并在其中输入 1。
2. 检查整个板子，看看有没有冲突
3. 如果板上有冲突，请将当前单元格中的数字增加 1（因此将 1 更改为 2、2 为 3 等）
4. 如果棋盘是干净的移动，请再次从第一步开始。
5. 如果给定单元格上的所有九个可能数字都导致棋盘冲突，那么您将该单元格设置回空，返回到前一个单元格，并从第 3 步重新开始（这是“回溯”出现的地方）。

Here is my code. I think something is wrong with my Help_Solve(...)function. Can you help me to identify the problem, please?

这是我的代码。我认为我的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;
}

Edit: I need to use recursion right? But maybe the parameters I give to the function are wrong. I really don't know. In Add_First_Cord()I declare the starting values that every sudoku has in the beginning. Here are the values that I use: http://bg.wikipedia.org/wiki/%D0%A4%D0%B0%D0%B9%D0%BB:Sudoku-by-L2G-20050714.gif. I expect to see the solved sudoku as it is shown in wikipedia. But some solved values are right others are not. Here is what I get in the console

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

回答by Timothy Shields

Suggested Approach

建议的方法

1. Implement a generic graph search algorithm
   • could use either IDFSor A* graph search
     • I would prefer the second
   • do this for a general directed graph
     • node type TNode
     • node successor function TNode => vector<TNode>
2. Define your Sudoku states
   • a state is a 9x9 array with a number 1, 2, ..., or 9 or a blank in each position
3. Define what a goal Sudoku state is
   • all 81 cells filled in
   • all 9 rows have numbers {1, 2, ..., 9} in them
   • all 9 columns have numbers {1, 2, ..., 9} in them
   • all 9 3x3 squares have numbers {1, 2, ..., 9} in them
4. Define your valid Sudoku state successor function
   • a state Scan have number Nadded at row I, column Jif:
     • cell (I,J)is empty
     • there is no other Nin row I
     • there is no other Nin column J
     • there is no other Nin the 3x3 square containing (I,J)
   • the state successor function maps a state Sto the vectorof states that satisfy these rules
5. Apply your generic graph search algorithm (1) to the Sudoku state graph (2-4)
6. (optional) If you do choose to use A* graph search, you can also define a heuristic on your Sudoku state space to potentially drastically increase performance
   • how to design the heuristic is another whole problem, that's more of an art than a science

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. 定义有效的数独状态后继函数
   • 一个状态S可以N在 row I， column添加数字，J如果：
     • 单元格(I,J)为空
     • 没有其他人N在排I
     • N列中没有其他内容J
     • N3x3 方格中没有其他包含(I,J)
   • 状态后继函数将状态映射S到vector满足这些规则的状态
5. 将您的通用图搜索算法 (1) 应用于数独状态图 (2-4)
6. （可选）如果您选择使用 A* 图搜索，您还可以在数独状态空间上定义启发式算法，以潜在地大幅提高性能
   • 如何设计启发式是另一个完整的问题，这更像是一门艺术而不是一门科学

Current Approach

当前方法

Your current approach mixes the specification of the graph to be searchedand the implementation of the search algorithm. You're going to have a lot of difficulty if you mix those two. This problem naturally separates into two distinct pieces -- the algorithm and the graph -- so you can and should exploit that in your implementation. It will make it much simpler.

您当前的方法混合了要搜索的图的规范和搜索算法的实现。如果你把这两者混合起来，你会遇到很多困难。这个问题自然地分为两个不同的部分——算法和图——所以你可以而且应该在你的实现中利用它。它会让事情变得简单得多。

The other benefit you get if you go with this separation is that you will be able to reuseyour graph search algorithm on a huge number of problems - very cool!

如果你采用这种分离，你得到的另一个好处是你将能够在大量问题上重用你的图搜索算法 - 非常酷！

回答by gha.st

The following assumes you are trying to solvea given board, not generate a puzzle.

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

Basic (simple) approach

基本（简单）方法

Create a class whose objects can hold a board (here called board_t). This class may internally use array, but must support copying boards.

创建一个类，其对象可以容纳一块板（此处称为board_t）。该类内部可以使用数组，但必须支持抄板。

Have a function void solve(board_t const& board);which repeats the following for each number n:

具有void solve(board_t const& board);对每个数字重复以下内容的函数n：

• Copies your input
• Enters nin the first empty cell of the copied board
• If the copied board is a solution, print the solution and return.
• Else If the board is still viable (e.g. no conflicts):
  • call solve(copied_board)

• 复制您的输入
• 进入n复制板的第一个空单元格
• 如果抄板是解法，打印解法和return。
• 否则如果董事会仍然可行（例如没有冲突）：
  • 称呼 solve(copied_board)

Performance

表现

This is a recursive backtracking solution, which performs horribly for hard problems. You can significantly speed it up by proper pruning or deductive steps (e.g. if you end up with 8 numbers in a row after inserting one, you can immediately enter the ninth without any kind of search).

这是一个递归回溯解决方案，它在解决难题时表现得非常糟糕。您可以通过适当的修剪或演绎步骤来显着加快速度（例如，如果您在插入一个数字后以连续 8 个数字结束，您可以立即输入第 9 个数字，而无需任何类型的搜索）。

Reasoning

推理

While certainly not an impressive technique, it has a high probability of working correctly, since you will only ever be modifying a copy to add a single value. This prevents corruption of your data structures (one problem your idea has is that it will destroy the numbers it finds when backtracking, are not necessarily the ones you just inserted, but may be part of the initial puzzle).

虽然肯定不是一种令人印象深刻的技术，但它很有可能正常工作，因为您只会修改副本以添加单个值。这可以防止您的数据结构损坏（您的想法存在的一个问题是它会破坏回溯时找到的数字，不一定是您刚刚插入的数字，但可能是初始难题的一部分）。

Improving performance is quite simple, once you start picking more intelligent heuristics (e.g. instead of testing the square in order, you could pick the ones with the fewest remaining moves and try to get them out of the way - or do the reverse...) or start doing a bit of deduction and pruning.

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

Note: The Algorithm Design Manualuses a Soduko solver to show the impact of these techniques on backtracking.

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

回答by Zoran Horvat

There is one very important modification to recursive algorithms: Use most constrained first approach. This means first to solve a cell with smallest number of possible candidates (when direct row/column/block conflicts are removed).

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

Another modification is: Change the board in-place; do not copy it. In each recursive call you modify only one cell on the board, and that cell used to be empty. If that call doesn't end up in a solved board somewhere down the recursive call tree, just clear the cell again before returning - this returns the board into original state.

另一个修改是：就地更改电路板；不要复制它。在每次递归调用中，您只修改板上的一个单元格，而该单元格曾经是空的。如果该调用未在递归调用树的某个位置结束，则只需在返回之前再次清除单元格 - 这会将板返回到原始状态。

You can find a very short and fast solution in C# on address: Sudoku Solver. It solves arbitrary sudoku board in about 100 steps only, all thanks to the most constrained first heuristic.

您可以在 C# 中找到一个非常简短且快速的解决方案：Sudoku Solver。它仅在大约 100 步内解决任意数独板，这一切都归功于最受约束的第一启发式。

回答by s.n

This is a classic Constraint Satisfaction Problem. I recommend doing some research on the topic to figure out the successful strategy. You will need to use AC-3 ( Arc Consistency 3) algorithm along with the backtracking techniques to solve the problem.

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