public
Created

Sudoku Solver

  • Download Gist
Board.java
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142
package sudoku;
 
import java.util.Arrays;
 
/**
* This class is a DataStructure to store the board
* It's also offers method to get particular areas of the board and to retrieve/set values
* Visibility is package-friendly as it is part of the "internals" of the Solver
*
* @author vincent
*/
final class Board {
// Constants with package visibility
static final int EMPTY_CELL = 0;
static final int GRID_SIZE = 9;
static final int REGION_SIZE = 3;
static final String ERROR_MSG_SIZE = "Please provide a "+ GRID_SIZE +"x" + GRID_SIZE + " array for Input";
 
private final int[][] board;
private char[] line;
 
/**
* Default Constructor
* @param init a dimension 2 array of integers, empty cells are represented by 0
*/
Board(int[][] init) {
// A check on the size of the input data could be done here, to throw an InvalidInputException
// Also, it is possible to deep copy the input array to ensure isolation/security.
board = init;
}
/**
* Returns the specified row
* @param row row number (starting from 0)
*/
int[] getRow(int row) {
return board[row];
}
 
/**
* Returns the specified column
* @param col column number (starting from 0)
*/
int[] getColumn(int col) {
final int[] columnView = new int[GRID_SIZE];
for(int a = 0; a < GRID_SIZE; a++) {
columnView[a] = board[a][col];
}
return columnView;
}
 
/**
* Return the numbers from an area of the board (classically a 3x3 square)
* @param row row number
* @param col column number
* @return the area that enclose the specified row/col values
*/
int[] getRegion(int row, int col) {
final int[] regionView = new int[GRID_SIZE];
final int rowBase = row - (row % REGION_SIZE);
final int colBase = col - (col % REGION_SIZE);
int counter = 0;
// REGION_SIZE (3) Rows/Columns from rowBase/ColumnBase
for (int r = rowBase; r < REGION_SIZE + rowBase; r++) {
for (int c = colBase ; c < REGION_SIZE + colBase; c++) {
regionView[counter++] = board[r][c];
}
}
return regionView;
}
 
/**
* Getter
*/
int getCell(int row, int col) {
return board[row][col];
}
 
/**
* Setter
*/
void setCell(int row, int col, int val) {
board[row][col] = val;
}
 
/**
* Return a string containing the sudoku with region separators
*/
@Override
public String toString() {
// Exact size of the generated string for the buffer (values + spacers)
final int size = (GRID_SIZE*2+1+((REGION_SIZE+1)*2))*(GRID_SIZE+REGION_SIZE+1);
final String verticalSpace = " |";
// A StringBuilder is absolutely needed here
// use of String concatenation (+) would have really bad performance
final StringBuilder buffer = new StringBuilder(size);
// Row/Column traversal
for (int a=0; a < GRID_SIZE; a++) {
int[] row = board[a];
if (a % REGION_SIZE == 0) {
appendLine(buffer);
}
for (int b=0; b < GRID_SIZE; b++) {
int value = row[b];
if (b % REGION_SIZE == 0) {
buffer.append(verticalSpace);
}
appendValue(buffer, value);
}
buffer.append(verticalSpace);
buffer.append('\n');
}
appendLine(buffer);
return buffer.toString();
}
 
/**
* Appends the value, or a _ if empty
*/
private void appendValue(StringBuilder buffer, int value) {
buffer.append(' ');
if (value != EMPTY_CELL) {
buffer.append(value);
} else {
buffer.append('_');
}
}
/**
* Append a line (separator between region)
*/
private void appendLine(StringBuilder buffer) {
// Only create the line once
// Thread safe because the Sudoku class create one new Board for every toString() method call
if (line == null) {
line = new char[GRID_SIZE*2+((REGION_SIZE+1)*2)];
Arrays.fill(line, '-');
//first char as space
line[0] = ' ';
}
buffer.append(line);
buffer.append('\n');
}
}
Main.java
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
import sudoku.Sudoku;
 
/**
* Main class
* As, it is in another package, it has only the visibility on the Sudoku "API" class
* This design enforce maintainability as the internals of the Solvers are not externally accessible.
*
* Thus, Sudoku internal classes could evolve, without breaking client compatibility.
*/
public class Main {
public static void main(String[] args) {
// Here, input args parsing is possible to enable passing a sudoku as a CLI argument
// It would have involved to parse 81 Integer and to generate a 9x9 array
//Very hard sudoku (lot of 0)
final int[][] sudoku = {
{8,6,0,0,2,0,0,0,0},
{0,0,0,7,0,0,0,5,9},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,6,0,8,0,0},
{0,4,0,0,0,0,0,0,0},
{0,0,5,3,0,0,0,0,7},
{0,0,0,0,0,0,0,0,0},
{0,2,0,0,0,0,6,0,0},
{0,0,7,5,0,9,0,0,0}
};
// Print input sudoku
System.out.println(Sudoku.asString(sudoku));
// If sudoku sucessfuly solved
if (Sudoku.solve(sudoku)) {
//Print solved sudoku
System.out.println(Sudoku.asString(sudoku));
}
}
}
Solver.java
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82
package sudoku;
import static sudoku.Board.EMPTY_CELL;
import static sudoku.Board.GRID_SIZE;
 
/**
* This class implements the solving algorithm, It is separated from
* the board logic
*
* The visibility of this class is package, as it is not the external API
* @author vincent
*
*/
class Solver {
 
private final Board board;
 
/**
* Constructor
* @param input a 9x9 array representing a sudoku, empty cells are 0
*/
Solver(int[][] input) {
this.board = new Board(input);
}
/**
* Method to solve the sudoku "in-place" (without creating/copying with a new array)
* @return true if the sudoku is successfully solved
*/
boolean solve() {
return solve(0,0);
}
 
/**
* Returns the board object, useful for pretty-printing of the sudoku
*/
Board getBoard() {
return board;
}
/**
* Backtracking recursive algorithm to solve sudoku
*/
private boolean solve(int row, int col) {
if (row == GRID_SIZE) {
row = 0;
if (++col == GRID_SIZE) {
return true;
}
}
if (board.getCell(row, col) != EMPTY_CELL) {
return solve(row+1,col);
}
// For all possible values
for(int val = 1; val <= GRID_SIZE; val++) {
if (isMoveOK(row, col, val)) {
board.setCell(row, col, val);
if (solve(row+1, col)) {
return true;
}
}
}
// Reset the cell to EMPTY to do recursive backtrack and try again
board.setCell(row, col, EMPTY_CELL);
return false;
}
 
 
private boolean isMoveOK(int row, int col, int val) {
return ! ( arrayContains(board.getRow(row), val)
|| arrayContains(board.getColumn(col), val)
|| arrayContains(board.getRegion(row, col), val));
}
 
private boolean arrayContains(int[] array, int val) {
for (int arrayVal : array) {
if (arrayVal == val) {
// return true and stop the iteration
return true;
}
}
return false;
}
}
Sudoku.java
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
package sudoku;
 
/**
* Sudoku External API (only public class of the package)
*/
public class Sudoku
{
/**
* Solves "in-place" the sudoku in the provided array
* this method signature is inspired from the JDK method Arrays.sort(int[] array)
* @param sudoku a 9x9 array representing a sudoku, empty cells are 0
* @return true if the sudoku has been sucessfully solved
*/
public static boolean solve(int[][] sudoku) {
return new Solver(sudoku).solve();
}
/**
* Returns the sudoku board as a string
* @param sudoku a 9x9 array representing a sudoku, empty cells are 0
* @return a string representation of the sudoku
*/
public static String asString(int[][] sudoku) {
return new Board(sudoku).toString();
}
}
output
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
-------------------------
| 8 6 _ | _ 2 _ | _ _ _ |
| _ _ _ | 7 _ _ | _ 5 9 |
| _ _ _ | _ _ _ | _ _ _ |
-------------------------
| _ _ _ | _ 6 _ | 8 _ _ |
| _ 4 _ | _ _ _ | _ _ _ |
| _ _ 5 | 3 _ _ | _ _ 7 |
-------------------------
| _ _ _ | _ _ _ | _ _ _ |
| _ 2 _ | _ _ _ | 6 _ _ |
| _ _ 7 | 5 _ 9 | _ _ _ |
-------------------------
 
-------------------------
| 8 6 3 | 9 2 5 | 7 4 1 |
| 4 1 2 | 7 8 6 | 3 5 9 |
| 7 5 9 | 4 1 3 | 2 8 6 |
-------------------------
| 9 7 1 | 2 6 4 | 8 3 5 |
| 3 4 6 | 8 5 7 | 9 1 2 |
| 2 8 5 | 3 9 1 | 4 6 7 |
-------------------------
| 1 9 8 | 6 3 2 | 5 7 4 |
| 5 2 4 | 1 7 8 | 6 9 3 |
| 6 3 7 | 5 4 9 | 1 2 8 |
-------------------------

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.