数独求解算法C++

Question

我正在努力制作一个Sudoku Solving程序几天,但我坚持使用这些方法.我在这里找到了这个算法,但我真的不明白它:

1. 从第一个空单元格开始,并在其中放入1.
2. 检查整个电路板,看看是否有任何冲突
3. 如果电路板上有coflicts,请将当前单元格中的数字增加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.我希望看到解决的数独,因为它在维基百科中显示.但有些解决的价值是正确的,其他则不是.这是我在控制台中得到的

Answer 1

建议的方法

1. 实现通用图搜索算法
   • 可以使用IDFS或A*图搜索
     • 我更喜欢第二个
   • 为常规有向图执行此操作
     • 节点类型 TNode
     • 节点后继函数 TNode => vector<TNode>
2. 定义您的Sudoku状态
   • 状态是9x9数组,每个位置的数字为1,2,...,或9或空白
3. 定义Sudoku状态的目标
   • 所有81个细胞都填满了
   • 所有9行都有数字{1,2,...,9}
   • 所有9列都有数字{1,2,...,9}
   • 所有9个3x3正方形都有数字{1,2,...,9}
4. 定义有效的Sudoku状态后继函数
   • 如果以下情况,状态S可以N在行I,列添加数字J:
     • 细胞(I,J)是空的
     • 没有其他N的排I
     • N专栏中没有其他内容J
     • N在3x3广场中没有其他包含(I,J)
   • 状态后继函数将状态映射S到vector满足这些规则的状态
5. 将通用图搜索算法(1)应用于Sudoku状态图(2-4)
6. (可选)如果您确实选择使用A*图搜索,您还可以在Sudoku状态空间中定义启发式,以潜在地显着提高性能
   • 如何设计启发式是另一个整体问题,更多的是艺术而不是科学

目前的方法

您当前的方法混合了要搜索的图表的规范和搜索算法的实现.如果你混合这两个,你会遇到很多困难.这个问题自然地分为两个不同的部分 - 算法和图形 - 所以你可以而且应该在你的实现中利用它.它会使它变得更简单.

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