Sudoku: Intelligence?
Let’s try to put some intelligence up in this thing. Not artificial, mind you, though it will involve code. Spoiler: Works well and we learn a bit.
So, as the Tour de France guys all say, yeah. Yeah, let’s see about putting some of the human reasoning techniques into our little program. My thinking, and I assure you that it is not artificial, is that if we do some analysis of the puzzle, we might be able to fill in some blanks more directly than via searching, and, if we can, we’ll probably reduce the search space quite a lot.
I expect that at least for the time being, we’ll keep our existing solver as the last resort. It basically works by trial and error, mostly error. I’m imagining a method that, given a partially-solved puzzle, applies whatever techniques we can find that will tell us specific values for cells in the puzzle. When we run out of ideas, we’ll select a cell o guess at, and recur. Then we run our “smart” analysis on the new puzzle, rinse repeat.
I think that the hardest part of this scheme will be coming up with examples for our tests, and most of the analyses we’ll be doing will surely need testing. And, given my propensity for what we in the trade call “human error”, I’ll do well to test the ones that don’t need testing, should any turn up.
Let’s begin by seeing how this idea might plug in. I am thinking that we’ll have a new class to manage all this, and that it may have associated classes to help with specific analyses. And unless I miss my guess, it will be clear where to put it. Here’s relevant code from Solver:
class Solver:
solver_count = 0
def __init__(self, puzzle):
Solver.solver_count += 1
self.puzzle = puzzle
def solve(self) -> Puzzle | None:
if self.puzzle.is_filled_in:
return self.puzzle
for new_puzzle in self.puzzle.find_next_puzzles():
solved_puzzle = Solver(new_puzzle).solve()
if solved_puzzle:
return solved_puzzle
return None
Hm, well, surely it will go in there somewhere. What does find_next_puzzles look like? I hope it’s a generator.
class Puzzle:
def find_next_puzzles(self):
guesses = self.possible_answers()
Puzzle.guess_count += len(guesses)
puzzles = (Puzzle.new_puzzle_trying_guess(self, guess) for guess in guesses)
return puzzles
@classmethod
def new_puzzle_trying_guess(cls, puzzle, guess, position=None):
if position is None:
position = puzzle.guess_position
old = puzzle.game
new = old[:position] + guess + old[position+1:]
return cls(new)
Good, the result of find_next_puzzles is a generator, since it is enclosed in parens, not square brackets, which means it won’t create a puzzle until it’s actually asked to do so.
I think we’ll do well to keep all the solving in Solver, perhaps like this:
def solve(self) -> Puzzle | None:
if self.puzzle.is_filled_in:
return self.puzzle
for new_puzzle in self.puzzle.find_next_puzzles():
techniques = SudokuTechniques(new_puzzle)
improved_puzzle = techniques.apply()
solved_puzzle = Solver(improved_puzzle).solve()
if solved_puzzle:
return solved_puzzle
return None
Curiously, this won’t compile, but if we do this, we should go green.
class SudokuTechniques:
def __init__(self, puzzle):
self.puzzle = puzzle
def apply(self):
return self.puzzle
We are green and commit: initial SudokuTechniques class does nothing.
So that’s nice. Now, my reasoning is this: we have taken a new puzzle from the puzzle’s list of possible guesses in some cell. We do not know what cell that is, but it is filled in. Anything we reason about now is tentative: if that guess, or any preceding guess on the stack, is wrong, we’ll come to a point where there are no remaining things to guess, and that level will return None, and all the changes we made applying techniques will be discarded. So we can modify this puzzle with impunity. If we make it easier to solve, our changes will be included when it ultimately gets solved. If it can’t be solved, as given, we’ve wasted some time but the recursion popping up will discard our well-intended but wasted work.
Let’s try to create a technique. The most obvious one, at least to me, is what I’ll call “force”. If we calculate the possible answers for an unsolved position, and there is only one, we can fill it in. I am tempted just to code that up, it’s so easy.
An issue comes to mind: Puzzle class can create a new puzzle, setting a position. It cannot edit the string that defines the puzzle. So the only “fair” way we can do this thing is to let it create a new puzzle each time we find a force. (Obviously we can also come up with a way to edit the string and even make sure it only happens in one place.) But, you know, I think the fact is that we don’t want our code to know about the string. Puzzle knows that and no one else should. We might even want to change it.
We’ll allow the creation for now.
Against my worst judgment, which is that I could just code this up, let’s see if we can devise a test.
Seems we’re going to want a new test file for this. I’ll create it now.
class TestTechniques:
def test_hookup(self):
assert 2 + 1 == 4
That fails as intended, and I fix it:
class TestTechniques:
def test_hookup(self):
assert 2 + 2 == 4
Now, what do we want to test? I think we can sketch it:
def test_force(self):
has_force = [
'000000000',
'000000000',
'000000000',
'000000000',
'000000000',
'000000000',
'000000000',
'000000000',
'000000000',
]
puzzle = Puzzle.from_list(has_force)
techniques = SudokuTechniques(puzzle)
force_point = 0
force_value = '9'
applied = techniques.apply()
assert applied.game[force_point] == force_value
None of the blanks are filled in, of course, so we have a failing test. How can we force a 9 into position zero?
Here’s one way:
def test_force(self):
has_force = [
'024680000',
'100000000',
'300000000',
'500000000',
'700000000',
'000000000',
'000000000',
'000000000',
'000000000',
]
puzzle = Puzzle.from_list(has_force)
techniques = SudokuTechniques(puzzle)
force_point = 0
force_value = '9'
applied = techniques.apply()
assert applied.game[force_point] == force_value
Let’s see if we can make this pass.
class SudokuTechniques:
def __init__(self, puzzle):
self.puzzle = puzzle
def apply(self):
self.force()
return self.puzzle
def force(self):
available = self.puzzle.possible_answers(0)
if len(available) == 1:
self.puzzle = Puzzle.new_puzzle_trying_guess(self.puzzle, available[0], 0)
That passes just fine. Let’s do a harder test, see if we can drive out the loop.
def test_force_loop(self):
has_force = [
'024680010',
'100000000',
'300000030',
'500000050',
'700000090',
'000000000',
'000000000',
'000000000',
'000000000',
]
puzzle = Puzzle.from_list(has_force)
techniques = SudokuTechniques(puzzle)
force_point_1 = 0
force_value_1 = '9'
applied = techniques.apply()
assert applied.game[force_point_1] == force_value_1
force_point_2 = 16
force_value_2 = '7'
assert applied.game[force_point_2] == force_value_2
I think I’ve done that right. It fails as expected. Let’s improve our force method.
OK, I’ve done that but the test is wrong, there are lots of possibilities for cell 16. Improve the test:
has_force = [
'024680010',
'100000000',
'300000020',
'500000030',
'700000040',
'000000050',
'000000060',
'000000080',
'000000090',
]
So the force tests pass now. However, several others do not, because we are now smarter than we were. Also let’s use the puzzle size in our new method:
def force(self):
for cell in range(self.puzzle.line_size*self.puzzle.line_size):
if self.puzzle.game[cell] == '0':
available = self.puzzle.possible_answers(cell)
if len(available) == 1:
self.puzzle = Puzzle.new_puzzle_trying_guess(self.puzzle, available[0], cell)
Actually, that makes all the tests run … including the big one. Let’s see if our guesses were reduced.
The 9x9 prints this:
Solver.solver_count=3316
Puzzle.puzzle_count=26276
Puzzle.guess_count=3332
Wasn’t that like 78,000 before? Let me comment out our improvement and see what we get.
Solver.solver_count=78431
Puzzle.puzzle_count=78430
Puzzle.guess_count=78449
Wow, we’re very clever aren’t we? We only did about 3000 recursions instead of 78,000, and created 26,000 puzzles instead of 78,000.
We could, of course, reduce the 26,000 by editing the string in place, but I have a rule, whose number I forget, about trusting your language’s object creation and destruction code to be reasonably efficient.
I’d be a fool not to stop while I’m winning. Commit: SudokuTechnique.force reduces hard 9x9 recursions from 78,000 to 3000. Woot!
Let’s sum up and get the flock out of here.
Summary
We’ve found what seems like a perfect place to put specialized solving techniques, right after creating a new puzzle to solve. One slight issue is that as things stand, we will not solve an initial puzzle using only “techniques”, because we always guess first. Now that I realize that, I am less happy than I was two sentences ago, because it means that unless the first empty cell needs a ‘1’, we will waste up to 9 tries of the solver.
We can probably avoid that issue by moving where we call the techniques, and we’ll look at that next time.
Still, reducing recursions to 1/20th of what they were is nothing to sneeze at, whatever that means.
We actually managed to build some decent tests for the force technique, which is surely the simplest one we’ll ever encounter. I am expecting that tests for the other techniques may be difficult to write. We may at least find ourselves testing them independently.
That gives me an idea. Suppose that a technique was an object kind of thing. Then we might have a list of techniques and we could configure solvers with different lists, isolating solvers to be tested, or perhaps trying them in different orders.
And that makes me worry just a little bit … as coded today, the Solver always applies the techniques. Does that mean that some tests are no longer testing what we thought they were? I’ll bet it does. Why do I think that? Well, because some tests were failing and then I put in the line size check and they all passed. So I know we are running the force on all our tests. For example:
def test_full_3x3(self):
puzzle = Puzzle('103000001')
solver = Solver(puzzle)
solved = solver.solve()
assert solved.game == '123312231'
That test can be solved entirely using the force method. But we were trying to test the Solver’s recursion. So our current smarter solver is still working fine, but our tests do not show it.
I want a failing test to remind me of this. Let’s check how many solvers that test uses without force and then assert that.
def test_full_3x3(self):
Puzzle.puzzle_count = 0
Solver.solver_count = 0
puzzle = Puzzle('103000001')
solver = Solver(puzzle)
solved = solver.solve()
assert solved.game == '123312231'
assert Solver.solver_count == 10
assert Puzzle.puzzle_count == 10
Now turning the force back on:
> assert Solver.solver_count == 10
E assert 3 == 10
E + where 3 = Solver.solver_count
Perfect. We’ll commit the failing test as a reminder: Need to turn off techniques for early tests to be valid.
Naturally, I wouldn’t do that in prod. I’d have to put a sticky note on my monitor or something. No, I would not open a branch. I would not could not do that, Sam-I-Am.
We’ve learned a bit about how to do “smart” techniques, a bit about where to put them, and a bit about the need to configure them on or off. Nice!
We have a fine little start at applying “smart” techniques in our solver. It’s a good morning. See you next time!
P.S. No, this is not “AI”.