Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
import java.util.ArrayList;
public class SudokuSolver {
private class Coord {
public int row;
public int col;
public Coord(int row, int col) {
this.row = row;
this.col = col;
}
}
private class Sudoku {
public boolean[][] rowStatus = new boolean[9][9];
public boolean[][] colStatus = new boolean[9][9];
public boolean[][] blockStatus = new boolean[9][9];
public int[][] startInds = new int[9][9]; // start index on each cell
// for nextSuitableNumber
public ArrayList<Coord> emptyCells = new ArrayList<Coord>();
public Sudoku(char[][] board) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] != '.') {
rowStatus[i][board[i][j] - '0' - 1] = true;
colStatus[j][board[i][j] - '0' - 1] = true;
blockStatus[getBlockInd(i, j)][board[i][j] - '0' - 1] = true;
} else {
emptyCells.add(new Coord(i, j));
}
}
}
}
private int getBlockInd(int row, int col) {
if ((row >= 0 && row <= 2) && (col >= 0 && col <= 2))
return 0;
if ((row >= 3 && row <= 5) && (col >= 0 && col <= 2))
return 1;
if ((row >= 6 && row <= 8) && (col >= 0 && col <= 2))
return 2;
if ((row >= 0 && row <= 2) && (col >= 3 && col <= 5))
return 3;
if ((row >= 3 && row <= 5) && (col >= 3 && col <= 5))
return 4;
if ((row >= 6 && row <= 8) && (col >= 3 && col <= 5))
return 5;
if ((row >= 0 && row <= 2) && (col >= 6 && col <= 8))
return 6;
if ((row >= 3 && row <= 5) && (col >= 6 && col <= 8))
return 7;
return 8;
}
public void update(int row, int col, char val, boolean isUndo) {
boolean status = isUndo ? false : true;
rowStatus[row][val - '0' - 1] = status;
colStatus[col][val - '0' - 1] = status;
blockStatus[getBlockInd(row, col)][val - '0' - 1] = status;
}
public char nextSuitableNumber(int row, int col) {
char target = '.';
char tmp;
int startInd = startInds[row][col];
for (int i = startInd; i < 9; i++) {
tmp = (char) ('1' + i);
if (rowStatus[row][i])
continue;
if (colStatus[col][i])
continue;
if (blockStatus[getBlockInd(row, col)][i])
continue;
target = tmp;
startInds[row][col] = i + 1;
break;
}
if (target == '.')
startInds[row][col] = 0;
return target;
}
}
public void solveSudoku(char[][] board) {
Sudoku sd = new Sudoku(board);
solveSudoku(board, sd);
}
private void solveSudoku(char[][] board, Sudoku sd) {
int i = 0;
int numOfEmptyCells = sd.emptyCells.size();
int row = 0;
int col = 0;
while (true) {
row = sd.emptyCells.get(i).row;
col = sd.emptyCells.get(i).col;
char candidate = sd.nextSuitableNumber(row, col);
if (candidate == '.') {
if (isOutOfBound(--i, numOfEmptyCells))
return;
Coord previous = sd.emptyCells.get(i);
row = previous.row;
col = previous.col;
char previousValue = board[row][col];
board[row][col] = '.';
sd.update(row, col, previousValue, true);
} else {
board[row][col] = candidate;
sd.update(row, col, candidate, false);
if (isOutOfBound(++i, numOfEmptyCells))
return;
// Coord next = sd.emptyCells.get(i);
// row = next.row;
// col = next.col;
}
}
}
private boolean isOutOfBound(int i, int range) {
return i >= 0 && i < range ? false : true;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment