I wrote a backtracking algorithm to generate sudokus with arbitrary size. My problem is the varying speed of this generation algorithm.
I added some console output to see the results. I generated ~20 Sudokus with the size of 16x16, each one had 1ms to 150ms generating time. The next one took over 10 minutes, and it didn't even finish. (I stopped the program). In consideration of that, I think I made a mistake in the backtracking implementation, which prevents the algorithm from advancing.
Here is the code:
public class Generator {
public static NormalSudoku generateNormal(int size) {
NormalSudoku ns = new NormalSudoku(size);
boolean[][][] track = new boolean[size][size][size];
ArrayList<Integer> vals = new ArrayList<Integer>();
fill(vals, size);
int row = 0;
int col = 0;
int val = 0;
int count = 0;
while (row < size) {
boolean found = false;
while (!vals.isEmpty() && !found) {
val = vals.get((int) (Math.random() * vals.size()));
track[row][col][val - 1] = true;
if (ns.checkValue(row, col, val)) {
ns.setValue(row, col, val);
fill(vals, size);
col++;
found = true;
} else {
vals.remove(Integer.valueOf(val));
}
if (col >= size) {
row++;
col = 0;
}
}
if (vals.isEmpty()) {
ns.setValue(row, col, 0);
for (int i = 0; i < size; i++) {
track[row][col][i] = false;
}
col--;
if (col < 0) {
row--;
col = size - 1;
}
ns.setValue(row, col, 0);
fill(vals, track, row, col);
}
}
return ns;
}
private static void fill(ArrayList<Integer> vals, int size) {
vals.clear();
for (int i = 1; i <= size; i++) {
vals.add(i);
}
}
private static void fill(ArrayList<Integer> vals, boolean[][][] track,
int row, int col) {
vals.clear();
for (int i = 0; i < track[row][col].length; i++) {
if (!track[row][col][i]) {
vals.add(Integer.valueOf(i + 1));
}
}
}
}
Explanation of the code:
boolean[][][] track:
some sort of checklist for the values which are already tried (to reduce overhead of trying the same random value multiple times). I put track[row][col][val] on true if I already tried to put val on this field. If I go back, I have to clear the marks for that cell, to make the values possible again.
ns.checkValue:
Sets the value on the cell, checks if the sudoku is still correct, sets the old value again and returns true/false.
ns.setValue:
Simply sets the value on the cell.
vals:
An array list containing the values which are not tried yet for that cell. If I move forward, the list obviously must contain every possible number. If I backtrack, the list only has to contain the numbers which aren't tried yet. (I use the track array to realize that).
What am I doing wrong?
Greets
