OK, Sudoku
[Added] What's It All About?
I see that it’s not obvious to people who haven’t been in the conversations what I’m up to. People say that the game of Sudoku makes a good TDD example. The ultimate idea is to write a program that, given a Sudoku puzzle setup, will solve the puzzle. I haven’t even played the game, so I don’t know the strategies. I do understand the rules of a solution. (For a 9x9 game, each integer from 1 to 9 must appear in each row, in each column, and in each of 9 inner squares.) I’d suggest a quick run at Google if you don’t know about the game, though maybe I’ll add some more about the game at some future time.
I could start, I suppose, with a simple Sudoku game and try to TDD its solution. I don’t feel that I could do that. I could return a literal result in “Fake It Till You Make It” style, but then what? So, instead, I’m going to set up a game with an assumed internal data structure, and then TDD some methods that I expect to need, namely fetching a row, a column, or an inner square.
Arguably this is a violation of YAGNI, but since I don’t really know how to start or how to know when I’m done, writing some Spike code in TDD style seems to me to be a good way to get my feet wet.
I’m not saying this is good, or what you should do, or anything of the kind. I’m displaying what I do, faced with this problem, and how I explore what the computer and I can do in moving toward a Suduko solution.
Maybe I’m even building infrastructure. Since this whole article represents maybe 90 minutes of programming, I’m not even out of the first day yet, so I don’t think I’ve broken any rules. I would like to have a better idea, but at this moment I don’t. If I didn’t feel I could make any progress programming, I wouldn’t program. But I think I can. Ride along and see if I’m right, or if I crash and burn.
Sudoku
My plan, subject as always to change, is to code something up in that way that I have, to see what happens. Right now, I’m planning to implement a fairly naive strategy, and a tree-trimming one that I think should solve all problems, albeit perhaps too slowly, and then leave it open to my readers to propose new squares and new heuristic algorithms.
I’m re-ripping my entire CD collection, so I have to sit here anyway. Might as well code something.
The Game
I’m not going to talk much here about the game. There’s a square of cells, with side length of n-squared, for order n = 1, 2, 3, 4, etc. You fill in the squares with the integers from 1 to n-squared, subject to the rule that the same integer cannot appear more than once in the same row, same column, or same n-size subsquare as the cell you’re filling in. The game begins with some squares “given”. Reportedly games come in a range of difficulty. Since I’ve never played the game, I don’t know what makes them more or less difficult. Maybe I’ll find out.
Why is This Interesting?
Frankly, I don’t know, since I don’t play the game. I think that during this exercise we might hit some interesting notions about solving computing problems we couldn’t solve by hand, and addressing problems about which we know very little. If nothing else, it may be amusing watching me drown.
Begin With a Test
I’m going to do this in Ruby. My plan is to start with 9 by 9 squares, just because I can, in spite of the fact that I can see already, having thought about it, how to use order to compute a bunch of the items. I’ll keep it specific just by way of tempting the YAGNI gods.
My Ruby style uses a project.rb file to map all the files in the app, and various .rb files to contain the tests and classes. My base setup looks like this:
project.rb
require 'test/unit'
require 'sudokutest.rb'
sudokutest.rb
require 'project.rb'
class TC_MyTest < Test::Unit::TestCase
def setup
end
def test_hookup
assert_equal(5, 2+2)
end
end
The test fails, asserting that my implementation of 5, 2+2, is not correct. Bummer. I was sure I had it figured out this time. Anyway, time to move to a Sudoku test. I guess I’ll have a class called Game, and I’m planning that it will contain an array of 81 integers, zero meaning a cell is empty, 1-9 otherwise, and that I’ll have to be able to ask questions about the rows and columns. For my starting Game, I’m going to put 0-80 in the elements, just for testing porpoises. My first test:
def test_cells
game = Game.test_game
(0..80).each do | i |
assert_equal(i, game.cell(i))
end
end
… and the resulting implementation:
class Game
def Game::test_game
game = Game.new
game.test_game
game
end
def test_game
@cells = []
for i in 0..80
@cells.push i
end
end
def cell(i)
@cells[i]
end
end
By the way … Ruby experts please bear with me … I haven’t used Ruby much for a while, and I have to relearn it. So I’ll do some pretty dumb implementations for a while. In test_game above, I intentionally built the array differently from how I was accessing it in the test, just to give myself a fair chance to catch any total misconceptions. I think it’s OK, but I’ll test some more. My plan is to build “accessors” that will fetch all the cells in a row, in a column, or in a square. I’ll start with the rows, and see whether I can correctly return the values in row three:
def test_row_three
game = Game.test_game
assert_equal([27, 28, 29, 30, 31, 32, 33, 34, 35], game.row(3))
end
Which wins the implementation:
def row(row_number)
row_start = row_number*9
@cells[row_start, 9]
end
Seems to work. I want to check the last row, because I’m uncertain whether I got all the numbers in there.
def test_row_eight
game = Game.test_game
assert_equal([72, 73, 74, 75, 76, 77, 78, 79, 80], game.row(8))
end
Test runs. Now let’s see if we can fetch columns. That’ll be a bit trickier.
def test_column_three
game = Game.test_game
assert_equal([3, 12, 21, 30, 39, 48, 57, 66, 75], game.column(3))
end
I think that’s right. I didn’t draw a picture, just did it in my head. The test will tell me. Now, hmm, to implement it. We need a vector of indexes, which we then convert to a vector of cell values. Should be easy enough. Wonder if I should test that first. No, I’ll go for it.
def column(column_number)
column_indexes = []
(0..8).each do
| row |
column_indexes.push column_number+row*9
end
column_indexes.collect { | c | cell(c) }
end
That works. I noticed along the way that the beginning of this method should be pulled out to express better the fact that it is computing a vector of indexes representing a column. Also I noticed that in the row method I referred to @cells directly, and here I used the cell() method. I ought to make up my mind. I’m inclined to use the @cells array, because in the row case, at least, it’s more efficient and more expressive to use the slice.
It’s time to dress for Zukey Lake Tavern. (They’re not very formal, but you don’t want to know how informally dressed I am right now. It’s rather hot here in Pinckney. We’re just down the road from Hell, you know.) My tests are all green, so it’s time to refactor, when we get back from dinner.
Post-Pizza Impression
Excellent pizza. We ate on the deck, on the roof, overlooking beautiful Zukey Lake. Perfect weather, felt like a vacation. Good chat with my wife, discussing the siblings article in Time, luck, and other matters. Now, a quick look at the code, and maybe some more tests and implementation, or then again, maybe not.
Here’s the code as it stands:
require 'project.rb'
class TC_MyTest < Test::Unit::TestCase
def setup
end
def test_cells
game = Game.test_game
(0..80).each do | i |
assert_equal(i, game.cell(i))
end
end
def test_row_three
game = Game.test_game
assert_equal([27, 28, 29, 30, 31, 32, 33, 34, 35], game.row(3))
end
def test_row_eight
game = Game.test_game
assert_equal([72, 73, 74, 75, 76, 77, 78, 79, 80], game.row(8))
end
def test_column_three
game = Game.test_game
assert_equal([3, 12, 21, 30, 39, 48, 57, 66, 75], game.column(3))
end
end
class Game
def Game::test_game
game = Game.new
game.test_game
game
end
def test_game
@cells = []
for i in 0..80
@cells.push i
end
end
def cell(i)
@cells[i]
end
def row(row_number)
row_start = row_number*9
@cells[row_start, 9]
end
def column(column_number)
column_indexes = []
(0..8).each do
| row |
column_indexes.push column_number+row*9
end
column_indexes.collect { | c | cell(c) }
end
end
Well, what do we see … there’s that use of cell vs @cell. Mostly harmless, I think I’ll leave it. There’s the possibility of extracting the code from the column method, the part that calculates the column indexes. I think it can be made simpler, too. Here’s step one:
def column(column_number)
column_indexes(column_number).collect { | c | cell(c) }
end
def column_indexes(column_number)
column_indexes = []
(0..8).each do
| row |
column_indexes.push column_number+row*9
end
column_indexes
end
Tests still run. Does it bother you to use the same name, column_indexes, for the variable inside the method, as the method name? It doesn’t bother me, mostly because I’m going to make that name disappear:
def column_indexes(column_number)
(0..8).collect { | row | column_number+row*9 }
end
Sweet. One more access method: let’s select out a square and fetch the cell values in it. I’m going to number the squares the same way the cells are numbered, left to right within top to bottom:
0 1 2 3 4 5 6 7 8
Our mission is to do the same thing as we did with the column, namely produce a vector of indexes of the square we want, and then collect the cell values. Let’s test, oh, the middle square, number 4, just to make the manual arithmetic hard.
def test_square_four
game = Game.test_game
assert_equal( [39, 40, 41, 48, 49, 50, 57, 59, 59], game.square(4))
end
I still haven’t drawn a picture of one of these things, so if I got that right it’s a miracle. The test will fail if I didn’t get something right, so let’s build the code, starting by intention:
def square(square_number)
square_indexes(square_number).collect { | c | cell(c) }
end
That was easy. Now the square_indexes. We reason as follows: a square has three elements from each of three consecutive rows, starting in row 0, 4, and 7. The first cell of the row is in position 0, 3, or 6. There’s almost certainly some cool mod thing to do. Also I’m thinking about wishing I could use slice, which I can’t with this implementation. One thing at a time. Let’s first write it out longhand:
def square_indexes(square_number)
result = []
first_row = square_number / 3
first_column = (square_number % 3) * 3
first_row.upto(first_row+2) do
| row |
first_column.upto(first_column+2) do
| col |
cell_number = row * 9 + col
result.push(cell_number)
end
end
result
end
That’s a lot of code, and I’m afraid it won’t work. And it doesn’t:
1) Failure: test_square_four(TC_MyTest) [./sudokutest.rb:31]: <[39, 40, 41, 48, 49, 50, 57, 59, 59]> expected but was <[12, 13, 14, 21, 22, 23, 30, 31, 32]>.
We see that it has started in row 1, not row 4 as it should have, but that it is taking the right corresponding cells after that incorrect start. So the row_number init is wrong.
Now, this might have been a good time to just throw the code away and start over, which is a pretty good trick. If I had felt the need to debug, I’d have tried to start over instead, since that method was pretty weird. But I see exactly what the bug is – I think – so I’ll just fix it. If it doesn’t work, I’ll start over.
The bug is that first_row should be 0, 3, or 6, and as calculated it’s 0, 1, or 2. Oops. (I also notice that above, I said 0, 4, 7, which is flat wrong. Anyway, we need to multiply by three. This should work:
def square_indexes(square_number)
result = []
first_row = square_number / 3 * 3
first_column = (square_number % 3) * 3
first_row.upto(first_row+2) do
| row |
first_column.upto(first_column+2) do
| col |
cell_number = row * 9 + col
result.push(cell_number)
end
end
result
end
Test still doesn’t run, saying:
1) Failure: test_square_four(TC_MyTest) [./sudokutest.rb:31]: <[39, 40, 41, 48, 49, 50, 57, 59, 59]> expected but was <[30, 31, 32, 39, 40, 41, 48, 49, 50]>.
But I think the test is wrong, and that thirty is correct. I got the 39 when I was thinking it was row 4. So the test is wrong, and should say:
def test_square_four
game = Game.test_game
assert_equal( [30, 31, 32, 39, 40, 41, 48, 49, 50], game.square(4))
end
Now that’s a bit iffy, so I’d better do another test. How about square 8? No chance I can do that by hand. I better draw a picture. OK …
def test_square_eight
game = Game.test_game
assert_equal( [60, 61, 62, 69, 70, 71, 78, 79, 80], game.square(8))
end
That test runs. Now let’s clean up that ugly square_indexes method. It currently looks like this:
def square_indexes(square_number)
result = []
first_row = square_number / 3 * 3
first_column = (square_number % 3) * 3
first_row.upto(first_row+2) do
| row |
first_column.upto(first_column+2) do
| col |
cell_number = row * 9 + col
result.push(cell_number)
end
end
result
end
What are some options? We could use collect on the inner loop, or, maybe, the outer one. There’s a way to flatten an array of arrays in Ruby, so we could do that. We could just crunch the code around. We could pull the starting numbers inside the loop and just loop over something simpler. The 0..8 in column_index is kind of nice.
Let’s try that. The relationship between the indexes is always the same in every square, it’s 0, 1, 2, 9, 10, 11, 18, 19, 20. Let’s just take that array and adjust it, using collect. That’s cool: we’ll just need the index of the first cell in the square. This should be neat.
What were the redneck’s last words? “Watch this.”
def raw_square [0, 1, 2, 9, 10, 11, 18, 19, 20] end def square_indexes(square_number) first_row = square_number / 3 * 3 first_column = (square_number % 3) * 3 start_cell = first_row * 9 + first_column raw_square.collect { | offset | start_cell + offset } end
That works. We just compute the starting cell, then use the raw_square indexes as offsets from that one. Still not lovely. Let’s extract the warmup:
def square_indexes(square_number)
start_cell = start_cell(square_number)
raw_square.collect { | offset | start_cell + offset }
end
def raw_square
[0, 1, 2, 9, 10, 11, 18, 19, 20]
end
def start_cell(square_number)
first_row = square_number / 3 * 3
first_column = (square_number % 3) * 3
first_row * 9 + first_column
end
Summing Up
Now we have a Game object that includes the ability to return all the cell values in a row, a column, or a square. That is arguably YAGNI, because I have no earthly purpose for those methods … yet. Well, get over it, that’s my motto, because I still don’t even know how to play this game, and now I know a lot about representing its data and manipulating it. This is enough for today, we have enough code, and enough words, to go public.
I’m not sure what I’ll do next. Maybe solve a puzzle, or part of one. Maybe something else. Maybe tomorrow … maybe next week. For now, thank you and good night. Here’s the code as it stands:
require 'project.rb'
class TC_MyTest < Test::Unit::TestCase
def setup
end
def test_cells
game = Game.test_game
(0..80).each do | i |
assert_equal(i, game.cell(i))
end
end
def test_row_three
game = Game.test_game
assert_equal([27, 28, 29, 30, 31, 32, 33, 34, 35], game.row(3))
end
def test_row_eight
game = Game.test_game
assert_equal([72, 73, 74, 75, 76, 77, 78, 79, 80], game.row(8))
end
def test_column_three
game = Game.test_game
assert_equal([3, 12, 21, 30, 39, 48, 57, 66, 75], game.column(3))
end
def test_square_four
game = Game.test_game
assert_equal( [30, 31, 32, 39, 40, 41, 48, 49, 50], game.square(4))
end
def test_square_eight
game = Game.test_game
assert_equal( [60, 61, 62, 69, 70, 71, 78, 79, 80], game.square(8))
end
end
class Game
def Game::test_game
game = Game.new
game.test_game
game
end
def test_game
@cells = []
for i in 0..80
@cells.push i
end
end
def cell(i)
@cells[i]
end
def row(row_number)
row_start = row_number*9
@cells[row_start, 9]
end
def column(column_number)
column_indexes(column_number).collect { | c | cell(c) }
end
def column_indexes(column_number)
(0..8).collect { | row | column_number+row*9 }
end
def square(square_number)
square_indexes(square_number).collect { | c | cell(c) }
end
def square_indexes(square_number)
start_cell = start_cell(square_number)
raw_square.collect { | offset | start_cell + offset }
end
def raw_square
[0, 1, 2, 9, 10, 11, 18, 19, 20]
end
def start_cell(square_number)
first_row = square_number / 3 * 3
first_column = (square_number % 3) * 3
first_row * 9 + first_column
end
end