I just finished up a program which takes a byte[9][9]
as input and recursively does a DFS to find any solutions (including multiple solutions). I'm pretty happy with it and it works pretty quickly as far as I can tell. I'm mainly looking for advice on the algorithm I used and its efficiency, as well as the way I handled return values, but any advice is appreciated.
The algorithm:
- Generate a
byte[9][9]
with each cell value representing the # of possible values that can be placed in that spot on the sudoku grid. - Check each cell in the possible values grid. If it is 1, then there is only one possible value - enter this into the sudoku grid.
- If a value was changed in 2, repeat 1-2 with the updated possible values grid.
- If the grid is full, it is solved; return it. If the grid has empty cells, but zero possible values, it is invalid; return an empty
byte[1][1]
. Otherwise, continue to 5. - Once there are no more 1's in the possible values grid, find a cell with the least possible values
n
(usually 2 or 3) and createn
copies of the sudoku grid, filling in the cell of each with each of the possible values. Call the same function on each of these grid, and if the return value is not an emptybyte[1][1]
, return it because it is the solution.
It seems very roundabout to have to return a byte[1][1]
but I can't think of a better way to still satisfy the return type.
public byte[][] solve(byte[][] g) {
byte[][] grid = twoDimensionalCopy(g);
byte[][] numPossible = getNumPossible(grid);
// Fills cells where only one value is possible.
// If a new value is added at any point in the loop, repeats the loop until there are no cells with only one possible value.
boolean valueAdded = false;
for (int row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++) {
numPossible = getNumPossible(grid);
if (numPossible[row][col] == 1) {
enterValue(getPossibleValues(row, col, grid).get(0), row,
col, grid);
valueAdded = true;
}
}
// If at the end of the loop and a value was added, repeat.
if (row == 8 && valueAdded) {
row = -1;
valueAdded = false;
}
}
// If the grid is full, then it must be a solution since all values added are first checked to be valid.
if (isFull(grid)) {
return grid;
}
else {
for (int row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++) {
// If there exists an empty cell on the grid with no possible values, return an empty byte[][].
if (cellEmpty(row, col, grid)
&& getPossibleValues(row, col, grid).size() == 0) {
return new byte[1][1];
}
}
}
// If neither of the above cases works, find a cell with the least number of possible values.
int lowestPossible = -1;
int lowestRow = -1;
int lowestCol = -1;
for (int row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++) {
if ((lowestPossible == -1 && cellEmpty(row, col, grid))
|| (numPossible[row][col] != 0 && numPossible[row][col] < lowestPossible)) {
lowestRow = row;
lowestCol = col;
lowestPossible = numPossible[row][col];
}
}
}
ArrayList<Byte> pValues = getPossibleValues(lowestRow, lowestCol, grid);
// For each of the possible values for the cell, enter the value in the grid and call the function again. Add all the results to the ArrayList, then return the ArrayList.
for (byte pValue : pValues) {
byte[][] newGrid = twoDimensionalCopy(grid);
enterValue(pValue, lowestRow, lowestCol, newGrid);
newGrid = solve(newGrid);
if (newGrid[0][0] != 0){
return newGrid;
}
}
}
return new byte[1][1];
}
private byte[][] getNumPossible(byte[][] grid) {
// Returns a byte[][] with cells representing the number of possible values for each cell.
}
private ArrayList<Byte> getPossibleValues(int row, int col, byte[][] grid) {
// Returns an ArrayList with all the possible values for a given cell.
}
private boolean anyHas(int value, int row, int col, byte[][] grid) {
// Returns true if a cell in the same row, column, or section has the same value as the given one.
}