Sudoku 4: Disaster Narrowly Averted

The program reached an impossible state during the first test of the algorithm that I turned loose. I thought I had made a mistake, but it turned out I had not. Well, not a coding mistake.

Planning Next Steps

It’s time to decide which direction to go. The Game knows how to find a constrained cell, and knows what value it would like to put into that cell. That suggests that a sufficiently easy game, one that is constrained all the way, can now be solved. One possibility, and it’s a tempting one, is to solve a game. That is, after all, the story.

On the other hand, we know that the “real” story is to build Sudoku and learn about objects, how to represent the strategies, and so on. The idea was that Sudoku is a good example of how to use TDD well. As such, I’m as interested in getting a “good” program as I am in getting “done”. Maybe more so, since I really don’t need any Sudoku solutions, and I do need to be good at my job, which involves programming.

I think, though, that I can’t resist going for the solution. Let’s see what happens.

A Constraint-based Solution

I’m assuming that some puzzles are solvable by just repeatedly finding cells that have only one possible result, and filling in that result, repeating until done. I’m further assuming, or at least hoping, that my current “given” puzzle is one of those. If it is, I should be able to write the solve method quickly. The question is how to test it. I need a method “solved?” to tell me whether I’m done. I’ll start with a simple definition and beef it up later.

Begin with a test.

  class GameTest < Test::Unit::TestCase

    def setup
      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)
    end

    def test_first_game     
      assert_equal(23, @game.first_constrained)
      assert_equal(1, @game.proposed_value(23))
    end

    def test_solved_says_no
      assert_equal(false, @game.solved?)
    end
  end

I’ve refactored my GameTest class to have a setup, and added a new test with a call to solved?. I’ll implement that to return true, to give me a red bar, then implement a simple version. That turns out to be:

    def solved?
      collect_values(0..80).all? { | value | value > 0 }
    end

I’m just looking to see whether all the cells have a solution, not whether the solution is fully valid. That will do for now. Now I’ll test my test_game, which is not solved because its first element is zero, and then I’ll set its first element non-zero and see if it shows up as solved.

    def test_fake_completed_game
      givens = [
        1, 1, 1, 1, 1, 1, 1, 1, 1,
        1, 1, 1, 1, 1, 1, 1, 1, 1,
        1, 1, 1, 1, 1, 1, 1, 1, 1,
        1, 1, 1, 1, 1, 1, 1, 1, 1,
        1, 1, 1, 1, 1, 1, 1, 1, 1,
        1, 1, 1, 1, 1, 1, 1, 1, 1,
        1, 1, 1, 1, 1, 1, 1, 1, 1,
        1, 1, 1, 1, 1, 1, 1, 1, 1,
        1, 1, 1, 1, 1, 1, 1, 1, 1
      ]
      assert_equal(true, Game.new(givens).solved?)
    end

That passes. Now let’s write a test that asks us to solve the game:

    def test_solve_given_Game
      assert_equal(false, @game.solved?)
      @game.solve
      assert_equal(true, @game.solved?)
    end

With an empty definition of solve, that fails on the second assert. Now to write solved:

    def solve
      while solve_one_cell
      end
    end

    def solve_one_cell
      cell_number = first_constrained
      if (cell_number == nil) 
        return false
      end
      set_cell(cell_number, proposed_value(cell_number))
    end

    def set_cell(cell_number, val)
      @cells[cell_number].value= val
    end

Yikes!! The test fails, on the 80th cell in the game. By inspection, I can see that the lower right corner, still empty, has no possible value! But I need to get to work … I’ll have to return to this tonight.

Stalking the Problem

I thought about the problem off and on today, just a little bit. I couldn’t see any way that this simple solver could be wrong — but I also know what it means when a programmer says there’s no way his program could be wrong.

So I decided to set a trap. I extended the solver part of the code so that after setting each new value, it checks to see if the game is still solvable, using just a very simple test: does there exist a cell in the game such that it’s blocked and can contain none of the numbers from 1-9. I ran the problem and it actually failed fairly early … the matrix was less than half full and it had already blocked.

I looked at the code, looked at the last move it had made, and it all looked OK. So I decided that I would go back to websoduku.com and see whether my solution looked like the solved version of the original puzzle. I figured I’d let the program make one move at a time, and see if websoduke agreed with me.

So the first thing I did, of course, was check to see whether my givens equal the givens of the game on websoduku … and they didn’t. I had mis-transcribed one number!

I changed the number to the original, ran the tests, and they all ran, including my solve_given_Game test up above. The program works, and it was working just fine before I said Yikes! up above. I’m greatly relieved. I’m not sure whether I should back out my impossibility-checking code, or whether to leave it in now that it’s written. I didn’t TDD it, I just slammed it in as debugging code. It’s just a loop with a bunch of checks in it, and a print.

I guess I’ll leave it for now, for you to look at if you care to. The bottom line is that the program works. I’ll retrospect in the next article. For now, know this: I believe the program can solve any game where there always exists at least one square that is forced. The simplest strategy is implemented, and I’m sure it works. I’ll test a bit more, of course, but I think we’re good so far.

What I’d like to do pretty soon … maybe next … is to clean up this code. I’ve seen some pretty procedural code among the community who are working this problem right now, and I’d like to do better. And, of course, I’d like to toss in a couple of new strategies..

Speaking of which, it has been pointed out to me that what I “concluded” in that sketch in the preceding article is flat wrong. I’m not sure what I saw when I was fiddling with a game, but that picture doesn’t represent a true observation about the game. Nice catch, folks!

Here’s the code, just in case … it’s not better or more interesting, it’s just here for the record. I’ll just include the Game, everything else is the same.

Code With the Debug Pieces In It

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

    def solved?
      collect_values(0..80).all? { | value | value > 0 }
    end

    def solve
      while solve_one_cell
      end
    end

    def solve_one_cell
      cell_number = first_constrained
      if (cell_number == nil) 
        return false
      end
      proposed = proposed_value(cell_number)
      set_cell(cell_number, proposed)
      if (!possible)
        puts "Game just became impossible"
        puts "I played #{proposed} at #{cell_number} = #{cell_number / 9}, #{cell_number %9}"
        print_game
      end
      return true
    end

    def set_cell(cell_number, val)
      @cells[cell_number].value= val
    end

    def possible
      (0..80).each do
        | cell_number |
        if (cell_value(cell_number) == 0 && !cell_possible(cell_number))
          return false
        end
      end
      return true
    end

    def cell_possible(cell_number)
      if possible_values(cell_number).length == 0
        puts "impossible at #{cell_number} = #{cell_number / 9}, #{cell_number %9}"
        return false
      end
      return true
    end

    def print_game
      puts
      (0..8).each do
        | row |
        (0..8).each do
          | col |
          print cell_value(row*9+col), ' '
        end
        puts
      end
    end
  end

Posted on:

Written by: Ron Jeffries

Categorization: Articles

Recent Articles

Issues with SAFe

Recent Twitter conversations inspire me to pull out some of my concerns with SAFe and talk about them.

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.

SAFe – Good But Not Good Enough

I recently took the SAFe SPC training. My bottom line assessment is that it will be a marketing success, organizations trying it will see improvement, and some will see great improvement. And I don’t like it.