backtrack solver algorithm for sudoku puzzles in c which counts possible solutions
I found this c code implementing a sudoku solver backtrack algorithm and it is able to find a solution to any sudoku puzzle that has at least one solution. i would like to know if there is an easy adjustment, that it is able to tell if there is more than one solution at a given sudoku puzzle
#include <stdio.h>
int matrix[9][9]={0}; //row*col sudoku numbers
int test[9][9] = {
{5, 3, 0, 0, 7, 0, 0, 0, 0} ,
{6, 0, 0, 1, 9, 5, 0, 0, 0} ,
{0, 9, 8, 0, 0, 0, 0, 6, 0} ,
{8, 0, 0, 0, 6, 0, 0, 0, 3} ,
{4, 0, 0, 8, 0, 3, 0, 0, 1} ,
{7, 0, 0, 0, 2, 0, 0, 0, 6} ,
{0, 6, 0, 0, 0, 0, 2, 8, 0} ,
{0, 0, 0, 4, 1, 9, 0, 0, 5} ,
{0, 0, 0, 0, 8, 0, 0, 7, 9}
};
int veryhard[9][9] = {
{8, 0, 0, 0, 0, 0, 0, 0, 0} ,
{0, 0, 3, 6, 0, 0, 0, 0, 0} ,
{0, 7, 0, 0, 9, 0, 2, 0, 0} ,
{0, 5, 0, 0, 0, 7, 0, 0, 0} ,
{0, 0, 0, 0, 4, 5, 7, 0, 0} ,
{0, 0, 0, 1, 0, 0, 0, 3, 0} ,
{0, 0, 1, 0, 0, 0, 0, 6, 8} ,
{0, 0, 8, 5, 0, 0, 0, 1, 0} ,
{0, 9, 0, 0, 0, 0, 4, 0, 0}
};
int fivesolution[9][9] = {
{0, 0, 0, 0, 0, 0, 0, 0, 0} ,
{0, 1, 6, 0, 3, 0, 0, 5, 0} ,
{0, 9, 0, 0, 0, 2, 0, 0, 8} ,
{0, 0, 7, 0, 0, 8, 0, 0, 0} ,
{0, 6, 0, 0, 1, 0, 3, 4, 5} ,
{2, 5, 1, 0, 4, 0, 0, 0, 0} ,
{0, 0, 0, 0, 9, 0, 0, 8, 0} ,
{0, 4, 0, 5, 2, 1, 6, 7, 0} ,
{0, 2, 0, 0, 8, 3, 0, 0, 0}
};
int moresolution[9][9] = {
{1, 0, 0, 0, 0, 0, 0, 0, 0} ,
{0, 0, 0, 0, 0, 0, 0, 0, 0} ,
{0, 0, 0, 0, 0, 0, 0, 0, 0} ,
{0, 0, 0, 0, 0, 0, 0, 0, 0} ,
{0, 0, 0, 0, 0, 0, 0, 0, 0} ,
{0, 0, 0, 1, 0, 0, 0, 0, 0} ,
{0, 0, 0, 0, 0, 0, 0, 0, 0} ,
{0, 0, 0, 0, 0, 0, 0, 0, 0} ,
{0, 0, 0, 0, 0, 0, 0, 0, 0}
};
int nosolution[9][9] = {
{0, 0, 0, 0, 0, 0, 0, 0, 0} ,
{0, 1, 6, 0, 3, 0, 0, 5, 0} ,
{0, 9, 0, 0, 0, 2, 0, 0, 8} ,
{0, 0, 7, 0, 0, 8, 0, 0, 0} ,
{0, 6, 0, 0, 1, 0, 3, 4, 5} ,
{0, 0, 0, 0, 0, 0, 0, 0, 0} ,
{0, 0, 0, 0, 0, 0, 0, 8, 0} ,
{0, 4, 0, 0, 2, 1, 6, 7, 0} ,
{0, 5, 0, 0, 4, 3, 0, 0, 0}
};
int usedInRow(int matrix[9][9],int row,int num) {
for (int col = 0; col < 9; col++) {
if (matrix[row][col] == num) {
return 1;
}
}
return 0;
}
int usedInCol(int matrix[9][9],int col,int num) {
for (int row = 0; row < 9; row++) {
if (matrix[row][col] == num) {
return 1;
}
}
return 0;
}
int usedInBox(int matrix[9][9],int boxStartRow,int boxStartCol,int num) {
for (int row = 0; row < 3; row++) {
for (int col = 0; col < 3; col++) {
if (matrix[row + boxStartRow][col + boxStartCol] == num) {
return 1;
}
}
}
return 0;
}
int isSafe(int matrix[9][9],int row,int col,int num) {
return (
!usedInRow(matrix, row, num) &&
!usedInCol(matrix, col, num) &&
!usedInBox(matrix, row - (row % 3), col - (col % 3), num)
);
}
void print_sgrid(int matrix[9][9]){
for(int a=0;a<9;a++){
for (int b=0;b<9;b++){
printf("%d ",matrix[a][b]);
if (b==2 || b==5) printf("| ");
}
printf("\n");
if (a==2 || a==5) printf("------+-------+------\n");
}
}
int solveSudoku(int matrix[9][9]) {
int row = 0;
int col = 0;
int checkBlankSpaces = 0;
/* verify if sudoku is already solved and if not solved,
get next "blank" space position */
for (row = 0; row < 9; row++) {
for (col = 0; col < 9; col++) {
if (matrix[row][col] == 0) {
checkBlankSpaces = 1;
break;
}
}
if (checkBlankSpaces == 1) {
break;
}
}
// no more "blank" spaces means the puzzle is solved
if (checkBlankSpaces == 0) return 1;
// try to fill "blank" space with correct num
for (int num = 1; num <= 9; num++) {
/* isSafe checks that num isn't already present
in the row, column, or 3x3 box (see below) */
if (isSafe(matrix, row, col, num)) {
matrix[row][col] = num;
if (solveSudoku(matrix)) return 1;
/* if num is placed in incorrect position,
mark as "blank" again then backtrack with
a different num */
matrix[row][col] = 0;
}
}
return 0;
}
int main (void){
if (solveSudoku(veryhard))
print_sgrid(veryhard);
return 0;
}
This modification works for me, found no problems with it so far. Note that solution_cnt needs to be declared globally and cleared before you try to count solutions again.
int count_solutions(int matrix[9][9]) {
int row = 0;
int col = 0;
int checkBlankSpaces = 0;
/* verify if sudoku is already solved and if not solved,
get next "blank" space position */
for (row = 0; row < 9; row++) {
for (col = 0; col < 9; col++) {
if (matrix[row][col] == 0) {
checkBlankSpaces = 1;
break;
}
}
if (checkBlankSpaces == 1) {
break;
}
}
// no more "blank" spaces means the puzzle is solved
if (checkBlankSpaces == 0){
solution_cnt++;
return solution_cnt;
}
// try to fill "blank" space with correct num
for (int num = 1; num <= 9; num++) {
/* isSafe checks that num isn't already present
in the row, column, or 3x3 box (see below) */
if (isSafe(matrix, row, col, num)) {
matrix[row][col] = num;
if(count_solutions(matrix)>1)return solution_cnt; //stop after a found amount of solutions
/* if num is placed in incorrect position,
mark as "blank" again then backtrack with
a different num */
matrix[row][col] = 0;
}
}
return solution_cnt;
}