Archive for Projects

Sudoku speedup

Previous version: 10 hours.

With the latest improvement: 33 seconds.

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

Leave a Comment

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

Comments (2)

Zendo and inductive logic

…is what I’m thinking about now. (Okay, technically, are what I’m thinking about now.)

Don’t have time for a fully explanatory post right now; I just wanted to get something on here so that the new blog doesn’t stagnate before it’s even started. So here’s a bullet-point-form introduction:

  • Zendo is a game where players try to guess the Master’s secret rule by probing it with examples.
  • Inductive logic is… the same thing, really, except generalised to not necessarily include players, a Master, or… plastic pyramids.
  • Doing either of these things algorithmically is, in general, hard. But in an interesting way.

Also: colours!

Leave a Comment