Sudoku solving algorithm C++

Question

asked Jul 20, 2019 in AI and Deep Learning by ashely (50.2k points)

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:

start at the first empty cell, and put 1 in it.
Check the entire board, and see if there are any conflicts
If there are conflicts on the board, increase the number in the current cell by 1 (so change 1 to 2, 2 to 3, etc)
If the board is clean move, start at step one again.
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

1 Answer

vinita · Answer 1 · 2019-07-20T14:32:16+0000

There are two approaches:

first is the Simple Algorithm

The Simple Algorithm is to generate all possible configurations of numbers from 1 to 9 to fill the blank cells. you have to Try every configuration one by one until the correct configuration is found.

second is the Backtracking Algorithm

Like all other Backtracking problems, we can solve Sudoku by one by one assigning numbers to empty cells. Before specifying a number, we check whether it is safe to assign. We primarily check that the same number is not present in the current row, current column and current 3X3 subgrid. After investigating for safety, we assign the number, and recursively check whether this assignment leads to a solution or not. If the task doesn’t lead to a solution, then we try the next number for the current empty cell. And if none of the number (1 to 9) leads us to a solution, we return false.

For full implementation of the Solving Sudoku using a simple search algorithm, refer to the following link:

https://medium.com/@george.seif94/solving-sudoku-using-a-simple-search-algorithm-3ac44857fee8

Sudoku solving algorithm C++

1 Answer

Related questions

Browse Categories