C++ Sudoku Solver using recursion backtracking not working

Question

I'm trying to code a sudoku solver with recursion and backtracking. But my code always returns false. The SudokuSolver() traverses only the first row up to fourth column and then it stops and starts backtracking. The problem is that the backtracking continues until the first cell and finally returns false. As a result, none of the empty cells(cells with value "-1" ) are replaced by any other numbers(1-9) and the board remains as it is.

Compiler shows [Done] exited with code=0 in 0.557 seconds

#include<iostream>
using namespace std;
# define N 9

bool SolveSudoku();
pair<int,int> FindUnassigned();
void PrintBoard();
bool NoConflict(int, int, int);
bool inRow(int,int);
bool inCol(int, int);
bool inGrid(int, int, int);
bool isFilled(pair<int,int>);

//board[row][col]==-1 indicates an empty position

int board[N][N] = {{3,-1,6,5,-1,8,4,-1,-1},
                   {5,2,-1,-1,-1,-1,-1,-1,-1},
                   {-1,5,7,-1,-1,-1,-1,3,1},
                   {-1,-1,3,-1,1,-1,-1,8,-1},
                   {9,-1,-1,8,6,3,-1,-1,5},
                   {-1,5,-1,-1,9,-1,6,-1,-1},
                   {1,3,-1,-1,-1,-1,2,5,-1},
                   {-1,-1,-1,-1,-1,-1,-1,7,4},
                   {-1,-1,5,2,-1,6,3,-1,-1}};


int main() {
    if(SolveSudoku()) 
        PrintBoard();
    return 0;
}


bool SolveSudoku() {
    pair<int,int> pos = FindUnassigned();
    int row=pos.first;
    int col=pos.second;
    if(isFilled(pos)) { return true; }
      for(int num=1; num<=9; num++) {
        if(NoConflict(num,row,col)) {
            board[row][col]=num;
            SolveSudoku();
            board[row][col]=-1;
        }  
      }
    return false;
}

pair<int,int> FindUnassigned() {
    pair<int,int> pos;
    pos.first=-1;
    pos.second=-1;
    for(int r=0; r<N; r++) {
        for(int c=0; c<N; c++) {
            if(board[r][c]==-1) {
                pos.first=r;
                pos.second=c;
                return pos;
            } 
        }
    }
    return pos;
}

bool isFilled(pair<int,int> pos) {
    return (pos.first==-1 && pos.second==-1);
}

bool NoConflict(int num, int r, int c) {
    return ((!inRow(numenter code here,r)==false) && (!inCol(num,c)==false) && (!inGrid(num,r-r%3,c-c%3)==false));
}

bool inRow(int num, int r) {
    for(int c=0; c<N; c++) {
        if(board[r][c]==num) return true;
    }
    return false;
}

bool inCol(int num, int c) {
    for(int r=0; r<N; r++) {
        if(board[r][c]==num) return true;
    }
    return false;
}

bool inGrid(int num, int rf, int cf) {
    for(int r=0; r<3; r++) {
        for(int c=0; c<3; c++) {
            if(board[r+rf][c+cf]==num) return true;
        }
    }
    return false;
}

void PrintBoard() {
    for(int r=0; r<N; r++) {
        for(int c=0; c<N; c++) {
            cout<<board[r][c]<<"\t";
        }
 enter code here       cout<<endl;
    }
}

Answer 1

• The SolveSudoku() needs to iterate untill all "cells" in the board has been visited.

• The NoConflict() looked strange, so I split the checks for clarity.

• Your example board has a conflicting value at [2][1] causing pre-mature termination.

I added a validation routine, to ensure a valid board before attempting to solve. The following seems to provide a solution of the Sudoku:

#include <iostream>
#include <cstdio>
using namespace std;
# define N 9

bool ValidateSudoku();
bool SolveSudoku();
bool FindUnassigned(pair<int,int>& pos );
void PrintBoard();
bool NoConflict(int, int, int);
bool inRow(int,int);
bool inCol(int, int);
bool inGrid(int, int, int);
bool isFilled(pair<int,int>);

int board[N][N] = {
  { 3,-1, 6,  5,-1, 8,  4,-1,-1},
  { 5, 2,-1, -1,-1,-1, -1,-1,-1},
  {-1, 5 /*this is wrong*/, 7, -1,-1,-1, -1, 3, 1},

  {-1,-1, 3, -1, 1,-1, -1, 8,-1},
  { 9,-1,-1,  8, 6, 3, -1,-1, 5},
  {-1, 5,-1, -1, 9,-1,  6,-1,-1},

  { 1, 3,-1, -1,-1,-1,  2, 5,-1},
  {-1,-1,-1, -1,-1,-1, -1, 7, 4},
  {-1,-1, 5,  2,-1, 6,  3,-1,-1}
};

int main() {
    std::cout<<"Solve:"<<std::endl;
    PrintBoard();
    std::cout<<std::endl;

    if (ValidateSudoku()) {
      if (SolveSudoku()) {
        std::cout<<"Solution:"<<std::endl;
        PrintBoard();
      }
      else {
        std::cout<<"Failed to solve"<<std::endl;
      }
    }
    else {
      std::cout<<"Board is invalid"<<std::endl;
    }
    return 0;
}


bool ValidateSudoku() {
  for (int row=0;row<N; row++) {
    for (int col=0; col<N; col++) {
      int num = board[row][col];
      board[row][col] = -1;
      if (num != -1) {
        if (inRow(num, row)) {
          return false;
        }

        if (inCol(num, col)) {
          return false;
        }

         if (inGrid(num, row-(row%3), col-(col%3))) {
          return false;
        }
      }
      board[row][col] = num;
    }
  }
  return true;
}

bool SolveSudoku() {
    pair<int,int> pos;
    while (FindUnassigned(pos)) {
      int row=pos.first;
      int col=pos.second;
      for(int num=1; num<=9; num++) {
        if(NoConflict(num,row,col)) {
            board[row][col]=num;
            if (SolveSudoku()) {
              return true;
            }

            board[row][col]=-1;
        }  
      }    
      return false;
    }
    return true;
}

bool FindUnassigned(pair<int,int>& pos ) {
    for(int r=0; r<N; r++) {
        for(int c=0; c<N; c++) {
            if(board[r][c]==-1) {
                pos.first=r;
                pos.second=c;
                return true;
            } 
        }
    }
    return false;
}

bool isFilled(pair<int,int> pos) {
    return (pos.first==-1 && pos.second==-1);
}

bool NoConflict(int num, int r, int c) {
    if (inRow(num, r)) {
      return false;
    }
    if (inCol(num, c)) {
      return false;
    }

    if (inGrid(num, r-(r%3), c-(c%3))) {
      return false;
    }
    return true;
    //I think this is buggy: return ((!inRow(num,r)==false) && (!inCol(num,c)==false) && (!inGrid(num,r-r%3,c-c%3)==false));
}

bool inRow(int num, int r) {
    for(int c=0; c<N; c++) {
        if(board[r][c]==num) return true;
    }
    return false;
}

bool inCol(int num, int c) {
    for(int r=0; r<N; r++) {
        if(board[r][c]==num) return true;
    }
    return false;
}

bool inGrid(int num, int rf, int cf) {
    for(int r=0; r<3; r++) {
        for(int c=0; c<3; c++) {
            if(board[r+rf][c+cf]==num) return true;
        }
    }
    return false;
}

void PrintBoard() {   
    for(int r=0; r<N; r++) {
        if (0 == (r % 3)) { std::cout<<std::endl; }
        for(int c=0; c<N; c++) {
           if (0 == (c % 3)) { std::cout<<" "; }
           std::cout.width(3);
           cout<<board[r][c]<<" ";
        }
        std::cout<<std::endl;
    }
}

Answer 2

Recursive functions work exactly like non-recursive functions.
(This is the most important thing to understand about recursion.)

Here:

board[row][col]=num;
SolveSudoku();
board[row][col]=-1;

you ignore the result of the function call, so you will recurse until the board is filled, then backtrack completely and finally return false;.

What you probably want is (thoroughly untested):

if (SolveSudoku())
{
    return true;
}

There is also a bug in NoConflict, which is equivalent to

bool NoConflict(int num, int r, int c) {
    return inRow(num,r) && inCol(num,c) && inGrid(num,r-r%3,c-c%3);
}

that is, there is no conflict if and only if num is already in the row, the column, and the grid.

You probably meant that num should not be found anywhere:

bool NoConflict(int num, int r, int c) {
    return !inRow(num,r) && !inCol(num,c) && !inGrid(num,r-r%3,c-c%3);
}

but added another negative by mistake.

It's possible that there are more bugs than this.