Sudoku 5: Objects Begin to Emerge
What's Next
The strategy of looking for forced moves is working – at least it solved one puzzle. I’m not entirely comfortable, because of the odd problems that were exhibited when I was working with an incorrectly transcribed puzzle. I’m a happy path kind of guy, but clearly I’ll need to do something about that.
I think I’d like to normalize my terminology, specifically using the word “box” instead of “square”. “Box” seems to be the Sudoku term.
I’d like to add the “bifurcation” approach, which looks to me to be more like a tree-trimming approach, though it is probably worth starting one’s trial and error on a cell with only two options if possible: that will reduce the tree search time, I’d think. It might be best to carry that notion through, always making one’s next guess, if one is necessary, on a cell with the minimum number of options.
It will be interesting to put that code in, because we want the program to use all its “smart” approaches before going to the tree trimmer.
The code could use a good cleaning now that I’m at a green bar again, and I’d really like to reduce or eliminate some of the procedural code, and I’d like to reduce the repeated calculation of the row indexes, which aren’t even cached.
Finally, it seems like it would be prudent to check the proposed solution for validity, either in the test or in the game code. (Hmm, should we rename that to puzzle?)
I think I’ll start with some simple review of the code and a little clean up, to warm up my fingers, then see what comes up for me.
Code Review
Look at the previous article for the current code. I’ll paste anything that’s particularly interesting in here as well.
One thing I’m noticing is the little procedural patches of code in the game, for producing a row or column’s cell values, by producing a collection of indexes, and then pulling out the cells. That code is very low level, compared to the code that looks for possible values, or does the solution. Those methods are focused more on game aspects, the former ones are focused more on manipulating the elements of the game. That’s suggesting to me that we have at least two objects to think about here, one that supports the cells and rows and columns, and one that deals with game aspects like solving and evaluating what to do.
I need to extract a class. The choice is whether to extract the strategic stuff and leave the grid stuff, or vice versa. I am inclined to want to extract the grid-related work and leave the rest, but it seems that it might be less work moving in the other direction. In a sense, it doesn’t matter much, so I’m inclined to start whichever way offers the most obvious first move.
The @cells variable is an array, and we manipulate it using procedural array code. Most of the code now goes through the cell_value method. So it might be that we can create a new object, say, Grid, and use that to support the cell array, pushing more and more function to it. I’ll try that. The first bit is easy enough:
class Game
...
def initialize(number_array)
@grid = Grid.new(number_array)
end
def cell_value(cell_number)
@grid.cell_value(cell_number)
end
def set_cell(cell_number, val)
@grid.set_cell(cell_number, val)
end
...
end
class Grid
def initialize(number_array)
@cells = number_array.collect { | value | Cell.new(value) }
end
def cell_value(cell_number)
@cells[cell_number].value
end
def set_cell(cell_number, val)
@cells[cell_number].value= val
end
end
This little change just seemed like a good step to me: my thinking was as described above. But now the Grid seems to me to be a nice place to stand, to put other bits of functionality. It seems to me that the Grid, not the Game, should return the row values, column value, and square values. I’ll move them over, one at a time. While I’m at it, I’ll do a tiny bit of renaming, to row_values, for example. We’ll go from this in Game:
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
… to this:
def possible_values(cell_number)
[1, 2, 3, 4, 5, 6, 7, 8, 9] -
@grid.row(row_containing(cell_number)) -
column(column_containing(cell_number)) -
square(square_containing(cell_number))
end
… by adding to Grid like this:
def row(row_number)
row_start = row_number*9
collect_values row_start..row_start+8
end
def collect_values index_collection
index_collection.collect { | c | cell_value(c) }
end
Now I’d like not to have to calculate the row number in Game, but do it in Grid:
def possible_values(cell_number)
[1, 2, 3, 4, 5, 6, 7, 8, 9] -
@grid.row_for_cell(cell_number) -
column(column_containing(cell_number)) -
square(square_containing(cell_number))
end
We’ll do that:
class Grid
def initialize(number_array)
@cells = number_array.collect { | value | Cell.new(value) }
end
def cell_value(cell_number)
@cells[cell_number].value
end
def set_cell(cell_number, val)
@cells[cell_number].value= val
end
def row_containing(aCell)
aCell / 9
end
def row_for_cell(cell_number)
row(row_containing(cell_number))
end
def row(row_number)
row_start = row_number*9
collect_values row_start..row_start+8
end
def collect_values index_collection
index_collection.collect { | c | cell_value(c) }
end
end
A couple of other things broke. I changed one test to refer to Grid instead of game, to reflect the fact that Game no longer does the row stuff:
def test_row_containing
@grid = Grid.new([])
assert_equal(0, @grid.row_containing(0))
assert_equal(0, @grid.row_containing(8))
assert_equal(1, @grid.row_containing(10))
assert_equal(2, @grid.row_containing(20))
assert_equal(3, @grid.row_containing(30))
assert_equal(4, @grid.row_containing(40))
assert_equal(5, @grid.row_containing(50))
assert_equal(6, @grid.row_containing(60))
assert_equal(7, @grid.row_containing(70))
assert_equal(8, @grid.row_containing(80))
end
test_row_three and test_row_eight also failed when I tried to remove the row method from Game. In the long run, they’ll need a similar fix, to refer to the Grid, but for now I think I’ll implement a grid-fetching method on Grid, and just call through the Game to keep those running. Then I’ll take a look and see whether I want to start testing the Grid directly … or differently:
def test_row_three
assert_equal([27, 28, 29, 30, 31, 32, 33, 34, 35], @game.grid.row(3))
end
def test_row_eight
assert_equal([72, 73, 74, 75, 76, 77, 78, 79, 80], @game.grid.row(8))
end
That gets the tests running. The same thing will happen when I move column and square. Column is next:
def possible_values(cell_number)
[1, 2, 3, 4, 5, 6, 7, 8, 9] -
@grid.row_for_cell(cell_number) -
@grid.column_for_cell(cell_number) -
square(square_containing(cell_number))
end
Implemented by:
def column_for_cell(cell_number)
column(column_containing(cell_number))
end
def column(column_number)
collect_values column_indexes(column_number)
end
def column_containing(aCell)
aCell % 9
end
def column_indexes(column_number)
(0..8).collect { | row | column_number+row*9 }
end
Again, I had to adjust some tests. The changes were all just to ask the @game for its grid: I’ll show you all of them later. Now to go for the square logic. Here’s the code change in Game:
def possible_values(cell_number)
[1, 2, 3, 4, 5, 6, 7, 8, 9] -
@grid.row_for_cell(cell_number) -
@grid.column_for_cell(cell_number) -
@grid.square_for_cell(cell_number)
end
And here are the Grid changes:
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 square_containing(aCell)
row_containing(aCell) / 3 * 3 + column_containing(aCell) / 3
end
def square(square_number)
collect_values square_indexes(square_number)
end
def square_for_cell(cell_number)
square(square_containing(cell_number))
end
This wasn’t entirely pretty, but it basically amounted to doing some move method refactorings over to Grid. Let me rearrange the methods a bit and show you all the code.
Grid Class
Let’s look at the Grid class. All the tests are running, but the changes aren’t very interesting. What I’m seeing in this class is too many little methods. (They were mostly all there in the Game class, but putting them into Grid has called my attention to them. I tried alphabetizing them to help with organization but that’s pretty weak. We need to think of something better.)
class Grid
def initialize(number_array)
@cells = number_array.collect { | value | Cell.new(value) }
end
def cell_value(cell_number)
@cells[cell_number].value
end
def collect_values index_collection
index_collection.collect { | c | cell_value(c) }
end
def column_containing(cell_number)
cell_number % 9
end
def column_for_cell(cell_number)
column_values(column_containing(cell_number))
end
def column_indexes(column_number)
(0..8).collect { | row | column_number+row*9 }
end
def column_values(column_number)
collect_values column_indexes(column_number)
end
def row_containing(cell_number)
cell_number / 9
end
def row_for_cell(cell_number)
row_values(row_containing(cell_number))
end
def row_values(row_number)
row_start = row_number*9
collect_values row_start..row_start+8
end
def set_cell(cell_number, val)
@cells[cell_number].value= val
end
def square_containing(aCell)
row_containing(aCell) / 3 * 3 + column_containing(aCell) / 3
end
def square_for_cell(cell_number)
square_values(square_containing(cell_number))
end
def square_indexes(square_number)
start_cell = square_upper_left(square_number)
square_offsets.collect { | offset | start_cell + offset }
end
def square_offsets
[0, 1, 2, 9, 10, 11, 18, 19, 20]
end
def square_upper_left(square_number)
first_row = square_number / 3 * 3
first_column = (square_number % 3) * 3
first_row * 9 + first_column
end
def square_values(square_number)
collect_values square_indexes(square_number)
end
end
We could declare some of these private, or move them to a private section, but that doesn’t seem to me to help much. Basically we’ve got three groups of code that do much the same thing: row, column, and square. They’re implemented basically the same way, but they appear multiple times.
This constitutes duplication, even though the code lines don’t look exactly alike. There are three kinds of groups of cells: rows, columns, and squares. (Remind me to change the name “squares” to “boxes” in accord with usual Sudoku terminology, but we’re in the middle of something else right now.) I’m inclined to conclude that we need a CellGroup object to support the single function of grabbing up a collection of cells and returning their value. A related idea on my mind is that we’re calculating those index collections over and over, and they ought to be cached.
But I’m also mindful that I’d like to start trying to solve harder puzzles, and adding more interesting strategies. There’s only an hour or two of programming in what has gone on lately, spread over a few days, but I’m still impatient to get on with the problem. Still, I’m sure that I’ll go faster building on better code, and there’s just a little more time before breakfast. So let’s see about building a CellGroup and using it.
I’m at a green bar, so this is a refactoring. I’m going to build a tiny object and move functionality into it from the Grid code:
CellGroup
A cell group will be called something like this, to begin with:
def column_values(column_number)
cell_group = CellGroup.new(column_indexes(column_number))
cell_group.values(@cells)
end
We’ll create a CellGroup on a set of indexes, and then ask it for the values of the cells it indexes. I’m not entirely sure whether CellGroups should know the Grid and call back to it, or whether we’d rather pass them the cells. For now, I’ll pass the cells. Now to make it work:
class CellGroup
def initialize(indexes)
@indexes = indexes
end
def values(cell_array)
@indexes.collect { | index | cell_array[index].value }
end
end
That works. I should be able to make the row and column methods work the same way now. One at a time, of course:
def row_values(row_number)
row_start = row_number*9
cell_group = CellGroup.new(row_start..row_start+8)
cell_group.values(@cells)
end
That works. Now for the square:
def square_values(square_number)
cell_group = CellGroup.new(square_indexes(square_number))
cell_group.values(@cells)
end
Still works. Now let’s look at what we have and what we can now improve:
class Grid
def initialize(number_array)
@cells = number_array.collect { | value | Cell.new(value) }
end
def cell_value(cell_number)
@cells[cell_number].value
end
def collect_values index_collection
index_collection.collect { | c | cell_value(c) }
end
def column_containing(cell_number)
cell_number % 9
end
def column_for_cell(cell_number)
column_values(column_containing(cell_number))
end
def column_indexes(column_number)
(0..8).collect { | row | column_number+row*9 }
end
def column_values(column_number)
cell_group = CellGroup.new(column_indexes(column_number))
cell_group.values(@cells)
end
def row_containing(cell_number)
cell_number / 9
end
def row_for_cell(cell_number)
row_values(row_containing(cell_number))
end
def row_values(row_number)
row_start = row_number*9
cell_group = CellGroup.new(row_start..row_start+8)
cell_group.values(@cells)
end
def set_cell(cell_number, val)
@cells[cell_number].value= val
end
def square_containing(aCell)
row_containing(aCell) / 3 * 3 + column_containing(aCell) / 3
end
def square_for_cell(cell_number)
square_values(square_containing(cell_number))
end
def square_indexes(square_number)
start_cell = square_upper_left(square_number)
square_offsets.collect { | offset | start_cell + offset }
end
def square_offsets
[0, 1, 2, 9, 10, 11, 18, 19, 20]
end
def square_upper_left(square_number)
first_row = square_number / 3 * 3
first_column = (square_number % 3) * 3
first_row * 9 + first_column
end
def square_values(square_number)
cell_group = CellGroup.new(square_indexes(square_number))
cell_group.values(@cells)
end
private :square_upper_left, :square_offsets, :square_indexes
end
class CellGroup
def initialize(indexes)
@indexes = indexes
end
def values(cell_array)
@indexes.collect { | index | cell_array[index].value }
end
end
We can remove the collect_values method, I’d think. Yes, that works.
What about that cell_value method now? It’s being called from some tests – I’ll leave it alone for now, but I’m feeling that those tests are too fine-grained. We’ll see. Relating to columns, we have these methods:
def column_containing(cell_number)
cell_number % 9
end
def column_for_cell(cell_number)
column_values(column_containing(cell_number))
end
def column_indexes(column_number)
(0..8).collect { | row | column_number+row*9 }
end
The column indexes are part of what we need to cache, and I’m thinking I’ll move those to some kind of factory methods on CellGroup. The methods column_for_cell and column_containing sound like they should be supported by a cell object that would know its row and its column. We might want to go there, but right now we’re working on an underlying object, the CellGroup. By that I mean that I expect that if a cell did know its row or column or box, we would implement those using CellGroup instances. But looking forward a bit, we can imagine that we might set up all the groups when we create a Game Grid, then as we create each Cell, tell it who its groups are. That ought to move some decision logic to the cell, which would be a good thing, since right now it’s nothing but a data holder.
Reviewing the row and square logic, we also don’t find much that we can move. So far, our CellGroup isn’t carrying much weight – just the value collecting capability. Let’s go further, making CellGroup handle creating a column. I can see two ways that I might want to do that. One is to add a class method to CellGroup, column(column_number) and move the supporting methods to be calss methods in CellGroup. The other is to build a subclass of CellGroup, Column, and have its new method just do the right thing.
Since I almost never create a subclass before I actually need it, let’s try that to see what trouble I get into. I’m going to change the column code in Grid to use a Column, instead of a CellGroup:
def column_values(column_number)
column = Column.new(column_number)
column.values(@cells)
end
Then Column, as a subclass of CellGroup:
class Column < CellGroup
def initialize(column_number)
super(column_indexes(column_number))
end
def Column.column_containing(cell_number)
cell_number % 9
end
def Column.column_for_cell(cell_number)
column_values(column_containing(cell_number))
end
def Column.column_indexes(column_number)
(0..8).collect { | row | column_number+row*9 }
end
end
Unfortunately, this breaks things, including our solver, which wants to know the column for a cell:
def possible_values(cell_number)
[1, 2, 3, 4, 5, 6, 7, 8, 9] -
@grid.row_for_cell(cell_number) -
@grid.column_for_cell(cell_number) -
@grid.square_for_cell(cell_number)
end
This is why we have tests. The column_for_cell method should never have been moved at all, nor should column_containing. I misread their meaning. In addition, the initialize method for Column is referring to column_indexes. Either that needs to refer to Column.column_indexes, or we need to make the method an instance method. I think it should be a class method, so we’ll do it this way:
class Column < CellGroup
def initialize(column_number)
super(Column.column_indexes(column_number))
end
def Column.column_indexes(column_number)
(0..8).collect { | row | column_number+row*9 }
end
end
Tests run. We’ve moved one method from Grid to Column: that’s good. But I had hoped for more. Maybe that was just too big a bite, but I’m getting the feeling that I’m confused. We’re here to improve the code, so it’s not a surprise that it might be confusing us, but I’m hoping for more. I think that for now, I’ll do the same thing with Row and Square, and see what condition that leaves Grid in. Here’s Row:
def row_values(row_number)
row = Row.new(row_number)
row.values(@cells)
end
class Row < CellGroup
def initialize(row_number)
row_start = row_number*9
super(row_start..row_start+8)
end
end
Pretty simple, because the row indexes are so easy to compute. Irritates me, though, that it doesn’t look the same. For now, Square:
def square_values(square_number)
square = Square.new(square_number)
square.values(@cells)
end
And the implementation:
class Square < CellGroup
def initialize(square_number)
super(Square.square_indexes(square_number))
end
def Square.square_indexes(square_number)
start_cell = Square.upper_left(square_number)
Square.offsets.collect { | offset | start_cell + offset }
end
def Square.offsets
[0, 1, 2, 9, 10, 11, 18, 19, 20]
end
def Square.upper_left(square_number)
first_row = square_number / 3 * 3
first_column = (square_number % 3) * 3
first_row * 9 + first_column
end
end
The addition of those new CellGroup-based classes has moved a lot of code out of grid, as we’ll see in a moment. It has centralized the creation of the specialized group types, Row, Column, and Square, into separate classes, reflecting the similar structure and different details. I think it’s a righteous use of subclassing. Some may disagree, and I’ll hope to hear from them. For now, let’s review the code, and have breakfast.
class Grid
def initialize(number_array)
@cells = number_array.collect { | value | Cell.new(value) }
end
def cell_value(cell_number)
@cells[cell_number].value
end
def column_containing(cell_number)
cell_number % 9
end
def column_for_cell(cell_number)
column_values(column_containing(cell_number))
end
def column_values(column_number)
column = Column.new(column_number)
column.values(@cells)
end
def row_containing(cell_number)
cell_number / 9
end
def row_for_cell(cell_number)
row_values(row_containing(cell_number))
end
def row_values(row_number)
row = Row.new(row_number)
row.values(@cells)
end
def set_cell(cell_number, val)
@cells[cell_number].value= val
end
def square_containing(aCell)
row_containing(aCell) / 3 * 3 + column_containing(aCell) / 3
end
def square_for_cell(cell_number)
square_values(square_containing(cell_number))
end
def square_values(square_number)
square = Square.new(square_number)
square.values(@cells)
end
end
class CellGroup
def initialize(indexes)
@indexes = indexes
end
def values(cell_array)
@indexes.collect { | index | cell_array[index].value }
end
end
class Column < CellGroup
def initialize(column_number)
super(Column.column_indexes(column_number))
end
def Column.column_indexes(column_number)
(0..8).collect { | row | column_number+row*9 }
end
end
class Row < CellGroup
def initialize(row_number)
row_start = row_number*9
super(row_start..row_start+8)
end
end
class Square < CellGroup
def initialize(square_number)
super(Square.square_indexes(square_number))
end
def Square.square_indexes(square_number)
start_cell = Square.upper_left(square_number)
Square.offsets.collect { | offset | start_cell + offset }
end
def Square.offsets
[0, 1, 2, 9, 10, 11, 18, 19, 20]
end
def Square.upper_left(square_number)
first_row = square_number / 3 * 3
first_column = (square_number % 3) * 3
first_row * 9 + first_column
end
end
There’s still a lot of code in Grid, but it is mostly either returning values, which is clearly the Grid’s job, or it’s describing the structure of the Grid, which is also the Grid’s job. The fact that Grid has two jobs is a bit concerning, and we’ll see about that soon. We’ve moved in two steps, first creating the CellGroup class to remove duplication, then the Column, Row, and Square, which improve communication and also serve to increase the cohesion of the Grid class. The work was simple, done a step at a time, and leaves the world a better place.
Feel free to comment via email or on the lists. For now … it’s time to hang out with my brothers and eat things.