I've read a bit more about Sudoku, and even played part of a game. Plus, the ideas of others in the lists and in email have me thinking. Should I try some of these ideas ... or not? UPDATED: My strategy conclusion is wrong!

## 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```