I was compelled to look into a Sudoku Solver in Java using the principles I have learned in a course, namely I wanted to make something that included backtracking and forward checking.
Has anybody else managed to produce a Sudoku solver that uses the forward checking algorithm that is more efficient than the backtracking on its own?
I have produced this, and found that my code must be very inefficient as it's a lot slower than just backtracking, even on complex problems.
Any advice on how I should implement the forward checking algorithm would be nice. Initially I had HashMaps with the cell number as a Key and an ArrayList as the domain. I then considered that this is wildly inefficient and changed the code to a String array which used the cell number as an index and then put a string in it containing the domain.
This was a heck of a lot more efficient, but is still a lot worse than just backtracking.
package sudokuai;
import java.util.ArrayList;
import java.util.HashMap;
/**
* @author Nik Bradley $date $time
*/
/**
* Concrete Sudoku_AI algorithm implementation using Backtracking With Forward Checking
*/
class Sudoku_AI_Backtracking_ForwardChecking implements Sudoku_AI {
private static final String NAME = "Backtracking with Forward Checking";
private static final int GRIDSIZE_ROW = 9;
private static final int GRIDSIZE_COLUMN = 9;
private static final int BOXSIZE = 3;
private Integer[][] solution = new Integer[GRIDSIZE_ROW][GRIDSIZE_COLUMN];
private String[] backupDomains,domains = new String[GRIDSIZE_ROW*GRIDSIZE_COLUMN+1];
//private HashMap domains = new HashMap(81);
//private HashMap backupDomains;
private boolean emptyDomainFlag;
public Sudoku_AI_Backtracking_ForwardChecking() {
}
public void initDomains() {
for (int i = 0; i < GRIDSIZE_ROW; i++) {
for (int j = 0; j < GRIDSIZE_COLUMN; j++) {
//creates 81 domains with the values 1-9 in them
int cell = (i * 9) + 1 + j;
domains[cell]="123456789";
}
}
}
/**
* Largely inefficient, looks through every cell with data assigned and
* checks if there are too many assignments of the same value in each row
* column and box for that specific cell.
*/
@Override
public boolean isSolvable(Integer[][] currentBoard) {
Integer[][] board = new Integer[GRIDSIZE_ROW][GRIDSIZE_COLUMN];
for (int i = 0; i < GRIDSIZE_ROW; i++) {
System.arraycopy(currentBoard[i], 0, board[i], 0, GRIDSIZE_COLUMN);
}
/* Finds the number of cells that have data on the board */
int numberOfCells = getCellCount(board);
for (int i = 0; i < numberOfCells; i++) {
int[] cell = getNextCell(board);
int[] counts = countUsage(board[cell[0]][cell[1]], cell, board);
if (counts[0] + counts[1] + counts[2] == 3) {
board[cell[0]][cell[1]] = null;
} else {
return false;
}
}
return true;
}
/**
* Counts the amount of cells with data in them on the board.
*/
private int getCellCount(Integer[][] board) {
int count = 0;
for (int i = 0; i < GRIDSIZE_ROW; i++) {
for (int j = 0; j < GRIDSIZE_COLUMN; j++) {
if (board[i][j] != null) {
count++;
}
}
}
return count;
}
/**
* Gets the next cell with data in it on the board
*/
private int[] getNextCell(Integer[][] board) {
int[] cell = new int[2];
all:
for (int i = 0; i < GRIDSIZE_ROW; i++) {
for (int j = 0; j < GRIDSIZE_COLUMN; j++) {
if (board[i][j] != null) {
cell[0] = i;
cell[1] = j;
break all; /* used to break out of both loops when a cell is found */
}
}
}
return cell;
}
/**
* Created for debugging, not used.
*
* Would print out a list of the domains, then do a first round of forward
* checking and then reprint the domains.
*/
private void doInitialDomains() {
System.out.println(domains);
//INITIAL FORWARD CHECK
initial_ForwardCheck();
System.out.println(domains);
}
/**
* This method kicks off the solver AI, it does an initial forward check
* which checks all cells on the board and reduces their domains.
*
* It then starts the solve method and if it gets a success it returns the
* solution to the calling method. If it fails to find a solution it creates
* a new grid with null values and returns it
*/
@Override
public Integer[][] getSolution() {
emptyDomainFlag = false;
initDomains();
//INITIAL FORWARD CHECK
initial_ForwardCheck();
if (solveSudoku()) {
//domains.clear();
return solution;
} else {
return new Integer[GRIDSIZE_ROW][GRIDSIZE_COLUMN];
}
}
/**
* The solve algorithm performs a recursive search through values in the
* domains and attempts to assign them to a cell starting from the upper
* left cell and proceeds row by row
*/
private boolean solveSudoku() {
/* Finds the next empty cell */
int[] nextCell = findNextCell();
/* checks if the cell is not empty, if so we have finished */
if (solution[nextCell[0]][nextCell[1]] != null) {
return true;
}
/**
* Converts the coords of the cell into a number between 1-81
* representing the cell then it uses that to get the ArrayList of
* domains from a HashMap, key = int of cell (1-81)
*/
int cell = (nextCell[0] * 9) + 1 + nextCell[1];
// for (int i=0;i<domains.size();i++){
// domainSave.put(i+1, domains.get(i));
// }
//domainSave.putAll(domains);
String mainDomain = domains[cell];
String domain = mainDomain;
/**
* Loops through all available domains in the ArrayList and attempts to
* use them calls isSafe to ensure that the value can be used in the row
* / column / box without clashing with constraints.
*
* If it can be used within constraints, assign it and then empty the
* relevant domains as long as the domains all have possible values,
* call this method to solve the next cell if not remove the value and
* start again.
*
* No remaining options = backtrack
*/
for (int i=0;i<domain.length();i++){
int value = Integer.valueOf(domain.substring(i, i+1));
if (isSafe((Integer) value, nextCell, solution)) {
String[] domainSave = domains.clone();
//domainSave = (HashMap) domains.clone();
solution[nextCell[0]][nextCell[1]] = value;
emptyDomains(nextCell);
if (!emptyDomainFlag) {
if (solveSudoku()) {
return true;
}
}
solution[nextCell[0]][nextCell[1]] = null;
domains = domainSave;
emptyDomainFlag = false;
}
}
return false; // Triggers backtracking
}
/**
* deepCopy allows us to use the HashMap class to alter domains.
*
* @param original the original HashMap to be copied
* @returns a duplicate NEW HashMap of the original.
*/
public static HashMap deepCopy(HashMap original){
HashMap copy = new HashMap();
for (Object ob : original.entrySet()){
HashMap.Entry entry = (HashMap.Entry) ob;
copy.put(entry.getKey(),new ArrayList((ArrayList) entry.getValue()));
}
return copy;
}
/**
* Empties the relevant domains for the cell just updated.
*
* It first creates a backup of the domains and then empties them all while
* there is no flag set that there is an empty domain.
*
* Once done if there is an empty domain it clears the domains and rolls
* them back again
*/
public void emptyDomains(int[] cell) {
fcRow(cell);
if (!emptyDomainFlag) {
fcCol(cell);
}
if (!emptyDomainFlag) {
fcBox(cell);
}
}
/**
* Finds the next empty cell
*/
private int[] findNextCell() {
int[] cell = new int[2];
all:
for (int i = 0; i < GRIDSIZE_ROW; i++) {
for (int j = 0; j < GRIDSIZE_COLUMN; j++) {
if (solution[i][j] == null) {
cell[0] = i;
cell[1] = j;
break all;
}
}
}
return cell;
}
/**
* counts the amount of occurrences of data within rows / columns / boxes
* and returns the numbers in an array.
*/
private int[] countUsage(int value, int[] cell, Integer[][] board) {
int countRow = 0;
int countCol = 0;
int countBox = 0;
for (int i = 0; i < GRIDSIZE_COLUMN; i++) {
if (board[cell[0]][i] == null) {
} else if (board[cell[0]][i] == value) {
countRow++;
}
}
for (int i = 0; i < GRIDSIZE_ROW; i++) {
if (board[i][cell[1]] == null) {
} else if (board[i][cell[1]] == value) {
countCol++;
}
}
/* Figures out the start of the current 3x3 box */
int boxRow = cell[0] - (cell[0] % 3);
int boxCol = cell[1] - (cell[1] % 3);
for (int i = 0; i < BOXSIZE; i++) {
for (int j = 0; j < BOXSIZE; j++) {
if (board[i + boxRow][j + boxCol] == null) {
} else if (board[i + boxRow][j + boxCol] == value) {
countBox++;
}
}
}
int[] counts = {countRow, countCol, countBox};
return counts;
}
/**
* Checks if a value is used in the row already, returns false if it is.
*/
private boolean usedInRow(int value, int row, Integer[][] board) {
boolean safe = true;
for (int i = 0; i < GRIDSIZE_COLUMN; i++) {
if (board[row][i] == null) {
} else if (board[row][i] == value) {
safe = false;
break;
}
}
return safe;
}
/**
* Checks if a value is used in the column already, returns false if it is.
*/
private boolean usedInColumn(int value, int column, Integer[][] board) {
boolean safe = true;
for (int i = 0; i < GRIDSIZE_ROW; i++) {
if (board[i][column] == null) {
} else if (board[i][column] == value) {
safe = false;
break;
}
}
return safe;
}
/**
* Checks if a value is used in the box already, returns false if it is.
*/
private boolean usedInBox(int value, int[] cell, Integer[][] board) {
boolean safe = true;
/**
* boxRow is the starting row of the current box, determined by the
* cells x coord - the mod by 3 boxCol is the starting column of the
* current box, determined by the cells y coord - the mod by 3
*/
int boxRow = cell[0] - (cell[0] % 3);
int boxCol = cell[1] - (cell[1] % 3);
//* loop through the box and check if any of the values match the selected one */
for (int i = 0; i < BOXSIZE; i++) {
for (int j = 0; j < BOXSIZE; j++) {
if (board[i + boxRow][j + boxCol] == null) {
} else if (board[i + boxRow][j + boxCol] == value) {
safe = false;
break;
}
}
}
return safe;
}
/**
* Calls each of the methods to check if a value is already in either row /
* column / box and if it is return false.
*/
private boolean isSafe(int value, int[] cell, Integer[][] board) {
//Check if a number has already been used in the column or row or box
return usedInRow(value, cell[0], board) && usedInColumn(value, cell[1], board) && usedInBox(value, cell, board);
}
/**
* Performs the initial forward check once a puzzle has been sent to the
* solver
*/
public void initial_ForwardCheck() {
setupInitialDomains();
fcAllRow();
fcAllCol();
fcAllBox();
}
public static String stripChars(String input, String strip) {
StringBuilder result = new StringBuilder();
for (char c : input.toCharArray()) {
if (strip.indexOf(c) == -1) {
result.append(c);
}
}
return result.toString();
}
/**
* Finds out if the cell has a value if so remove all possible domain
* values.
*
* Once done it adds the value of the cell back to the domain
*/
private void setupInitialDomains() {
for (int i = 0; i < GRIDSIZE_ROW; i++) {
//Get all the values in the row
for (int j = 0; j < GRIDSIZE_COLUMN; j++) {
if (solution[i][j] != null) {
int cell = (i * 9) + 1 + j;
domains[cell] = solution[i][j].toString();
}
}
}
}
/**
* Remove the values from all of the domains in the row
*/
public void removeRowDomainValues(int row, String initialValues) {
String domain;
for (int j = 0; j < GRIDSIZE_COLUMN; j++) {
/* convert I,J coord into numerical value of 81 to find the domain */
int cell = (row * 9) + 1 + j;
domain = domains[cell];
domain = stripChars(domain,initialValues);
domains[cell] = domain;
if (solution[row][j] != null){
domains[cell] = (solution[row][j].toString());
}
/* if a domain shrinks to nothing we have an invalid solution, turn back now! */
if (domains[cell].length() < 1) {
//System.out.println("Empty Domain --->"+cell+" Domain:"+domain);
emptyDomainFlag = true;
break;
}
}
}
/**
* Remove the values from all of the domains in the column
*/
public void removeColDomainValues(int col, String initialValues) {
String domain;
for (int j = 0; j < GRIDSIZE_ROW; j++) {
/* convert I,J coord into numerical value of 81 to find the domain */
int cell = (j * 9) + 1 + col;
domain = domains[cell];
domain = stripChars(domain,initialValues);
domains[cell] = domain;
if (solution[j][col] != null){
domains[cell] = (solution[j][col].toString());
}
/* if a domain shrinks to nothing we have an invalid solution, turn back now! */
if (domains[cell].length() < 1) {
//System.out.println("Empty Domain --->"+cell+" Domain:"+domain);
emptyDomainFlag = true;
break;
}
}
}
private void removeBoxDomainValues(int boxRow, int boxCol, String initialValues) {
String domain;
escape:
for (int cellRow = boxRow; cellRow < boxRow+BOXSIZE; cellRow++) {
for (int cellCol = boxCol; cellCol < boxCol+BOXSIZE; cellCol++) {
/* convert coords into numerical value of 81 to find the domain */
int cell = (cellRow * 9) + 1 + cellCol;
domain = domains[cell];
domain = stripChars(domain,initialValues);
domains[cell] = domain;
if (solution[cellRow][cellCol] != null){
domains[cell] = (solution[cellRow][cellCol].toString());
}
/* if a domain shrinks to nothing we have an invalid solution, turn back now! */
if (domains[cell].length() < 1) {
//System.out.println("Empty Domain --->"+cell+" Domain:"+domain);
emptyDomainFlag = true;
break escape; //breaks from all loops
}
}
}
}
/**
* Forward Checks every row in the puzzle
*/
private void fcAllRow() {
for (int i = 0; i < GRIDSIZE_ROW; i++) {
String initialValues = "";
/* Get all the values in the row */
for (int j = 0; j < GRIDSIZE_COLUMN; j++) {
if (solution[i][j] != null) {
initialValues = initialValues+solution[i][j].toString();
}
}
/* If there are values that need to be removed from domains remove them */
if (initialValues.length() > 0) {
removeRowDomainValues(i, initialValues);
}
/* if we have created an empty domain stop doing forward checking */
if (emptyDomainFlag) {
break;
}
}
}
/**
* Forward Checks every column in the puzzle
*/
private void fcAllCol() {
for (int i = 0; i < GRIDSIZE_COLUMN; i++) {
String initialValues = "";
/* Get all the values in the column */
for (int j = 0; j < GRIDSIZE_ROW; j++) {
if (solution[j][i] != null) {
initialValues = initialValues+solution[j][i].toString();
}
}
/* If there are values that need to be removed from domains remove them */
if (initialValues.length() > 0) {
removeColDomainValues(i, initialValues);
}
/* if we have created an empty domain stop doing forward checking */
if (emptyDomainFlag) {
break;
}
}
}
/**
* Forward Checks every box in the puzzle
*/
private void fcAllBox() {
int cellRow, cellCol;
escape:
/**
* Loop through all the boxes Finds the top left square of each 3x3 box.
*/
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
String initialValues = "";
/* loops through each cell in a 3x3 box */
for (int x = 0; x < BOXSIZE; x++) {
for (int y = 0; y < BOXSIZE; y++) {
cellRow = (3 * i) + x;
cellCol = (3 * j) + y;
if (solution[cellRow][cellCol] != null) {
initialValues = initialValues+solution[cellRow][cellCol].toString();
}
}
}
/* If there are values that need to be removed from domains remove them */
if (initialValues.length() > 0) {
removeBoxDomainValues(i*3, j*3, initialValues);
}
/* if we have created an empty domain stop doing forward checking */
if (emptyDomainFlag) {
break escape; //Break all loops
}
}
}
}
/**
* Forward check just 1 row, determined by the @param currentCell.
*/
private void fcRow(int[] currentCell) {
String initialValues = "";
if (solution[currentCell[0]][currentCell[1]] != null) {
initialValues = initialValues+solution[currentCell[0]][currentCell[1]].toString();
}
/* If there are values that need to be removed from domains remove them */
if (initialValues.length() > 0) {
removeRowDomainValues(currentCell[0], initialValues);
}
}
/**
* Forward check just 1 column, determined by the @param currentCell.
*/
private void fcCol(int[] currentCell) {
String initialValues = "";
if (solution[currentCell[0]][currentCell[1]] != null) {
initialValues = initialValues+solution[currentCell[0]][currentCell[1]].toString();
}
/* If there are values that need to be removed from domains remove them */
if (initialValues.length() > 0) {
removeColDomainValues(currentCell[1], initialValues);
}
}
private void fcBox(int[] currentCell) {
String initialValues = "";
/* Finds the top left square of the current 3x3 box. */
int boxRow = currentCell[0] - (currentCell[0] % 3);
int boxCol = currentCell[1] - (currentCell[1] % 3);
initialValues = initialValues+solution[currentCell[0]][currentCell[1]].toString();
/* If there are values that need to be removed from domains remove them */
if (initialValues.length() > 0) {
removeBoxDomainValues(boxRow, boxCol, initialValues);
}
}
@Override
public String getName() {
return NAME;
}
@Override
public void setSolution(Integer[][] userInputPuzzle) {
this.solution = userInputPuzzle;
}
}
