0

我一直在寻找数独求解算法一段时间，我找到了这段代码。但我有一些困难。我无法理解。如果单个单元格中 1 到 9 之间的所有数字都存在冲突，程序应该停止，对吗？但它仍在继续。有人可以解释一下代码是如何工作的吗？这里是：

bool Sudoku::Help_Solve(int i, int j)
{
    int nextrow, nextcol;
    while(change[i][j] == 1) //We find the first cell in which we can change the number
    {                      
        j++;
        if(j > 9)
        {
            j = 1;
            i++;     
        }     
        if(i > 9) return true;            
    }


    for(int p = 1; p <= 9; p++)
    {
        if(Game.Check_Conflicts(p, i, j)) //We are checking for conflicts
        {
            board[i][j] = p;
            nextrow = i;
            nextcol = j+1;    
            if(nextcol > 9)
            {
                nextcol = 1;
                nextrow++;     
            } 
            if(nextcol == 1 && nextrow == 10) return true; 
            if(Game.Help_Solve(nextrow, nextcol)) return true;                   
        }      
    }
    board[i][j] = 0;
    return false;
}
4

4 回答 4

0

问题是我无法理解为什么它会继续，如果它最终返回 false ：/

它并不总是在函数的底部返回 tho'：

bool Sudoku::Help_Solve(int i, int j)
{
    int nextrow, nextcol;
    while(change[i][j] == 1) //We find the first cell in which we can change the number
    {                      
        j++;
        if(j > 9)
        {
            j = 1;
            i++;     
        }     
        if(i > 9) return true;            

-------------------------^^^^
returns true if we have filled all squares.

    }


    for(int p = 1; p <= 9; p++)
    {
        if(Game.Check_Conflicts(p, i, j)) //We are checking for conflicts
        {
            board[i][j] = p;
            nextrow = i;
            nextcol = j+1;    
            if(nextcol > 9)
            {
                nextcol = 1;
                nextrow++;     
            } 
            if(nextcol == 1 && nextrow == 10) return true; 
-----------------------------------------------------^^^^   
           returns when we have filled everything!

            if(Game.Help_Solve(nextrow, nextcol)) return true;                
---------------------------------------------------------^^^^
          returns if we filled at the next level of solution. 
        }      
    }
    board[i][j] = 0;
    return false;
-----------^^^^^ returns if we failed to fill the whole thing. 
}

正如其他人在评论中提到的那样，可以做一些琐碎的事情来改进算法——比如寻找“最适合先填充的地方”[这并不能改善最坏的情况，但确实可以改善典型案例]。

我编写了一个使用类似算法的数独求解器，但它试图找到候选数最少的单元格（可能的数字进入该单元格），并且只有在有多个选择时才递归尝试。

于 2013-05-25T22:14:38.840 回答
0

如果您想查看它，这是整个代码：

    #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();  
    bool 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 = 0; i <= 9; i++)
      for(int j = 0; 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+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;  
      } 


    /*
      0*0
      000
      000
    */            
    if((j == 2 || j == 5 || j == 8) && (i == 1 || i == 4 || i == 7))
      {
         if(board[i][j-1] == p || board[i][j+1] == p || board[i+1][j+1] == p || 
             board[i+1][j-1] == p || board[i+1][j] == p || board[i+2][j-1] == p || 
                 board[i+2][j] == p || board[i+2][j+1] == 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+1][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-2][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-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;  
      }      

    return true;                          
  }

bool Sudoku::Help_Solve(int i, int j)
  {
    int nextrow, nextcol;
    while(change[i][j] == 1)
      {
        j++;
        if(j > 9)
          {
            j = 1;
            i++;     
          }     
        if(i > 9) return true;            
      }


    for(int p = 1; p <= 9; p++)
      {
        if(Game.Check_Conflicts(p, i, j))
          {
            board[i][j] = p;
            nextrow = i;
            nextcol = j+1;    
            if(nextcol > 9)
              {
                nextcol = 1;
                nextrow++;     
              } 
            if(nextcol == 1 && nextrow == 10) return true; 
            if(Game.Help_Solve(nextrow, nextcol)) return true;                   
          }      
      }
    board[i][j] = 0;
    return false;

  }


int main()
{
  Game.Add_First_Cord();
  Game.Help_Solve(1, 1);
  Game.Print_Board();  

  system("pause");
  return 0;
}
于 2013-05-25T19:00:20.257 回答
0

如果数字可以放在那里，或者由于简单的冲突而不能放在那里，它看起来像Sudoku::Check_Conflicts返回。不同的函数名称可能会更好地自我记录代码。truefalse

于 2013-05-25T19:07:28.630 回答
0

没有足够的代码来正确解释，在 Game.Check_Conflicts(p, i, j) 中发生了什么，这个函数是否被递归调用？

于 2013-05-25T18:52:15.127 回答