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