Sudoku 5: Objects Begin to Emerge

The code is beginning to ask for some help. We’re processing a simple array of cells instead of an object, and the classes don’t feel cohesive. Let’s push some methods off to new classes and see what happens.

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.

Posted on:

Written by: Ron Jeffries

Categorization: Articles

Recent Articles

Refactoring — Not on the backlog!

There has recently been a lot of noise on the lists, and questions at conferences, about putting refactoring “stories” on the backlog. This is invariably an inferior idea. Here’s why:


Ref01

When our project begins, the code is clean. The field …

Build it right to build the right thing

You can’t build the right product if you can’t build the product right.

I tweeted that this morning, in response to a Twitter-vibe that was flitting around. I’d like to follow it up here with a bit more meat.

The …

Estimate This! (or not)

My friends and colleagues in the #NoEstimates circles have some good ideas, as I've commented elsewhere. I'm left, though, with a couple of concerns.