Sudoku 4: Disaster Narrowly Averted
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