Skip to content

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Sudoku Solver
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');
}
}
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));
}
}
}
-------------------------
| 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 |
-------------------------
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;
}
}
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();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.