I wrote a solver which calculates tough sudoku’s in about 1/3rd of a second. It doesn’t have any techniques or fancy strategies: for solving 1 puzzle it’s fast enough. It just fills in the next empty cell, unless it can’t, then it tries to increase the value of the previous cell, unless it can’t, etc etc. Worst case would be that it arrives at the last cells and has to backtrack all the way back to the first cells, repeatedly.
import java.util.Arrays;
public class Sudoku
{
public static void main(String[] args)
{
int[] grid = {//
0, 0, 3, 6, 0, 0, 8, 0, 0,//
0, 0, 9, 0, 0, 0, 0, 0, 3,//
0, 7, 0, 0, 0, 0, 0, 2, 0,//
0, 0, 1, 0, 0, 0, 7, 0, 4,//
0, 0, 7, 0, 0, 2, 0, 0, 0,//
9, 5, 0, 0, 0, 0, 0, 6, 0,//
0, 0, 0, 0, 0, 1, 2, 0, 0,//
8, 0, 0, 3, 0, 0, 6, 0, 0,//
0, 0, 0, 7, 4, 0, 9, 0, 0 };
print(grid);
int[] work = grid.clone();
if(solve(work, 0))
print(work);
for(int i = 0; i < 4; i++)
{
long t1 = System.currentTimeMillis();
solve(grid.clone(), 0);
long t2 = System.currentTimeMillis();
System.out.println("solving took: " + (t2 - t1) + "ms");
}
}
public static void print(int[] grid)
{
for(int i = 0; i < 81; i += 9)
System.out.println(Arrays.toString(Arrays.copyOfRange(grid, i, i + 9)));
System.out.println();
}
public static boolean solve(int[] grid, int cell)
{
while (cell < 81 && grid[cell] > 0)
cell++;
if(cell == 81)
return true;
for(int i = 1; i <= 9; i++)
{
grid[cell] = i;
+ if(isColumnValid(grid, cell % 9))
+ if(isRowValid(grid, cell / 9))
+ if(isBlockValid(grid, cell % 3 * 3, cell / 9 % 3 * 3))
if(isValid(grid) && solve(grid, cell + 1))
return true;
}
grid[cell] = 0;
return false;
}
private static final int[] freqs = new int[10];
public static boolean isValid(int[] grid)
{
for(int i = 0; i < 9; i++)
{
if(!isRowValid(grid, i))
return false;
if(!isColumnValid(grid, i))
return false;
if(!isBlockValid(grid, i % 3 * 3, i / 3 * 3))
return false;
}
return true;
}
public static boolean isRowValid(int[] grid, int row)
{
Arrays.fill(freqs, 0);
for(int i = 0; i < 9; i++)
{
int cell = grid[row * 9 + i];
if(cell > 0 && ++freqs[cell] > 1)
return false;
}
return true;
}
public static boolean isColumnValid(int[] grid, int col)
{
Arrays.fill(freqs, 0);
for(int i = 0; i < 9; i++)
{
int cell = grid[i * 9 + col];
if(cell > 0 && ++freqs[cell] > 1)
return false;
}
return true;
}
public static boolean isBlockValid(int[] grid, int x, int y)
{
Arrays.fill(freqs, 0);
for(int i = 0; i < 9; i++)
{
int cell = grid[(y + i / 3) * 9 + (x + i % 3)];
if(cell > 0 && ++freqs[cell] > 1)
return false;
}
return true;
}
}
[0, 0, 3, 6, 0, 0, 8, 0, 0]
[0, 0, 9, 0, 0, 0, 0, 0, 3]
[0, 7, 0, 0, 0, 0, 0, 2, 0]
[0, 0, 1, 0, 0, 0, 7, 0, 4]
[0, 0, 7, 0, 0, 2, 0, 0, 0]
[9, 5, 0, 0, 0, 0, 0, 6, 0]
[0, 0, 0, 0, 0, 1, 2, 0, 0]
[8, 0, 0, 3, 0, 0, 6, 0, 0]
[0, 0, 0, 7, 4, 0, 9, 0, 0]
[2, 4, 3, 6, 5, 7, 8, 9, 1]
[6, 8, 9, 2, 1, 4, 5, 7, 3]
[1, 7, 5, 9, 3, 8, 4, 2, 6]
[3, 2, 1, 5, 6, 9, 7, 8, 4]
[4, 6, 7, 1, 8, 2, 3, 5, 9]
[9, 5, 8, 4, 7, 3, 1, 6, 2]
[7, 3, 6, 8, 9, 1, 2, 4, 5]
[8, 9, 4, 3, 2, 5, 6, 1, 7]
[5, 1, 2, 7, 4, 6, 9, 3, 8]
-solving took: 1027ms
-solving took: 1026ms
-solving took: 1023ms
-solving took: 1027ms
+solving took: 390ms
+solving took: 389ms
+solving took: 387ms
+solving took: 387ms
World’s hardest sudoku for mere mortals:
http://i.telegraph.co.uk/multimedia/archive/02260/Untitled-1_2260717b.jpg
[8, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 3, 6, 0, 0, 0, 0, 0]
[0, 7, 0, 0, 9, 0, 2, 0, 0]
[0, 5, 0, 0, 0, 7, 0, 0, 0]
[0, 0, 0, 0, 4, 5, 7, 0, 0]
[0, 0, 0, 1, 0, 0, 0, 3, 0]
[0, 0, 1, 0, 0, 0, 0, 6, 8]
[0, 0, 8, 5, 0, 0, 0, 1, 0]
[0, 9, 0, 0, 0, 0, 4, 0, 0]
[8, 1, 2, 7, 5, 3, 6, 4, 9]
[9, 4, 3, 6, 8, 2, 1, 7, 5]
[6, 7, 5, 4, 9, 1, 2, 8, 3]
[1, 5, 4, 2, 3, 7, 8, 9, 6]
[3, 6, 9, 8, 4, 5, 7, 2, 1]
[2, 8, 7, 1, 6, 9, 5, 3, 4]
[5, 2, 1, 9, 7, 4, 3, 6, 8]
[4, 3, 8, 5, 2, 6, 9, 1, 7]
[7, 9, 6, 3, 1, 8, 4, 5, 2]
solving took: 75ms
solving took: 76ms
solving took: 76ms
solving took: 75ms
For which I never finished my own solver, because I wanted to implement all sorts of clever methods. 