4×4 Sudoku

The Java sudoku solver is coming along nicely. There are still a few obvious things missing; in particular there’s a simple strategy that should speed up solving quite a bit. (Which I won’t try to explain here.)

After that’s done, there’s a plan in the back of my mind to make it multi-threaded, or possibly even distributed. I’m not sure about the best place to split it up yet… For solving a puzzle that’s known to have one solution, or towards the end of generating a puzzle where only a few of the branches are valid, splitting up the brute force tasks should be fairly useful; but for choosing a value for the first cell of an empty puzzle, every branch has a valid solution, so having multiple threads exploring all of them is pointless. The most profitable time to split up the task would be early enough that the available branches are deep, and will take a while for each of the threads to explore; but late enough that only one of them is expected to be valid.

The interesting question is whether it’s possible to recognise that point.

Anyway, here’s a result from the current version. The 4×4 (er, 16×16) puzzle below took just over ten hours to generate.

6             2   15     16   11  
  2   4   3 8 12   5            
5 16 11     13 4           1   14  
  8 13           14           9 4
      14     1     7   3   4 6  
12 13 7       6 15         2   8 9
3       16 12     10     13       7
9           13 5       16   1    
  7   11         8   3       2  
13     16 8         10 1 7 4 3   6
  6           11     9 2       1
    8 1   5               13    
  15     14   3 16 2   5   12      
          2     4              
14     12   7 9 1     16   11   13  
2                 11       5 1 3

2 Comments »

  1. Priority-queued channel in Go — Dave's Programming Blog

    January 23, 2011 @ 3:17 pm

    [...] approach I used with the Java version was to keep partial solutions in a priority queue, ordered by the number of squares filled (so that [...]

  2. Ayden

    November 7, 2012 @ 4:53 am

    Languages topamax prices pharmacy Describe the process for preparing and distributing the medication

Leave a Comment