Sudoku is a popular logic game for one player. The objective is to fill numbers 1-9 in a grid of 9x9 squares in such a way that every row, column and group (3x3 subgrid) contains each number exactly once.
Sudoku was published by Howard Garns in 1979 (named as Number place). The puzzle became popular in Japan, where it has been published since 1986 under the name Suuji wa dokushin ni kagiru (single number). In 2005 Sudoku became popular worldwide.
How to solve Sudoku?
Sudoku is usually solved using so called candidates. Candidates are numbers, which can be filled in a given cell. In the beginning every cell has all candidates 1-9, which are one by one eliminated by applying less or more complex mental structures. When there remains only one candidate number, than it is a solution for the given cell.
Basic rules
The most straightforward strategy is just to follow the rules and eliminate duplicates in rows, columns and groups. Although is this approach very simple, it is sufficient for most of easy Sudokus.
(Hidden) Singles
Cells that have only one candidate (which is their solution) are called singles. Hidden single is a candidate, which is unique in a row, column or a group, but is not the only candidate in a cell. Thanks to its uniqueness, the hidden single is a solution to the cell.
Naked pair
If two cells in a group contain two identical candidates, than no other cell may contain any of them. The reason is simple – if some other cell contained also the candidate, than one of the original cell would have no candidates and the solution would be inconsistent. The same logic applies to 3 cells and three candidates, 4 cells and 4 candidates and so on.
Pointing pair, Pointing triples (intersection removal)
Let's assume that one candidate occurs in some row or column of one group more than once (and only in this row/column). Than we can remove it from the intersection of the row/column and other groups, through which this row/column goes.
Box/Line reduction (intersection removal)
If we turn the previous strategy inside out, we get box/line reduction. Suppose that we have a row/column, which has some candidate only in one group. Than we can eliminate this candidate from all other cells of the group.
Generation and machine solving of Sudoku
Generation of Sudoku puzzle must be done at two levels (using different solver). The first level verifies that the initial setting has only one solution. This can be done using a backtracking algorithm. Backtracking is a method of organized trials and errors. At each step the algorithm takes and verifies consistency of the partial solution. If its consistent, the algorithm makes another decision. If its inconsistent, the algorithm reevaluates the last decision made. If all possible decisions at the current were already taken, backtracking algorithm reevaluates the previous decision. Sooner or later the procedure finds a consistent solution (all solutions), or asserts that none exists.
At the second level, the generator must make sure that the puzzle is solvable by using only those strategies, which can be performed by a human. The human-like approach algorithm may be also used to evaluate difficulty of the puzzle – for example based on number of steps needed to solve the Sudoku and number/complexity of strategies used.
Initial setting generation
The only question remaining is how to get the initial setting of the puzzle. There are used mainly two approaches. The first one generates a complete solution of Sudoku and iteratively removes entries, while the Sudoku is still solvable.
On the contrary the second approach randomly creates a Sudoku initial setting with 17 cells filled (17 is the lowest known number of filled squares, which generates a unique solution). Than at every step the generator fills some other cell, while the Sudoku has not a unique solution (and verifies consistency of the puzzle at each step).
Code
/**
* Sudoku solver using backtracking
* @author Pavel Micka
*/
public class SudokuSolver {
/**
* Size of the sudoku, classical Sudoku 9x9
*/
public static final int SUDOKU_SIZE = 9;
/**
* Size of the inner subgrids
*/
public static final int SQUARE_SIZE = 3;
/**
* Empty cell value
*/
public static final int EMPTY = 0;
/**
* Solves the given Sudoku using backtracking (finds all possible solutions)
* @param array innital setting of the puzzle
*/
public static void solveSudoku(int[][] array) {
if (array.length != SUDOKU_SIZE) throw new IllegalArgumentException("Illegal array size");
boolean[][] fixed = new boolean[SUDOKU_SIZE][SUDOKU_SIZE];
for (int i = 0; i < array.length; i++) {
if (array[i].length != SUDOKU_SIZE) throw new IllegalArgumentException("Illegal array size");
for (int j = 0; j < array.length; j++) {
if(array[i][j] != 0) fixed[i][j] = true;
}
}
int x = -1;
int y = 0;
do {
x = x + 1; //shift to the next cell
boolean overflow = x >= SUDOKU_SIZE; //row overflow?
if (overflow) {
x = 0;
y += 1;
}
} while (fixed[y][x]);//while the cell is fixed (part of the initial setting)
for (int i = 1; i <= SUDOKU_SIZE; i++) {
solve(array, fixed, x, y, i);
}
}
/**
* Solves the Sudoku
* @param array array of the solution
* @param fixed array, where true denotes that the value is in the initial setting, false
* that its a member of the partial solution
* @param x x coordinate, where the next decision will be made
* @param y y coordinate, where the next decision will be made
* @param value decision
*/
private static void solve(int[][] array, boolean[][] fixed, int x, int y, int value) {
if (!checkConsistency(array, x, y, value)) return; //the solution is not consistent
array[y][x] = value; //set
do {
x = x + 1; //shift to the next cell
boolean overflow = x >= SUDOKU_SIZE; //row overflow?
if (overflow) {
x = 0;
y += 1;
if (y == SUDOKU_SIZE ) { //column overflow?...solution is complete
printArray(array);
return;
}
}
} while (fixed[y][x]); //while the field is fixed (part of the initial setting)
for (int i = 1; i <= SUDOKU_SIZE; i++) { //backtrack
solve(array, fixed, x, y, i);
}
array[y][x] = EMPTY; //reset the cell (otherwise it would infere with the backtracking algorithm)
}
/**
* Checks, if the partial solution is consistent
* @param array partial solution
* @param x x coordinate, where the decision was made
* @param y y coordinate, where the decision was made
* @param value decision
* @return true - if the partial solution is consistent, false - if it is not consistent
*/
private static boolean checkConsistency(int[][] array, int x, int y, int value) {
//column
for (int i = 0; i < array.length; i++) {
if (i != y && array[i][x] == value) return false;
}
//row
for (int i = 0; i < array[y].length; i++) {
if (i != x && array[y][i] == value) return false;
}
//group
int vertical = y/SQUARE_SIZE; //vertical row index
int horizontal = x/SQUARE_SIZE; //horizontal row index
for (int i = vertical*SQUARE_SIZE; i < vertical*SQUARE_SIZE + SQUARE_SIZE; i++) {
for (int j = horizontal*SQUARE_SIZE; j < horizontal*SQUARE_SIZE + SQUARE_SIZE; j++) {
if (array[i][j] == value) return false;
}
}
return true;
}
/**
* Prints out the array (solution)
* @param array array of the solution
*/
private static void printArray(int[][] array) {
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[i].length; j++) {
System.out.print(array[i][j] + "|");
}
System.out.println("");
}
System.out.println("");
}
}
/**
* Sudoku solver using humanlike strategies
* @author Pavel Micka
*/
public class HumanizedSudokuSolver {
private SudokuField[][] sudoku;
private SudokuStrategy[] strategies;
/**
* Constucts a Sudoku solver
* @param setting initial setting, 0 denotes an empty cell
* @param strategies array of strategies, which will be used
*/
HumanizedSudokuSolver(int[][] setting, SudokuStrategy... strategies) {
this.strategies = strategies;
sudoku = new SudokuField[setting.length][setting.length];
for (int i = 0; i < setting.length; i++) {
for (int j = 0; j < setting[i].length; j++) {
if (setting[i][j] == 0) {
sudoku[i][j] = new SudokuField();
} else {
sudoku[i][j] = new SudokuField(setting[i][j]);
}
}
}
}
/**
* Returns a solution of the given Sudoku
* @return solution
*/
public int[][] solve() {
boolean succ;
do {
succ = false;
for (SudokuStrategy s : strategies) {
succ = s.solve(sudoku);
if (succ) {
break;
}
}
} while (succ);
int[][] solution = new int[sudoku.length][sudoku.length];
for (int i = 0; i < sudoku.length; i++) {
for (int j = 0; j < sudoku.length; j++) {
solution[i][j] = sudoku[i][j].getSolution();
}
}
return solution;
}
/**
* Testing main method
* Programs solves the Sudoku using several simple strategies and
* prints out the solution
* @param args the command line arguments
*/
public static void main(String[] args) {
int[][] setting = { //source: MF DNES 23.8.2010
{0, 0, 4, 0, 3, 6, 9, 2, 7},
{1, 0, 0, 0, 0, 5, 0, 0, 0},
{0, 0, 0, 2, 0, 0, 0, 0, 4},
{0, 0, 5, 0, 0, 0, 0, 6, 0},
{6, 4, 0, 0, 0, 0, 0, 8, 5},
{0, 7, 0, 0, 0, 0, 2, 0, 0},
{5, 0, 0, 0, 0, 1, 0, 0, 0},
{0, 0, 0, 7, 0, 0, 0, 0, 2},
{4, 3, 7, 9, 2, 0, 5, 0, 0}
};
SudokuStrategy[] s = {new OneInARowStrategy(), new OneInAColumnStrategy(), new OneInAGroupStrategy()};
HumanizedSudokuSolver solver = new HumanizedSudokuSolver(setting, s);
int[][] solution = solver.solve();
for (int i = 0; i < solution.length; i++) {
for (int j = 0; j < solution.length; j++) {
System.out.print(solution[i][j] + " ");
}
System.out.println("");
}
}
}
/**
* Interface for a Sudoku strategies
* @author Pavel Micka
*/
interface SudokuStrategy {
/**
* Perform one step of the Sudoku solving
* @param sudoku array of the current state of the puzzle (0 denotes an emptz field)
* @return true if the strategy was able to perform a step, false otherwise
*/
public boolean solve(SudokuField[][] sudoku);
}
/**
* Sudoku strategy: every value must be unique in a row
* @author Pavel Micka
*/
class OneInARowStrategy implements SudokuStrategy {
public boolean solve(SudokuField[][] sudoku) {
for (int i = 0; i < sudoku.length; i++) {
for (int j = 0; j < sudoku[i].length; j++) {
int solution = sudoku[i][j].getSolution();
if (solution != 0) { //if the cell is not already solved
for (int k = 0; k < sudoku[i].length; k++) { //iterate over the row
if (sudoku[i][k].getSolution() == 0) { //if the cell is not already solved
if (sudoku[i][k].hasCandidate(solution)) { //and has the current candidate
sudoku[i][k].removeCandidate(solution); //than we will remove it
System.out.println("OneInARow: Removing candidate " + solution
+ " at coordinates x: " + k + " y: " + i);
return true; //return success
}
}
}
}
}
}
return false;
}
}
/**
* Sudoku strategy: every value must be unique in a column
* @author Pavel Micka
*/
class OneInAColumnStrategy implements SudokuStrategy {
public boolean solve(SudokuField[][] sudoku) {
for (int i = 0; i < sudoku.length; i++) {
for (int j = 0; j < sudoku[i].length; j++) {
int solution = sudoku[j][i].getSolution();
if (solution != 0) { //if the cell is not already solved
for (int k = 0; k < sudoku.length; k++) { //iterate over the column
if (sudoku[k][i].getSolution() == 0) { //if the cell is not already solved
if (sudoku[k][i].hasCandidate(solution)) { //and has the current candidate
sudoku[k][i].removeCandidate(solution); //than we will remove it
System.out.println("OneInAColumn: Removing candidate " + solution
+ " at coordinates x: " + i + " y: " + k);
return true; //return success
}
}
}
}
}
}
return false;
}
}
/**
* Sudoku strategy: every value must be unique in a group
* @author Pavel Micka
*/
class OneInAGroupStrategy implements SudokuStrategy {
public boolean solve(SudokuField[][] sudoku) {
int groupCount = (int) Math.sqrt(sudoku.length); //We assume that the Sudoku setting is a square
for (int i = 0; i < sudoku.length; i++) {
for (int j = 0; j < sudoku[i].length; j++) {
int solution = sudoku[i][j].getSolution();
if (solution != 0) { //if the cell is not already solved
for (int k = i - (i % groupCount); k < i - (i % groupCount) + groupCount; k++) {//rows
for (int l = j - (j % groupCount); l < j - (j % groupCount) + groupCount; l++) {//columns
if (sudoku[k][l].getSolution() == 0) { //if the cell is not already solved
if (sudoku[k][l].hasCandidate(solution)) { //and has the current candidate
sudoku[k][l].removeCandidate(solution);
System.out.println("OneInAGroup: Removing candidate " + solution
+ " at coordinates x: " + l + " y: " + k);
return true;
}
}
}
}
}
}
}
return false;
}
}
/**
* Represents a cell of a Sudoku
* @author Pavel Micka
*/
class SudokuField {
/**
* Set of candidates
*/
private Set<Integer> candidates;
/**
* Creates a cell, candidates are numbers 1-9
*/
public SudokuField() {
this.candidates = new HashSet<Integer>();
for (int i = 1; i <= 9; i++) {
candidates.add(i);
}
}
/**
* Creates a cell with only one candidate (solution)
* @param nr reseni
*/
public SudokuField(int nr) {
this.candidates = new HashSet<Integer>();
candidates.add(nr);
}
/**
* Checks if the number is a candidate for this cell
* @param nr number
* @return true if the number is a candidate, false otherwise
*/
public boolean hasCandidate(int nr) {
return candidates.contains(nr);
}
/**
* Removes the candidate
* @param nr candidate
*/
public void removeCandidate(int nr) {
boolean succ = candidates.remove(nr);
assert succ;
}
/**
* Returns a solution for this cell
* @return solution or 0, if the cell is not solved yet
*/
public int getSolution() {
if (candidates.size() != 1) {
return 0;
} else {
return (Integer) (candidates.toArray()[0]);
}
}
}
/**
* Sudoku solver using backtracking
* @author Pavel Micka
*/
class SudokuSolver {
public:
/**
* Size of the sudoku, classical Sudoku 9x9
*/
static const int SUDOKU_SIZE = 9;
/**
* Size of the inner subgrids
*/
static const int SQUARE_SIZE = 3;
/**
* Empty cell value
*/
static const int EMPTY = 0;
/**
* Solves the given Sudoku using backtracking (finds all possible solutions)
* @param array innital setting of the puzzle
*/
static void solveSudoku(int ** array) {
bool ** fixed = new bool *[SUDOKU_SIZE];
for (int i = 0; i < SUDOKU_SIZE; i++) {
fixed[i] = new bool[SUDOKU_SIZE];
}
for (int i = 0; i < SUDOKU_SIZE; i++) {
for (int j = 0; j < SUDOKU_SIZE; j++) {
if (array[i][j] != 0) fixed[i][j] = true;
else fixed[i][j] = false;
}
}
int x = -1;
int y = 0;
do {
x = x + 1; //shift to the next cell
bool overflow = x >= SUDOKU_SIZE; //row overflow?
if (overflow){
x = 0;
y += 1;
}
} while (fixed[y][x]); //while the cell is fixed (part of the initial setting)
for (int i = 1; i <= SUDOKU_SIZE; i++) {
solve(array, fixed, x, y, i);
}
//deallocate
for (int i = 0; i < SUDOKU_SIZE; i++) delete fixed[i];
delete[] fixed;
}
private:
/**
* Solves the Sudoku
* @param array array of the solution
* @param fixed array, where true denotes that the value is in the initial setting, false
* that its a member of the partial solution
* @param x x coordinate, where the next decision will be made
* @param y y coordinate, where the next decision will be made
* @param value decision
*/
static void solve(int ** array, bool ** fixed, int x, int y, int value) {
if (!checkConsistency(array, x, y, value)) return; //the solution is not consistent
array[y][x] = value; //set
do {
x = x + 1; //shift to the next cell
bool overflow = x >= SUDOKU_SIZE; //row overflow?
if (overflow){
x = 0;
y += 1;
if (y == SUDOKU_SIZE) { //column overflow?...solution is complete
printArray(array);
return;
}
}
} while (fixed[y][x]); //while the field is fixed (part of the initial setting)
for (int i = 1; i <= SUDOKU_SIZE; i++) { //backtrack
solve(array, fixed, x, y, i);
}
array[y][x] = EMPTY; //reset the cell (otherwise it would infere with the backtracking algorithm)
}
/**
* Checks, if the partial solution is consistent
* @param array partial solution
* @param x x coordinate, where the decision was made
* @param y y coordinate, where the decision was made
* @param value decision
* @return true - if the partial solution is consistent, false - if it is not consistent
*/
static bool checkConsistency(int ** array, int x, int y, int value) {
//column
for (int i = 0; i < SUDOKU_SIZE; i++) {
if (i != y && array[i][x] == value) return false;
}
//row
for (int i = 0; i < SUDOKU_SIZE; i++) {
if (i != x && array[y][i] == value) return false;
}
//group
int vertical = y/SQUARE_SIZE; //vertical row index
int horizontal = x/SQUARE_SIZE; //horizontal row index
for (int i = vertical*SQUARE_SIZE; i < vertical*SQUARE_SIZE + 3; i++) {
for (int j = horizontal*SQUARE_SIZE; j < horizontal*SQUARE_SIZE + 3; j++) {
if (array[i][j] == value) return false;
}
}
return true;
}
/**
* Prints out the array (solution)
* @param array array of the solution
*/
static void printArray(int ** array) {
for (int i = 0; i < SUDOKU_SIZE; i++) {
for (int j = 0; j < SUDOKU_SIZE; j++) {
cout << array[i][j] << "|";
}
cout << "\\n";
}
cout << "\\n";
}
};
Sources
- STUART, Andrew. Sudokuwiki.org/ [online]. 2008 [cit. 2010-08-24]. Available at WWW: <http://www.sudokuwiki.org/>.
- JOHNSON, Angus. Angus johnson's homepage [online]. 2005 [cit. 2010-08-24]. SOLVING SUDOKU. Available at WWW: <http://www.angusj.com/sudoku/hints.php>.