Sudoku
/***
Sudoku
Given
a partially filled 9×9 2D array ‘grid[9][9]‘, the goal is to assign digits
(from 1 to 9) to the empty cells so that every row, column,
and subgrid of size 3×3 contains exactly one instance of the digits from 1 to
9.
Backtracking
Algorithm
Like
all other Backtracking problems, we can solve Sudoku by one by one assigning
numbers to empty cells. Before
assigning a number, we check whether it is safe to assign. We basically check
that the same number is
not present in current row, current column and current 3X3 subgrid. After
checking for safety, we
assign the number, and recursively check whether this assignment leads to a
solution or not. If
the assignment doesn’t lead to a solution, then we try next number for current
empty cell. And
if none of number (1 to 9) lead to solution, we return false.
***/
#include<iostream>
using namespace std;
class Sudoku {
public:
Sudoku(int (*m)[9]);
~Sudoku(){ };
bool fill_Sudoku();
void print();
private:
int sudo[9][9];
// index
by number, fill[i][j], j is the row array which fill by the column.
int fill[10][9];
bool isSafe(int, int, int);
bool isSuccess(int*, int*);
};
Sudoku :: Sudoku (int (*m)[9]) {
//initial
sudo[][] and fill[][]
for(int i = 1; i<10; i++) {
for(int j = 0; j<9; j++)
fill[i][j] = -1;
}
for(int i = 0; i<9; i++) {
for(int j = 0; j<9; j++) {
sudo[i][j] = m[i][j];
if(sudo[i][j] != 0) {
fill[sudo[i][j]][i] =
j;
}
}
}
}
bool Sudoku :: isSafe(int num, int row, int col) {
if(fill[num][row] != -1) return false;
for(int i = 0; i<9; i++) {
if(fill[num][i] == col) return false;
}
int r = row / 3;
int c = col / 3;
for(int i = r*3; i<r*3+3; i++) {
for(int j = c*3; j<c*3+3; j++) {
if(sudo[i][j] == num) return false;
}
}
return true;
}
bool Sudoku :: isSuccess(int *row, int *col) {
for(int i = 0; i<9; i++) {
for(int j = 0; j<9; j++) {
if(sudo[i][j] == 0) {
*row = i;
*col = j;
return false;
}
}
}
return true;
}
bool Sudoku :: fill_Sudoku() {
int row, col;
if(isSuccess(&row, &col)) {
return true;
}
for(int i = 1; i<=9; i++) {
if(isSafe(i, row, col)) {
sudo[row][col] = i;
fill[i][row] = col;
if(fill_Sudoku()) return true;
sudo[row][col] = 0;
fill[i][row] = -1;
}
}
return false;
}
void Sudoku::print() {
for (int i = 0; i<9; i++)
{
for (int j = 0; j<9; j++)
{
cout<<sudo[i][j]<<" ";
}
cout<<endl;
}
}
int main()
{
// 0
means unassigned cells
int grid[9][9] = {
{3, 0, 6, 5, 0, 8, 4, 0, 0},
{5, 2, 0, 0, 0, 0, 0, 0, 0},
{0, 8, 7, 0, 0, 0, 0, 3, 1},
{0, 0, 3, 0, 1, 0, 0, 8, 0},
{9, 0, 0, 8, 6, 3, 0, 0, 5},
{0, 5, 0, 0, 9, 0, 6, 0, 0},
{1, 3, 0, 0, 0, 0, 2, 5, 0},
{0, 0, 0, 0, 0, 0, 0, 7, 4},
{0, 0, 5, 2, 0, 6, 3, 0, 0}};
Sudoku sd(grid);
sd.fill_Sudoku();
sd.print();
return 0;
}
Note: when checking the valid in subgrid, pay more attention on the index
ReplyDelete