Sudoku Solver
The 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.
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.
Here is the code for the Grid.java:
Here's an example of an input file with three puzzles:
Here's the output of the program when execute with the sample input file:
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 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 = new ArrayList<Grid>();
solve(grid, solutions);
printSolutions(grid, solutions);
}
}
// Recursive routine that implements the bifurcation algorithm
private static void solve(Grid grid, List<Grid> solutions) {
// Return if there is already a 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();
}
}
/**
* @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();
}
}
# 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
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 |
-------------------------
Nice Job!
you are a great man
Funny and handy !
good work
very nice
I want a program says if an array is aleady sorted
please help
Thanks