|
The Java Developers Almanac 1.4 |
|
e1089. Sudoku SolverThe Sudoku puzzle consists of a grid of 9x9 cells. This 81-cell grid is further subdivided into nine subgrids of 3x3 cells. A few of the cells are filled with a single digit between 1 and 9 (the givens). To solve the puzzle, the empty cells must be filled in such a way that every 9-cell row, column, and subgrid contains each of the digits between 1 and 9.Most published Sudoku puzzles can be solved with deductive reasoning. For example, if the digit 9 appears in the first 2 rows and subgrids, then the digit 9 must appear in the 3rd row in the top-right subgrid. If in this subgrid, there is only one empty cell, then the empty cell must contain 9. This solver does not employ deductive reasoning. Instead, it employs a technique called bifurcation which systematically tries every possible digit in every empty cell until the solution is achieved. Here's a summary of the algorithm. 1. Find an empty cell
1a. If there are no more empty cells, the puzzle is solved
2. Fill the empty cell with the lowest possible valid number
2a. If no valid number exists, backtrack to the previous empty cell
and try the next higher valid number in that cell
3. Go to step 1
This program consists of two classes - the
SudokuSolver class which is the main class and the
Grid class for holding the values of a grid while it is being solved.
/**
* This program is executed in the following way:
* java SudokuSolver <input-file>
* For details of the input-file format, see the Grid.java class.
*
* @author Patrick Chan
* @version 1, 12/31/05
* @see Grid
*/
import java.io.*;
import java.util.*;
public class SudokuSolver {
public static void main(String[] args) throws Exception {
// Open the file containing the givens
File file = new File(args[0]);
FileReader rd = new FileReader(args[0]);
// Process each grid in the file
while (true) {
Grid grid = Grid.create(rd);
if (grid == null) {
// No more grids
break;
}
// Find a solution
List<Grid> solutions = solve(grid);
printSolutions(grid, solutions);
}
}
// Recursive routine that
private static List<Grid> solve(Grid grid) {
List<Grid> solutions = new ArrayList<Grid>();
solve(grid, solutions);
return solutions;
}
private static void solve(Grid grid, List<Grid> solutions) {
// Return if there is already more than two solution
if (solutions.size() >= 2) {
return;
}
// Find first empty cell
int loc = grid.findEmptyCell();
// If no empty cells are found, a solution is found
if (loc < 0) {
solutions.add(grid.clone());
return;
}
// Try each of the 9 digits in this empty cell
for (int n=1; n<10; n++) {
if (grid.set(loc, n)) {
// With this cell set, work on the next cell
solve(grid, solutions);
// Clear the cell so that it can be filled with another digit
grid.clear(loc);
}
}
}
private static void printSolutions(Grid grid, List<Grid> solutions) {
// Print the grid with the givens
System.out.println("Original");
System.out.println(grid);
// Print the solution
if (solutions.size() == 0) {
System.out.println("Unsolveable");
} else if (solutions.size() == 1) {
System.out.println("Solved");
} else {
System.out.println("At least two solutions");
}
// Print the solution(s)
for (int i=0; i<solutions.size(); i++) {
System.out.println(solutions.get(i));
}
System.out.println();
System.out.println();
}
}
Here is the code for the Grid.java:
/**
* @author Patrick Chan
* @version 1, 12/31/05
* @see SudokuSolver
*/
import java.io.*;
import java.util.*;
/**
* A Grid object holds the currently known values of the Sudoku puzzle.
* The grid consists of 9x9 cells that hold integer values from 0 to 9.
* A value of 0 indicates that the cell is empty.
*
* Each of the 81 cells has a location which is used to identify a
* specific cell. There are 81 locations, labelled location 0 to location 80.
* Cell locations are ordered from left-to-right and top-down.
* For example, location 0 refers to the top-leftmost cell.
* Location 8 refers to the top-righttmost cell.
* Location 71 refers to the bottom-leftmost cell.
* Location 80 refers to the bottom-rightmost cell.
*
* The grid consists of 9 columns, labelled column 0 to column 8.
* The grid consists of 9 rows, labelled row 0 to row 8.
*
* The grid consists of 9 subgrids, labelled subgrid 0 to subgrid 8.
* Each subgrid contains a subgrid of 3x3 cells.
* Subgrid 0 contains cells - 0, 1, 2, 9, 10, 11, 18, 19, 20.
* Subgrid 8 contains cells - 60, 61, 62, 69, 70, 71, 78, 79, 80
*/
public class Grid implements Cloneable {
// Array that contains values of all 81 cells in the grid.
int[] cells = new int[81];
// A set of bit-vectors that represent the known values for each column.
// Specifically, if column c contains the digits d1 and d2,
// colsSet[c] = 2^(d1-1)|2^(d2-1)
// For example, if column 0 contains the values 1 and 4, colsSet[0] = 9.
// The information in this variable is redundant with the information
// in the cells variable. The purpose of this variable is to reduce
// the cost of determining whether a particular digit can be set in
// a particular cell.
int[] colsSet = new int[9];
// This purpose and behavior of this variable is similar to colsSet.
int[] rowsSet = new int[9];
// This purpose and behavior of this variable is similar to colsSet.
int[] subgridSet = new int[9];
/**
* This method returns a grid of givens and empty cells ready to be solved.
* The cells containing givens have values between 1 and 9.
* Empty cells have the value 0.
*
* Characters are read one at a time from the input stream and placed
* into the grid in left-to-right and top-down order.
* - The characters 0 or . indicates an empty cell.
* - The characters 1 to 9 indicates a given.
* - The character # is used for comments; subsequent characters are
* ignored until a newline is encountered.
* - All other characters are simply ignored.
*
* @param rd Reader containing the givens
* @return null if there are not enough characters in 'rd' to form a grid.
*/
public static Grid create(Reader rd) throws Exception {
Grid grid = new Grid();
// Read until all 81 cells are filled
for (int loc=0; loc<grid.cells.length; ) {
// Read a character
int ch = rd.read();
// -1 is returned if the input stream has no more characters
if (ch < 0) {
// No more characters so return null
return null;
}
if (ch == '#') {
// Skip to end-of-line
while (ch >= 0 && ch != '\n' && ch != '\r') {
ch = rd.read();
}
} else if (ch >= '1' && ch <= '9') {
// A given
grid.set(loc, ch-'0');
loc++;
} else if (ch == '.' || ch == '0') {
// Empty cell
loc++;
}
}
return grid;
}
/*
* Finds an empty cell.
* @return the location of an empty cell or -1 if there are no empty cells.
* Values must be in the range [-1, 80].
*/
public int findEmptyCell() {
for (int i=0; i<cells.length; i++) {
if (cells[i] == 0) {
return i;
}
}
return -1;
}
/*
* Sets a number in a cell. This method checks to see if
* 1. the cell is empty
* 2. the cell is allowed to contain the specified number. E.g. if
* the number is 5 but the row already has a 5, the cell will
* not be set and false is returned.
* @param loc the location of the target cell.
* Values must be in the range [0, 80].
* @param num the number to set in the cell.
* Values must be in the range [1, 9].
* @return true if the set was successful.
*/
public boolean set(int loc, int num) {
// Compute row and column
int r = loc/9;
int c = loc%9;
int blockLoc = (r/3)*3+c/3;
boolean canSet = cells[loc] == 0
&& (colsSet[c] & (1<<num)) == 0
&& (rowsSet[r] & (1<<num)) == 0
&& (subgridSet[blockLoc] & (1<<num)) == 0;
if (!canSet) {
return false;
}
cells[loc] = num;
colsSet[c] |= (1<<num);
rowsSet[r] |= (1<<num);
subgridSet[blockLoc] |= (1<<num);
return true;
}
/*
* Removes the number in a cell.
* @param loc the location of the target cell.
* Values must be in the range [0, 80].
*/
public void clear(int loc) {
// Compute row and column
int r = loc/9;
int c = loc%9;
int blockLoc = (r/3)*3+c/3;
int num = cells[loc];
cells[loc] = 0;
colsSet[c] ^= (1<<num);
rowsSet[r] ^= (1<<num);
subgridSet[blockLoc] ^= (1<<num);
}
/**
* Returns a copy of this grid. Any modifications to the returned
* grid will not affect this grid.
*
* @return a non-null deep copy of this grid.
*/
public Grid clone() {
Grid grid = new Grid();
grid.cells = cells.clone();
grid.colsSet = colsSet.clone();
grid.rowsSet = rowsSet.clone();
grid.subgridSet = subgridSet.clone();
return grid;
}
/**
* Returns a string representing the current contents of the grid.
* Used for debugging purposes.
*
* @return a non-null string representing the current contents of the grid.
*/
public String toString() {
StringBuffer buf = new StringBuffer();
for (int r=0; r<9; r++) {
if (r%3 == 0) {
buf.append("-------------------------\n");
}
for (int c=0; c<9; c++) {
if (c%3 == 0) {
buf.append("| ");
}
int num = cells[r*9+c];
if (num == 0) {
buf.append(". ");
} else {
buf.append(num+" ");
}
}
buf.append("|\n");
}
buf.append("-------------------------");
return buf.toString();
}
}
Here's an example of an input file:
# This puzzle was obtained from sudoku.com
.6.|1.4|.5.
..8|3.5|6..
2..|...|..1
---+---+---
8..|4.7|..6
..6|...|3..
7..|9.1|..4
---+---+---
5..|...|..2
..7|2.6|9..
.4.|5.8|.7.
-----------
# http://www.sudoku.org.uk/bifurcation.htm
1 0 0 9 0 7 0 0 3
0 8 0 0 0 0 0 7 0
0 0 9 0 0 0 6 0 0
0 0 7 2 0 9 4 0 0
4 1 0 0 0 0 0 9 5
0 0 8 5 0 4 3 0 0
0 0 3 0 0 0 7 0 0
0 5 0 0 0 0 0 4 0
2 0 0 8 0 6 0 0 9
# This puzzle has multiple solutions
1 2 3 4 5 6 7 8 9
0 6 0 0 0 0 0 3 0
0 7 0 0 0 0 0 4 0
7 8 9 1 2 3 4 5 6
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
4 5 6 7 8 9 1 2 3
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
Here's the output of the program when execute with the sample input file:
Original
-------------------------
| . 6 . | 1 . 4 | . 5 . |
| . . 8 | 3 . 5 | 6 . . |
| 2 . . | . . . | . . 1 |
-------------------------
| 8 . . | 4 . 7 | . . 6 |
| . . 6 | . . . | 3 . . |
| 7 . . | 9 . 1 | . . 4 |
-------------------------
| 5 . . | . . . | . . 2 |
| . . 7 | 2 . 6 | 9 . . |
| . 4 . | 5 . 8 | . 7 . |
-------------------------
Solved
-------------------------
| 9 6 3 | 1 7 4 | 2 5 8 |
| 1 7 8 | 3 2 5 | 6 4 9 |
| 2 5 4 | 6 8 9 | 7 3 1 |
-------------------------
| 8 2 1 | 4 3 7 | 5 9 6 |
| 4 9 6 | 8 5 2 | 3 1 7 |
| 7 3 5 | 9 6 1 | 8 2 4 |
-------------------------
| 5 8 9 | 7 1 3 | 4 6 2 |
| 3 1 7 | 2 4 6 | 9 8 5 |
| 6 4 2 | 5 9 8 | 1 7 3 |
-------------------------
Original
-------------------------
| 1 . . | 9 . 7 | . . 3 |
| . 8 . | . . . | . 7 . |
| . . 9 | . . . | 6 . . |
-------------------------
| . . 7 | 2 . 9 | 4 . . |
| 4 1 . | . . . | . 9 5 |
| . . 8 | 5 . 4 | 3 . . |
-------------------------
| . . 3 | . . . | 7 . . |
| . 5 . | . . . | . 4 . |
| 2 . . | 8 . 6 | . . 9 |
-------------------------
Solved
-------------------------
| 1 6 4 | 9 5 7 | 2 8 3 |
| 3 8 5 | 6 2 1 | 9 7 4 |
| 7 2 9 | 4 3 8 | 6 5 1 |
-------------------------
| 5 3 7 | 2 8 9 | 4 1 6 |
| 4 1 2 | 7 6 3 | 8 9 5 |
| 6 9 8 | 5 1 4 | 3 2 7 |
-------------------------
| 8 4 3 | 1 9 5 | 7 6 2 |
| 9 5 6 | 3 7 2 | 1 4 8 |
| 2 7 1 | 8 4 6 | 5 3 9 |
-------------------------
Original
-------------------------
| 1 2 3 | 4 5 6 | 7 8 9 |
| . 6 . | . . . | . 3 . |
| . 7 . | . . . | . 4 . |
-------------------------
| 7 8 9 | 1 2 3 | 4 5 6 |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
-------------------------
| 4 5 6 | 7 8 9 | 1 2 3 |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
-------------------------
At least two solutions
-------------------------
| 1 2 3 | 4 5 6 | 7 8 9 |
| 5 6 4 | 8 9 7 | 2 3 1 |
| 9 7 8 | 2 3 1 | 6 4 5 |
-------------------------
| 7 8 9 | 1 2 3 | 4 5 6 |
| 2 3 1 | 5 6 4 | 8 9 7 |
| 6 4 5 | 9 7 8 | 3 1 2 |
-------------------------
| 4 5 6 | 7 8 9 | 1 2 3 |
| 3 1 2 | 6 4 5 | 9 7 8 |
| 8 9 7 | 3 1 2 | 5 6 4 |
-------------------------
-------------------------
| 1 2 3 | 4 5 6 | 7 8 9 |
| 5 6 4 | 8 9 7 | 2 3 1 |
| 9 7 8 | 2 3 1 | 6 4 5 |
-------------------------
| 7 8 9 | 1 2 3 | 4 5 6 |
| 2 3 1 | 5 6 4 | 8 9 7 |
| 6 4 5 | 9 7 8 | 3 1 2 |
-------------------------
| 4 5 6 | 7 8 9 | 1 2 3 |
| 8 9 7 | 3 1 2 | 5 6 4 |
| 3 1 2 | 6 4 5 | 9 7 8 |
-------------------------
© 2002 Addison-Wesley. |