/*
Sudoku solver by Rudi Bjørn Rasmussen.
This program solves a Sudoku puzzle by reursively guessing until
the puzzle.
To speed up the guessing, only numbers not already in row, col or
3 by 3 cell are tried.
*/
#include <iostream>
// dimension of the Sudoku board, 9 by 9 fields
const int NSIZE = 9;
// dimension of sub cells
const int CELLSIZE = 3;
// the sum of rows, columns and the 9 3x3 cells, 1+2+...9=45
const int SUM = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9;
// prints the given board to stdout
void print(int b[NSIZE][NSIZE])
{
std::cout << std::endl;
for (int col = 0; col < NSIZE; ++col)
{
for (int row = 0; row < NSIZE; ++row)
{
if (b[col][row] == 0)
std::cout << ". ";
else
std::cout << b[col][row] << " ";
if (row == 2 || row == 5)
std::cout << "| ";
}
std::cout << std::endl;
if (col == 2 || col == 5)
std::cout << "------+-------+------" << std::endl;
}
std::cout << std::endl;
}
// returns true if the given board has been solved
bool solved(int b[NSIZE][NSIZE])
{
// check column sums
for (int c = 0; c < NSIZE; ++c)
{
int sum = 0;
for (int r = 0; r < NSIZE; ++r)
{
// If one of the fields is zero, no solution has been found.
// This check only needs to be done here, since the column check scans all fields.
if (b[c][r] == 0)
return false;
sum += b[c][r];
}
if (sum != SUM)
return false;
}
// check row sums
for (int r = 0; r < NSIZE; ++r)
{
int sum = 0;
for (int c = 0; c < NSIZE; ++c)
sum += b[c][r];
if (sum != SUM)
return false;
}
// check 3x3 cell sums
for (int cc = 0; cc < CELLSIZE; ++cc)
{
for (int rr = 0; rr < CELLSIZE; ++rr)
{
int sum = 0;
for (int c = cc * CELLSIZE; c < (cc + 1) * CELLSIZE; ++c)
{
for (int r = rr * CELLSIZE; r < (rr + 1) * CELLSIZE; ++r)
sum += b[c][r];
}
if (sum != SUM)
return false;
}
}
// no errors found, the Sudoku puzzle is solved
return true;
}
// check if the given row is missing the number N
int rowMissing(int board[NSIZE][NSIZE], int r, int N)
{
for (int c = 0; c < NSIZE; ++c)
{
if (board[c][r] == N)
return false;
}
return true;
}
// check if the given column is missing the number N
int colMissing(int board[NSIZE][NSIZE], int c, int N)
{
for (int r = 0; r < NSIZE; ++r)
{
if (board[c][r] == N)
return false;
}
return true;
}
// check if the given 3x3 cell is missing the number N
int cellMissing(int board[NSIZE][NSIZE], int c, int r, int N)
{
int cc = (c/CELLSIZE)*CELLSIZE;
int rr = (r/CELLSIZE)*CELLSIZE;
for (int _c = cc; _c < cc + CELLSIZE; ++_c)
{
for (int _r = rr; _r < rr + CELLSIZE; ++_r)
{
if (board[_c][_r] == N)
return false;
}
}
return true;
}
// This function recursively tries to guess next number on the board.
bool guess(int board[NSIZE][NSIZE], int index, int& guessCount)
{
// search for next cell containg 0
for (int i = index; i < NSIZE * NSIZE; ++i)
{
int c = i % NSIZE;
int r = i / NSIZE;
if (board[c][r] == 0)
{
for (int num = 1; num < NSIZE + 1; ++num)
{
if (rowMissing(board,r,num) && colMissing(board,c,num) && cellMissing(board,c,r,num))
{
++guessCount;
board[c][r] = num;
if (guess(board, i + 1, guessCount))
return true;
}
}
board[c][r] = 0; // reset number, all guess failed
return false;
}
}
return solved(board);
}
void solve(int b[NSIZE][NSIZE])
{
std::cout << "-------------------------" << std::endl;
std::cout << "Sudoku solver by guessing" << std::endl;
int guessCount = 0;
if (!guess(b,0,guessCount))
std::cout << "no ";
std::cout << "solution found after " << guessCount << " guesses" << std::endl;
print(b);
}
// example:
int main(int argc, char* argv[])
{
int board[NSIZE][NSIZE] =
{
{0,9,0, 2,0,3, 0,0,0},
{4,6,0, 0,5,0, 0,1,0},
{5,0,8, 1,0,0, 9,0,0},
{9,0,0, 0,0,1, 0,0,0},
{0,0,0, 5,0,2, 0,0,1},
{0,0,0, 8,0,0, 0,0,5},
{0,0,2, 0,0,5, 6,0,9},
{0,5,0, 0,7,0, 0,2,3},
{0,0,0, 4,0,6, 0,7,0}
};
solve(board);
}