Monthly Archives: August 2010

Sudoku: Math Is Hard, Let’s Go Shopping

4 Replies

I’ve been researching others’ techniques for generating sudoku puzzles, and I have come to the conclusion that nobody actually knows how to do it.

Seriously, if you Google for “generating sudoku puzzles”, most of the methods boil down to “randomly throw numbers at the board and see if it’s a sudoku”. Oh, there’s some cleverness you can do to try to intelligently preserve the randomness of a partially-complete sudoku puzzle (like not randomly putting a 9 into a column that already has one) but at the end of the day all of the solutions basically amount to bogosort.

I promised yesterday that I’d reveal the identity board math. I had planned a big reveal here with lots of mathy explanationing, but the math just isn’t that exotic. There’s a trick to it, but that’s about it. Here’s the math:

A Sudoku board of dimension n is n2xn2 digits, and has nxn sectors, each with n2 digits. Let’s write a function to find the number at position x, y on the board. The whole trick to my F(x,y) math is simply this: the numbers in every sector other than (0,0) are rotations or shifts of the numbers in sector (0,0).

Make sense? Here. The numbers in sector(0,0) are simply the digits 1..n2, arranged in a grid, so that’s easy:

F(x,y): y*n+x

And the math for every other sector is simply a selection into sector 0, 0. Specifically, for F(x,y) outside of sector (0,0), choose the F(x’,y’) IN sector 0,0 such that

x’ = ((x+y/n)%n

y’ = ((y+x/n)%n

So at the end of the day the whole function looks like this in ruby:

def idfx(x, y, n)
  if x<n && y<n
    y*n+x
  else
    idfx( ((x+y/n)%n, ((y+x/n)%n )
  end
end

I should point out that I am operating under the belief that a sudoku puzzle is like a Rubik’s Cube: that a set of transformations can be performed on a valid puzzle that leave the puzzle changed but always valid, and that you can turn any sudoku puzzle into any other sudoku puzzle via these transformations. If I am right, I can take my identity puzzle board and shuffle it using these transformations, and just like scrambling a Rubik’s Cube I will be left with a unique and interesting puzzle that is, most importantly, still valid.

I have proven the first half of my assumption–there are transformations that will change a sudoku without affecting its validity. What I haven’t proven is the second half. I cannot yet transform puzzles arbitrarily. It may not be possible at all, but right now I’m simply hoping that I don’t know enough transformations yet.

Sudoku: Creating Identity Boards

Leave a reply

I’m building a Sudoku generator. There’s just enough wicked math in there to make things interesting. One thing that caught my attention was that there is a sort of “identity” board that you should be able to build for any dimension of sudoku. For the standard 3×3 matrix, it looks like this:

+------+------+------+
| 1 2 3| 4 5 6| 7 8 9|
| 4 5 6| 7 8 9| 1 2 3|
| 7 8 9| 1 2 3| 4 5 6|
+------+------+------+
| 2 3 1| 5 6 4| 8 9 7|
| 5 6 4| 8 9 7| 2 3 1|
| 8 9 7| 2 3 1| 5 6 4|
+------+------+------+
| 3 1 2| 6 4 5| 9 7 8|
| 6 4 5| 9 7 8| 3 1 2|
| 9 7 8| 3 1 2| 6 4 5|
+------+------+------+

The way you write an identity board is this: You write the digits 1..9 in order in the top left sector and across the top line of the puzzle. If you look at it in terms of triplets, however, you build the top line by copying the 2nd triplet row (4 5 6) and then the 1st triplet row (7 8 9) across the top line.

The second row starts with (4 5 6) so you naturally continue with (7 8 9) in the next sector, and then roll around to the beginning to end with (1 2 3). The third row then follows naturally: (7 8 9) (1 2 3) (4 5 6).

You can build the entire board this way if you do the same thing vertically. Copying the first sector’s columns down the board’s first column, you get (1 4 7), (2 5 8), (3 6 9). Do this across the entire board and you end up with the completed puzzle.

The really neat part of this for me is that it works with any dimension of sudoku. For example, here’s a 2×2 and a 4×4 identity board built the same way:

+-----+-----+
| 0 1 | 2 3 |
| 2 3 | 0 1 |
+-----+-----+
| 1 0 | 3 2 |
| 3 2 | 1 0 |
+-----+-----+

+---------+---------+---------+---------+
| 0 1 2 3 | 4 5 6 7 | 8 9 A B | C D E F |
| 4 5 6 7 | 8 9 A B | C D E F | 0 1 2 3 |
| 8 9 A B | C D E F | 0 1 2 3 | 4 5 6 7 |
| C D E F | 0 1 2 3 | 4 5 6 7 | 8 9 A B |
+---------+---------+---------+---------+
| 1 2 3 0 | 5 6 7 4 | 9 A B 8 | D E F C |
| 5 6 7 4 | 9 A B 8 | D E F C | 1 2 3 0 |
| 9 A B 8 | D E F C | 1 2 3 0 | 5 6 7 4 |
| D E F C | 1 2 3 0 | 5 6 7 4 | 9 A B 8 |
+---------+---------+---------+---------+
| 2 3 0 1 | 6 7 4 5 | A B 8 9 | E F C D |
| 6 7 4 5 | A B 8 9 | E F C D | 2 3 0 1 |
| A B 8 9 | E F C D | 2 3 0 1 | 6 7 4 5 |
| E F C D | 2 3 0 1 | 6 7 4 5 | A B 8 9 |
+---------+---------+---------+---------+
| 3 0 1 2 | 7 4 5 6 | B 8 9 A | F C D E |
| 7 4 5 6 | B 8 9 A | F C D E | 3 0 1 2 |
| B 8 9 A | F C D E | 3 0 1 2 | 7 4 5 6 |
| F C D E | 3 0 1 2 | 7 4 5 6 | B 8 9 A |
+---------+---------+---------+---------+

The neatness of this pleased me, but when I tried to implement it in code it got hopelessly complicated very fast. On the drive home from work last week, I found an elegant mathematical function to produce this board. Can you guess it? I’ll post it tomorrow. If you can’t wait, dig around in my twitter feed–the entire function is less than 72 characters.

How to Install RSpec and RSpec-rails

1 Reply

I’ve done this so many times this week that I’m writing it down here where I can Google it later. What I’m looking for is the specific three commands you type to install rspec and rspec-rails as plugins into my rails project.

To find this data normally, I do this:

  1. Go to http://rspec.info because that’s the URL I can remember.
  2. Click on Spec::Rails in the menu bar.
  3. Click on Install in THAT menu bar.
  4. This takes you to a page that tells you that the Install instructions are no longer here, they’ve moved to http://wiki.github.com/dchelimsky/rspec/rails
  5. Hooray! THIS is the page you want to be at. Sure enough, scroll down to see

Okay, now… ready for the kicker? This documentation is ALSO out of date. (There’s a crash bug in tag 1.2.9 when you call model.should be_valid.) As of this writing, if you clone the rspec-rails repo and examine the tags, you will see that 1.3.2 is available. So here’s the updated command. For now.

ruby script/plugin install git://github.com/dchelimsky/rspec.git -r 'refs/tags/1.3.2'
ruby script/plugin install git://github.com/dchelimsky/rspec-rails.git -r 'refs/tags/1.3.2'
ruby script/generate rspec

…But lately I just get the latest and it seems to work:

ruby script/plugin install git://github.com/dchelimsky/rspec.git
ruby script/plugin install git://github.com/dchelimsky/rspec-rails.git
ruby script/generate rspec