Sudoku solver using forward checking

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 "+cell+" Domain:"+domain);
emptyDomainFlag = true;
break;
}
}
}

/**
* Remove the values fr

Don't use strings to represent bits

I scanned over your code very quickly and the first thing to stick out was that you are using strings called domains all over the place. These domains are used as an array of characters, each of which is a possibility left in a row/column/box. Each domain starts with the value "123456789" and then characters are stripped from each domain as numbers are filled in.

What you should do instead of using a string is to simply use an int to represent a domain. The first 9 bits of the int will represent whether each of the nine numbers is still possible. So each int will start off with the value 0x1ff which in binary is 111111111. Then when you want to strip a possibility, you use the & operator like this:

// value is in the range 0..8.  If you want to use 1..9, use (value-1)
domain &= ~(1 << value);

Code like this:

String initialValues = "";
    initialValues = initialValues+solution[currentCell[0]][currentCell[1]].toString();

would turn into this:

int initialValues = 0;
    initialValues |= (1 << solution[currentCell[0]][currentCell[1]]);

One based vs Zero based

I know that Sudoku involves the numbers 1..9. But in your program, I think that it simplifies a lot of logic to solve using zero based numbers, i.e. 0..8. This applies to array indexing, bit numbering, row/column calculations, etc. When you finally want to print out some kind of information to the user, you can convert the numbers back to 1..9 at that point.

Two dimensional arrays vs one dimensional arrays

It's strange that you use two dimensional arrays sometimes (board,solution) but one dimensional arrays at other times (domains). I think you should just use one dimensional arrays everywhere. It would simplify things in that you don't have to use an int[2] cell type just to hold a row/column pair.

Hardcoded numbers

At the top of the file, you define this values nicely:

private static final int GRIDSIZE_ROW = 9;
private static final int GRIDSIZE_COLUMN = 9;
private static final int BOXSIZE = 3;

But then in your program, you don't consistently use them. I still see a lot of 3s and 9s all over the place. Examples:

int cell = (i * 9) + 1 + j;
    int boxRow = cell[0] - (cell[0] % 3);
    int boxCol = cell[1] - (cell[1] % 3);

Other things

-
This line was pretty ugly:

break all;      /* used to break out of both loops when a cell is found */

It could have just been:

return cell;

-
deepCopy() is dead code. It's probably a leftover from when you used a HashMap.

How to loop through all bits

int domainBits = 0x124; // Example value, could be any combination
while (domainBits != 0) {
    int lowestBitNumber = Integer.numberOfTrailingZeros(domainBits);
    domainBits &= ~(1 << lowestBitNumber);
    // Do stuff here on lowestBitNumber
}

In the above example, domainBits starts at 0x124 which is 100100100 in binary. The loop will loop three times. The first time, lowestBitNumber will be 2, the second time 5, the third time 8. These correspond to the three bits set in domainBits.

StackExchange Code Review Q#90761, answer score: 6