Sudoku: Learning, Thinking and Doing Something About It
Strategies and Stronger Objects
I downloaded a Tablet PC Sudoku game and fiddled with it a bit. I haven’t finished a game, and I’m kind of holding off on doing so just as some kind of silly point of honor. But I did play long enough to get some hints of how to work with the puzzle.
I’ve also read a bit about the puzzle, and it’s clear that there are some strategies that are worth thinking about. It seems that trying possibilities and backing them out of they don’t work is ill thought of in the Sudoku-solving community, though I did find the possibility mentioned in one article. But there are definitely strategies that are worth thinking about.
We already have the rudiments of one strategy in place: if there’s only one possibility for a cell, we have the ability to detect that and to fill it in. I don’t know yet how many games that strategy alone will solve, but it’s clear from my reading that it isn’t strong enough for all games.
As far as I could tell, it wasn’t strong enough for the game I was playing with, which was labeled easy by the Tablet PC game. At least I got to a point where there didn’t seem to be any fully constrained cells. I did figure out some additional strategies. Here’s one pic I drew:
In the pic above, there’s a box with two open cells, each of which can only contain a 1 or a 7. Somewhere up above one of those cells, there’s a cell that could contain 1, 7 or some other number z. Then that cell must actually contain z, because if we put either a 1 or a 7 in it, the box below would be blocked. So, a limitation on what must be done later in the box below limits what we can do … and in this case defines what must be done.
This is simply incorrect! I’m not sure whether my memory of the game I was fooling with was off, or whether I just reasoned incorrectly. In any case, if all three of the cells in question are in a single row or column, then the reasoning is true. But not if they are at right angles as shown in the sketch. Thanks to everyone who dog-piled me … and to the one person who wrote to thank me for showing what really happens when I program this stuff. And thanks to those who read and don’t write back as well. I hope this stuff can be useful, as a horrible example if nothing else.
In that same pic, though it’s not shown, since we know that someday both 1 and 7 are going to end up in the middle row of the box, we also know that 1 and 7 are impossible anywhere else in that row. That could result in some other cell being solvable.
These are interesting rules, because to apply them, we’ll need to examine a box (called square in my code right now, but I gather that box is the official word) and determine that there are two cells, in the same row or column, with the same two possibles, and that those possibles don’t appear anywhere else in the box. We can easily check the possibles, our code already does that. What we don’t have, yet, is a way to ascertain that the box won’t allow those values anywhere else.
Strategies like these are going to raise the need to ask fairly complex questions about a row, a column, or a box. That, in turn, suggests to me that the code, plus our recognized needs, are calling out for some smarter objects to support row, column, and box.
I’m also thinking that each cell may need to be smarter. We might want them to have some intelligence and memory. When we ask what values a cell can contain, it might be better to ask the cell. Right now, we’re asking the game. Furthermore, it’s an open question whether the cell should be asked to remember something like “I can’t contain a 1 or a 7, because if I do I’ll damage that box down there”, or if, instead, the box should inform the cell, somehow, that it can’t contain those values. At this moment, I’m not sure whether that bit of analysis will more easily be driven by asking the neighboring boxes if they have anything to say, or whether it will be better for them to tell their neighbors what they should and shouldn’t do.
And one more thing: the current code computes the indexes of the cells that make up the rows and columns and boxes, every time we use them. That’s inefficient – though I don’t have a performance measure to prove that it’s important, as I was taught.
Putting this all together, I’m thinking that the code is telling us that it might like to have smarter cells, and that the game might want to have rows and columns and boxes that “point to” or “contain” the cells, rather than indexing into them dynamically as they do now.
Isn't This YAGNI?
No. This is thinking. YAGNI is doing, not thinking. If I were to implement any of these ideas, we’d have to ask whether that implementation wsa YAGNI. On the one hand, I prefer to wait until the code practically begs for new objects. On the other hand, I’m not bound by any law that says I can’t refactor the code to make it better, any time I want. I just like to do that very judiciously, and prefer to do it in response to a current need, not just to some thing that “we’re gonna need”.
Anyway, let’s take a look at the code so far. Here’s the game class:
require 'project.rb'
class Game
def Game::test_game
game = Game.new([])
game.test_game
game
end
def initialize(anArray)
@cells = anArray
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
def row_containing(aCell)
aCell / 9
end
def column_containing(aCell)
aCell % 9
end
def square_containing(aCell)
row_containing(aCell) / 3 * 3 + column_containing(aCell) / 3
end
def first_constrained
(0..80).each do
| cell |
return cell if constrained?(cell)
end
return nil
end
def constrained?(aCell)
@cells[aCell] == 0 && possible_values(aCell).length == 1
end
def possible_values(aCell)
possibles = [1, 2, 3, 4, 5, 6, 7, 8, 9]
possibles = possibles - row(row_containing(aCell))
possibles = possibles - column(column_containing(aCell))
return possibles - square(square_containing(aCell))
end
def proposed_value(aCell)
possibles = possible_values(aCell)
return nil if possibles.length != 1
return possibles.first
end
end
If we’re looking for places where objects ought to be, we should be looking at where there are primitive types, such as integers and strings. In our case, the primitives we’re using are all integers, and collections of integers, some of which are cell values, and some of which are indexes into an array of integers. None of this is very object oriented.
Let’s begin by building a Cell class. For now, it will just hold the integer value, but we can foresee that a Cell should know what row and column and box it is in. That may come up soon. So I’ll add a Cell class, and initialize the cells member of the Game to have an array of Cells:
require 'project.rb'
class Cell
attr :value
def initialize aValue
value= aValue
end
end
In Game, here’s the init:
def initialize(anArray)
@cells = anArray.collect { | value | Cell.new(value) }
end
This breaks a test, and only one, test_first_game, which expects 23 and gets nil:
def test_first_game
givens =
[0, 2, 3, 8, 0, 0, 0, 0, 7,
0, 5, 8, 9, 7, 6, 2, 0, 0,
7, 0, 0, 2, 0, 0, 0, 5, 0,
9, 0, 0, 4, 0, 2, 0, 0, 0,
6, 0, 7, 0, 0, 0, 4, 0, 5,
0, 0, 0, 7, 0, 8, 0, 0, 6,
0, 1, 0, 0, 0, 7, 0, 0, 8,
0, 0, 9, 5, 8, 4, 1, 7, 0,
8, 0, 0, 0, 0, 3, 5, 4, 0]
game = Game.new(givens)
assert_equal(23, game.first_constrained)
assert_equal(1, game.proposed_value(23))
end
At first I’m surprised by this, but most of our tests are just checking to see if the rows and colums are arranged right, so maybe that’s OK. Let’s make this one work, and then look a bit further at those tests. The issue is that first_constrained returned a nil. It was looking for cells that are zero and that only have one possible value. Of course no cell is zero any more, they’re all an instance of Cell. Their value might be zero. Therefore:
def constrained?(aCell)
@cells[aCell].value == 0 && possible_values(aCell).length == 1
end
This isn’t going to be sufficient, of course … and it isn’t. Now possible_values is wrong. It looks like this:
def possible_values(aCell)
possibles = [1, 2, 3, 4, 5, 6, 7, 8, 9]
possibles = possibles - row(row_containing(aCell))
possibles = possibles - column(column_containing(aCell))
return possibles - square(square_containing(aCell))
end
The issue is that row and column and square aren’t returning integers any more, and we want them to. Those look like this:
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
Remember how proud I was of that range selection in the rows method? Now we see that it should have been done the same way as the others. In any case, each one of these methods needs to collect the cell values, not the cells:
def row(row_number)
row_start = row_number*9
@cells[row_start, 9].collect { | cell | cell.value }
end
def column(column_number)
column_indexes(column_number).collect { | c | cell(c).value }
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).value }
end
def square_indexes(square_number)
start_cell = start_cell(square_number)
raw_square.collect { | offset | start_cell + offset }
end
Blammo! That breaks all the tests, in odd ways that I don’t like. I’m sure I could push through and fix them all, but that feels like a mistake. I’m going to back out all these changes and start over.
What Happened?
What seemed like a simple change turned out not to be. I made one change, a test broke, I changed a couple more things, and more tests broke. Bad sign, especially since I was surprised. That’s Nature’s way of telling me I don’t know what I’m doing. I just had a couple of minutes into the change and it was getting ugly. Better to back out now, before I’m hip deep in it. Let’s take another look at how to do this … and whether.
Try ... Again
OK, it’s nite time now, not early morning. I’ve had dinner at Cheeburger Cheeburger (nothing but the best for me when I travel) and I think I’m ready to take another run at improving the code. I’ll start by reviewing it again, to see what my slightly more experienced eyes see this time.
OK. Our fundamental data structure is an array of integers. Not very strong. Some of the other folks who are working the problem are recommending more structured arrays, up to 4D, but that seems to me just to be encoding meaning even more messily into magic numbers.
I have methods like :row, and :row_indexes, the former representing a set of integer values found in the row, and the latter representing the indexes of those values in the cell array. Some other authors have hard-coded the index lists, while I have them computed. Since I have them, I don’t see much advantage to changing that code. I do think that the method name :row might be better if it were something like :row_values, to emphasize that it returns the values. That’s not too important now, but if the cells become something better than ints, it will help.
We noticed last time, and again now, that the clever trick I used to take advantage of the row indexes being contiguous integers has made the row-fetching code look different from the column-fetching and square-fetching. I think that’s a mistake. One possibility is to make those three things all look alike, and then refactor to remove the duplication.
That would have the advantage of centralizing the code that knows that the cells are ints, which could mean there would be just one place that we’d have to change to make them into objects. That would be good.
I also remember that there are two ways that the array gets set up right now, the normal constructor, and the test_game method. That bit me, causing a bunch of tests to break because that didn’t go through the same code. I think I’ll fix that first, changing the test_game class method to use the real constructor. That should be easy and it’ll let me get my hand in.
Refactor test_game
The test_game class method and its supporting instance method look like this:
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
...
I should be able to use the regular constructor by just creating the array and passing it in, instead of passing an empty one and then adding to it. Here goes:
def Game::test_game
Game.new((0..80).to_a)
end
(instance method test_game deleted)
Uh, wow. That’s shorter and better, isn’t it? Who coded that other dumb idea? Interesting. What was going on when I wrote that was that I had a lot on my mind about what I was trying to accomplish, and didn’t have enough brain power left to think of a decent way to do it. Having a pair would likely have helped with that. Pitfalls of programming alone.
Consolidating the Collects.
Basically, we collect values in three places, two of them looking very much alike:
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 square(square_number)
square_indexes(square_number).collect { | c | cell(c) }
end
I’d like to consolidate those into one. First let’s consolidate the two that look alike:
def row(row_number)
row_start = row_number*9
@cells[row_start, 9]
end
def column(column_number)
collect_values column_indexes(column_number)
end
def square(square_number)
collect_values square_indexes(square_number)
end
def collect_values index_collection
index_collection.collect { | c | cell(c) }
end
We just made a helper method and called it twice. Tests all run. Now let’s change the row method to use the helper:
def row(row_number)
row_start = row_number*9
collect_values row_start..row_start+8
end
Tests still run. I don’t like the method name cell. I think I want to call it cell_value instead. I’ll just rename the method to see who calls it beside our collect_values.
def cell_value(i) @cells[i] end def collect_values index_collection index_collection.collect { | c | cell_value(c) } end
It turns out that test_cells calls it too:
def test_cells
(0..80).each do | i |
assert_equal(i, @game.cell(i))
end
end
That test isn’t very interesting … in fact none of the tests that run on the test_game are very interesting now, but let’s just make it legal for now, rather than think about refining the tests.
def test_cells
(0..80).each do | i |
assert_equal(i, @game.cell_value(i))
end
end
OK. Now we have all the cell value fetching and setting centralized to the cell_value method and the constructor. Let’s see if now we can put our Cell class back, and make everything continue to work:
class Cell
attr_accessor :value
def initialize aValue
value= aValue
end
end
and in Game:
def initialize(anArray)
@cells = anArray.collect { | value | Cell.new(value) }
end
def cell_value(i)
@cells[i].value
end
Perhaps I’ve forgotten something, but I expect this to work. Let’s run the tests and see … No! Everything blows up much as it did this morning. The 23 test finds nil instead of 23, and all the test_column and similar tests are returning a bunch of nils instead of the expected arrays of values.
On a flyer, I guess that I don’t understand how attr_accessor works, so I hand code the accessor for value:
class Cell
def initialize aValue
@value = aValue
end
def value
@value
end
end
Boom, everything works again in the test_column-ish tests and the test_first_game test is still getting a nil. Let’s look at it:
def test_first_game
givens =
[0, 2, 3, 8, 0, 0, 0, 0, 7,
0, 5, 8, 9, 7, 6, 2, 0, 0,
7, 0, 0, 2, 0, 0, 0, 5, 0,
9, 0, 0, 4, 0, 2, 0, 0, 0,
6, 0, 7, 0, 0, 0, 4, 0, 5,
0, 0, 0, 7, 0, 8, 0, 0, 6,
0, 1, 0, 0, 0, 7, 0, 0, 8,
0, 0, 9, 5, 8, 4, 1, 7, 0,
8, 0, 0, 0, 0, 3, 5, 4, 0]
game = Game.new(givens)
assert_equal(23, game.first_constrained)
assert_equal(1, game.proposed_value(23))
end
It’s failing on line 110, which is the first_constrained call. That’s returning nil instead of 23. Without looking at the code, which I’ll do in a second, I hypothesize that it’s some kind of thing where the first_constrained method expects to see an integer and is dealing instead with a Cell. And of course, I need to go back and figure out what was wrong with the attr_accessor thing, but clearly that’s me not understanding that aspect of Ruby. It’s very basic … but I haven’t used it (or Ruby for that matter) much at all. So, on to first_constrained.
def first_constrained
(0..80).each do
| cell |
return cell if constrained?(cell)
end
return nil
end
def constrained?(aCell)
@cells[aCell] == 0 && possible_values(aCell).length == 1
end
def possible_values(aCell)
possibles = [1, 2, 3, 4, 5, 6, 7, 8, 9]
possibles = possibles - row(row_containing(aCell))
possibles = possibles - column(column_containing(aCell))
return possibles - square(square_containing(aCell))
end
Cure enough. Notice that I’m accessing @cells directly, stupid me. I should have renamed the member variable to catch this. Anyway, we need to call cell_value instead, for sure:
def constrained?(cell_number)
cell_value(cell_number) == 0 && possible_values(cell_number).length == 1
end
I renamed the parameter as well, since it’s not a cell at all, it’s a cell number or cell index. That should be done further down as well. I don’t expect this to work yet, but I want to know what the test says:
Whoa! The tests all run! Since I’m surprised, I need to figure out why. First, to make it easier, I’m going to rename those other parameters:
def first_constrained
(0..80).each do
| cell_number |
return cell_number if constrained?(cell_number)
end
return nil
end
def constrained?(cell_number)
cell_value(cell_number) == 0 && possible_values(cell_number).length == 1
end
def possible_values(cell_number)
possibles = [1, 2, 3, 4, 5, 6, 7, 8, 9]
possibles = possibles - row(row_containing(cell_number))
possibles = possibles - column(column_containing(cell_number))
return possibles - square(square_containing(cell_number))
end
def proposed_value(cell_number)
possibles = possible_values(cell_number)
return nil if possibles.length != 1
return possibles.first
end
Ah. Good. possible_values works because it uses the row, column, and square method to get the values, and they are already converted, through the common method collect_values, to use the cell.value approach. Similarly for proposed_value. He just checks the size of possible values and returns the first. It’s all good.
In passing, I clean up possible_values a bit:
def possible_values(cell_number)
[1, 2, 3, 4, 5, 6, 7, 8, 9] -
row(row_containing(cell_number)) -
column(column_containing(cell_number)) -
square(square_containing(cell_number))
end
Summing Up
I set out to inject a new object, Cell, into the system. The first time a million tests broke, and I was surprised and lost confidence. Part of the problem was that I had not consolidated some duplication beforehand, but in retrospect I think that I probably could have pushed through and made the tests all run again. I base this on the fact that the same tests failed in the same way.
However, in the old format, the tests would have been fixed one at a time. Because the code was consolidated, in the new scheme, all the test_etc tests came back on line at once: there was just one bug to fix not three, two exactly the same in two places, and one different one. Much better.
Now I have an object in place instead of an integer, which will give me a place to store proposed values and things. But arguably the whole exercise, other than the consolidation, was premature. I would argue that it was not, because it improves the code according to Rule Of Simplicity #3: The code expresses all the design ideas you had while building it. I was thinking “cell” while coding integer, so I am not only justified in putting in Cell, I am required to by law. That’s my story, anyway, and I’m sticking to it.
There’s more to do, but the code is better, there’s an object in there, and a place to stand to make the code better still. At this writing there are a few things to do, like rename :row to :row_values, and I still can’t figure out why attr_accessor didn’t work for me. I just tried it again and it still fails. I guess I have to write a little bitty test to figure out what I’m doing wrong.
But the main thing to do is to call it a night, and give you a look at where we are. The current code follows:
The Code
project.rb
require 'test/unit'
require 'sudokutest.rb'
require 'game.rb'
require 'cell.rb'
sudokutest.rb
require 'project.rb'
class TC_MyTest < Test::Unit::TestCase
def setup
@game = Game.test_game
end
def test_cells
(0..80).each do | i |
assert_equal(i, @game.cell_value(i))
end
end
def test_row_three
assert_equal([27, 28, 29, 30, 31, 32, 33, 34, 35], @game.row(3))
end
def test_row_eight
assert_equal([72, 73, 74, 75, 76, 77, 78, 79, 80], @game.row(8))
end
def test_column_three
assert_equal([3, 12, 21, 30, 39, 48, 57, 66, 75], @game.column(3))
end
def test_square_four
assert_equal( [30, 31, 32, 39, 40, 41, 48, 49, 50], @game.square(4))
end
def test_square_eight
assert_equal( [60, 61, 62, 69, 70, 71, 78, 79, 80], @game.square(8))
end
def test_row_containing
assert_equal(0, @game.row_containing(0))
assert_equal(0, @game.row_containing(8))
assert_equal(1, @game.row_containing(10))
assert_equal(2, @game.row_containing(20))
assert_equal(3, @game.row_containing(30))
assert_equal(4, @game.row_containing(40))
assert_equal(5, @game.row_containing(50))
assert_equal(6, @game.row_containing(60))
assert_equal(7, @game.row_containing(70))
assert_equal(8, @game.row_containing(80))
end
def test_column_containing
assert_equal(0, @game.column_containing(0))
assert_equal(8, @game.column_containing(8))
assert_equal(1, @game.column_containing(19))
assert_equal(2, @game.column_containing(29))
assert_equal(3, @game.column_containing(39))
assert_equal(4, @game.column_containing(49))
assert_equal(5, @game.column_containing(59))
assert_equal(6, @game.column_containing(69))
assert_equal(7, @game.column_containing(79))
assert_equal(8, @game.column_containing(71))
end
def test_column_containing_minor_diagonal
assert_equal(0, @game.column_containing(72))
assert_equal(1, @game.column_containing(64))
assert_equal(2, @game.column_containing(56))
assert_equal(3, @game.column_containing(48))
assert_equal(4, @game.column_containing(40))
assert_equal(5, @game.column_containing(32))
assert_equal(6, @game.column_containing(24))
assert_equal(7, @game.column_containing(16))
assert_equal(8, @game.column_containing(8))
end
def test_square_containing
assert_equal(0, @game.square_containing(10))
assert_equal(0, @game.square_containing(0))
assert_equal(0, @game.square_containing(20))
assert_equal(1, @game.square_containing(13))
assert_equal(2, @game.square_containing(16))
assert_equal(3, @game.square_containing(37))
assert_equal(3, @game.square_containing(29))
assert_equal(3, @game.square_containing(45))
assert_equal(4, @game.square_containing(40))
assert_equal(5, @game.square_containing(43))
assert_equal(5, @game.square_containing(33))
assert_equal(5, @game.square_containing(53))
assert_equal(6, @game.square_containing(64))
assert_equal(7, @game.square_containing(67))
assert_equal(7, @game.square_containing(59))
assert_equal(7, @game.square_containing(75))
assert_equal(8, @game.square_containing(70))
assert_equal(8, @game.square_containing(60))
assert_equal(8, @game.square_containing(80))
end
end
class GameTest < Test::Unit::TestCase
def test_first_game
givens =
[0, 2, 3, 8, 0, 0, 0, 0, 7,
0, 5, 8, 9, 7, 6, 2, 0, 0,
7, 0, 0, 2, 0, 0, 0, 5, 0,
9, 0, 0, 4, 0, 2, 0, 0, 0,
6, 0, 7, 0, 0, 0, 4, 0, 5,
0, 0, 0, 7, 0, 8, 0, 0, 6,
0, 1, 0, 0, 0, 7, 0, 0, 8,
0, 0, 9, 5, 8, 4, 1, 7, 0,
8, 0, 0, 0, 0, 3, 5, 4, 0]
game = Game.new(givens)
assert_equal(23, game.first_constrained)
assert_equal(1, game.proposed_value(23))
end
end
game.rb
require 'project.rb'
class Game
def Game::test_game
Game.new((0..80).to_a)
end
def initialize(anArray)
@cells = anArray.collect { | value | Cell.new(value) }
end
def cell_value(i)
@cells[i].value
end
def row(row_number)
row_start = row_number*9
collect_values row_start..row_start+8
end
def column(column_number)
collect_values column_indexes(column_number)
end
def square(square_number)
collect_values square_indexes(square_number)
end
def collect_values index_collection
index_collection.collect { | c | cell_value(c) }
end
def column_indexes(column_number)
(0..8).collect { | row | column_number+row*9 }
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
def row_containing(aCell)
aCell / 9
end
def column_containing(aCell)
aCell % 9
end
def square_containing(aCell)
row_containing(aCell) / 3 * 3 + column_containing(aCell) / 3
end
def first_constrained
(0..80).each do
| cell_number |
return cell_number if constrained?(cell_number)
end
return nil
end
def constrained?(cell_number)
cell_value(cell_number) == 0 && possible_values(cell_number).length == 1
end
def possible_values(cell_number)
[1, 2, 3, 4, 5, 6, 7, 8, 9] -
row(row_containing(cell_number)) -
column(column_containing(cell_number)) -
square(square_containing(cell_number))
end
def proposed_value(cell_number)
possibles = possible_values(cell_number)
return nil if possibles.length != 1
return possibles.first
end
end
cell.rb
require 'project.rb'
class Cell
def initialize aValue
@value = aValue
end
def value
@value
end
end