Few days ago, a friend of mine posted the
following link on his wall on Facebook. The main question from that article was "how long will it take to crack ...the world's hardest Sudoku?". I felt like being challenged.
I am not a Sudoku fan, however my wife and my son are. Just to annoy them (not because I am a bad person :), but because I was looking for a way to sort the Sudoku puzzles in a quicker way, when being asked to assist them ... so, "I am lazy" is a more precise definition) and because I am a software engineer, I wrote a long time ago (of course I was inspired, it's not entirely my contribution) a little piece of Java code to resolve such puzzles. As a result, I decided to test it.
Here is the code:
import java.util.*;
import java.io.*;
public class ResolveSudoku {
private static final int[] sudokuMatrix = {0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0};
// load the content from file
public static void load(String file) throws Exception {
String str = null;
int line = 0;
BufferedReader br = new BufferedReader(new FileReader(file));
while ((str = br.readLine()) != null) {
if (str.trim().length() == 0 || str.startsWith("#"))
continue;
if (line >= 9) {
line = 10;
break;
}
String[] vls = str.split(",");
if (vls.length != 9) {
br.close();
throw new Exception("Line " + (line + 1) +
" has illegal number of elements!");
}
for (int i = 0; i < 9; ++i) {
int value = Integer.parseInt(vls[i].trim());
if (value < 0 || value > 9) {
br.close();
throw new Exception("Line " + (line + 1) +
" position " + (i + 1) + " has illegal value!");
}
sudokuMatrix[line*9 + i] = value;
}
++line;
}
br.close();
if (line != 9) throw new Exception("File " + file +
" has illegal number of lines!");
}
// print the content of the sudoku matrix
public static void printMatrix() {
for (int i = 0; i < 81; ++i) {
if (i != 0 && i % 3 == 0) System.out.print(" ");
if (i != 0 && i % 9 == 0) System.out.println();
if (i != 0 && i % 27 == 0) System.out.println();
if (sudokuMatrix[i] == 0) System.out.print(".");
else System.out.print(sudokuMatrix[i]);
}
System.out.println("\n");
}
private static boolean check(int row, int col, int value) {
// check if row is ok
int tmp = row * 9;
for (int i = 0; i < 9; ++i) {
if (sudokuMatrix[tmp + i] == value)
return false;
}
// check if column is ok
for (int i = 0; i < 9; ++i) {
if (sudokuMatrix[i*9 + col] == value)
return false;
}
// check if box is ok
tmp = (row / 3)*27 + (col / 3)*3;
if (sudokuMatrix[tmp] == value) return false;
if (sudokuMatrix[++tmp] == value) return false;
if (sudokuMatrix[++tmp] == value) return false;
tmp += 7;
if (sudokuMatrix[tmp] == value) return false;
if (sudokuMatrix[++tmp] == value) return false;
if (sudokuMatrix[++tmp] == value) return false;
tmp += 7;
if (sudokuMatrix[tmp] == value) return false;
if (sudokuMatrix[++tmp] == value) return false;
if (sudokuMatrix[++tmp] == value) return false;
return true;
}
public static boolean findSolution(int row, int col) {
if (row == 9) {
row = 0;
if (++col == 9) return true;
}
int pos = row * 9 + col;
if (sudokuMatrix[pos] != 0) return findSolution(row + 1, col);
for (int i = 1; i <= 9; ++i) {
if (check(row, col, i)) {
sudokuMatrix[pos] = i;
if (findSolution(row + 1, col)) return true;
}
}
// reset the value back to zero
sudokuMatrix[pos] = 0;
return false;
}
public static void main(String[] args) throws Exception {
load(args[0]);
printMatrix();
long start = System.currentTimeMillis();
boolean res = findSolution(0, 0);
long ex_time = System.currentTimeMillis() - start;
if (res) printMatrix();
else System.out.println("No solution!");
System.out.println("Execution time: " + ex_time + "ms.");
}
}
It's, basically, a routine that reads the puzzle's matrix from a file and another one that performs a brute force (i.e. analysing all the possible cases) in form of (I would say) an elegant recursive method call. Having the following input:
0,0,5,3,0,0,0,0,0
8,0,0,0,0,0,0,2,0
0,7,0,0,1,0,5,0,0
4,0,0,0,0,5,3,0,0
0,1,0,0,7,0,0,0,6
0,0,3,2,0,0,0,8,0
0,6,0,5,0,0,0,0,9
0,0,4,0,0,0,0,3,0
0,0,0,0,0,9,7,0,0
The problem was solved in ~30 milliseconds (after the byte code was JIT-ed on my "2.13Ghz, Core 2 Duo with SSD on board" laptop). And the answer was:
145 327 698
839 654 127
672 918 543
496 185 372
218 473 956
753 296 481
367 542 819
984 761 235
521 839 764
