Hi,
I am writing a sudoku solver program that uses recursion to solve all the empty cells.
However, I have no idea why my function did not do anything.
I read in my puzzle as double char array and convert it to double int array.
My output is :
900020750
600050040
020400010
208000000
070509060
000000401
010005080
090070004
082040006
where all the 0s are the empty cells
//
#include "puzzle.h"
#include <iostream>
#include <stdlib.h>
using namespace std;
Puzzle::Puzzle(const char grid[][9])
{ /*
for(int i = 0; i < 9; i++)
{
for(int j = 0; j < 9; j++)
{
//cout << "row"<< i << " column" << j << " "<< grid[i][j] << endl;
if(grid[i][j] == '*')
puzzle[i][j] = 0;
else
puzzle[i][j] = grid[i][j] - '0';
//cout << "puzzle row" << i << " column" << j << " " << puzzle[i][j] << endl;
}
}*/
for(int i = 0; i < 9; i++)
for(int j = 0; j < 9; j++)
puzzle[i][j] = 0;
puzzle[0][0] = 9;
puzzle[0][4] = 2;
puzzle[0][6] = 7;
puzzle[0][7] = 5;
puzzle[1][0] = 6;
puzzle[1][4] = 5;
puzzle[1][7] = 4;
puzzle[2][1] = 2;
puzzle[2][3] = 4;
puzzle[2][7] = 1;
puzzle[3][0] = 2;
puzzle[3][2] = 8;
puzzle[4][1] = 7;
puzzle[4][3] = 5;
puzzle[4][5] = 9;
puzzle[4][7] = 6;
puzzle[5][6] = 4;
puzzle[5][8] = 1;
puzzle[6][1] = 1;
puzzle[6][5] = 5;
puzzle[6][7] = 8;
puzzle[7][1] = 9;
puzzle[7][4] = 7;
puzzle[7][8] = 4;
puzzle[8][1] = 8;
puzzle[8][2] = 2;
puzzle[8][4] = 4;
puzzle[8][8] = 6;
}
bool Puzzle::isRowValid(int row, int num)
{
for(int col = 0; col < 9; col++)
{
if(puzzle[row][col] == num)
return false;
}
return true;
}
bool Puzzle::isColValid(int col, int num)
{
for(int row = 0; row < 9; row++)
{
if(puzzle[row][col] == num)
return false;
}
return true;
}
bool Puzzle::isBoxValid(int row, int col, int value)
{
row = (row/3)*3;
col = (col/3)*3;
for(int i = 0; i < 3; i++)
{
for(int j = 0; j < 3; j++)
{
if(puzzle[row+i][col+j] == value)
return false;
}
}
return true;
}
void Puzzle::next(int row, int col)
{
if(col < 8)
solve(row,col+1);
else
solve(row+1,0);
}
void Puzzle::solve(int row, int col)
{
// exit when row is > 8
if(row > 8)
return;
// check if cell needs to be solve
if(puzzle[row][col] != 0)
next(row, col);
else
{
// find a valid number for current cell
for(int num = 1; num <= 9; num++)
{
if(isRowValid(row,num) && isColValid(col,num) && isBoxValid(row,col,num))
{
//cout << "check2" << endl;
puzzle[row][col] = num;
//cout << "puzzle row" << row << " column" << col << " " << num << endl;
next(row,col);
}
}
// valid number not found, return to caller
puzzle[row][col] = 0;
}
}
void Puzzle::display()
{
for(int row = 0; row < 9; row++)
{
for(int col = 0; col < 9; col++)
cout << puzzle[row][col];
cout << endl;
}
}