Sudoku game or humans vs. machines (computers in this case)

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