Sudoku solving algorithm C++

Question

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).

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

    #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

Solution 1

Suggested Approach

1. Implement a generic graph search algorithm
   • could use either IDFS or 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 S can have number N added at row I, column J if:
     • cell (I,J) is empty
     • there is no other N in row I
     • there is no other N in column J
     • there is no other N in the 3x3 square containing (I,J)
   • the state successor function maps a state S to the vector of 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

Current Approach

Your current approach mixes the specification of the graph to be searched and 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 reuse your graph search algorithm on a huge number of problems - very cool!

Solution 2

The following assumes you are trying to solve a 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.

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

• Copies your input
• Enters n in 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)

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).

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 Manual uses a Soduko solver to show the impact of these techniques on backtracking.

Solution 3

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.

Comments

[Adam Rosenfield]

The problem can also be reformulated as a SAT problem, which you can then use a general SAT solver for.

[Sinan Zikri]

I don't know how to use graphs yet :/ Can you suggest another solution like the one I have tried to use? :)

[Timothy Shields]

@SinanZikri I wouldn't know what to call the algorithm you're trying to use other than a graph search. The concept of backtracking literally means going back up the search graph.

[Timothy Shields]

This is just a DFS graph search, with the "search algorithm" being the use of the language's recursive functions. You can do this, but it might be very slow...

[danielschemmel]

Of course it is. In fact, you can easily modify an implicit DFS like this to utilize A* or Iterative Deepining. (Personally I would start by going for symmetries, if the basic tricks should prove insufficient.) Not making this an explicit graph problem is done explicitly to not confuse the OP, who seems to already struggle to express exactly this algorithm, further.

[Sinan Zikri]

Thanks for the answers, but I still can't figure out what is my mistake :/

[Bill Weinman]

@SinanZikri - Your mistake is conceptual. Without a valid algorithm, it will be very difficult to create working code.

[Timothy Shields]

@SinanZikri If the only thing stopping you from taking my suggested approach is that you don't understand graph data structures, I strongly urge you to go learn them! It will be time well spent. :)