Sudoku: Whither?

The Naked Pairs (NAIAIS) technique seems to work. What should we do next? I feel that we should step away from the brute force solver.¹

The idea with the solution techniques is that they are strategies that humans and other sophonts might use in solving Sudoku puzzles. That’s entirely different from the Solver object, which is a barely sensible mostly just plain keep on guessing brute force solver. If a human tried to solve the puzzle like Solver does, it would take ages and use up a log of scratch paper. On my “hard” test puzzle, Solver makes something over 73,000 guesses to get the puzzle’s 81 numbers right.

And Solver cannot fail. If the puzzle has a solution, Solver will find it, subject only to the almost inconceivable² possibility that I’ve injected a defect into it. As such, if we are applying our human-style techniques to a puzzle, we should not fall back to the Solver. Instead, we should fail the test for that puzzle, which will tell us that we need a new strategy. And so on.

Design Thinking

So, at a guess, we’ll want a “HumanSolver” or “TechniqueSolver” that is used to apply Techniques, we’ll of course want tests for that, and we’ll need a suite of Sudoku puzzles. We’d like to have some easy ones and then a gradation of harder and harder ones, until the day comes—and that day may never come—when the next technique we might implement is not as shiny as whatever new problem catches my eye.³

Nearing a Plan

So, I think we need to begin building and working on a list like this:

Find at least one and preferably a pool of easy puzzles;
Start making tests that will drive out a new kind of Solver;
Make each of those tests run;
Rinse, repeat.

Naturally, we’ll typically write one test and make it run, then write another, although we might in principle allow ourselves to write more than one, though I can’t think why we would, and certainly sometimes a test turns out to be too difficult and we write a simpler one so that we can sneak up on the hard one.

A Round Tuit

I think I’ll make a new test file right now. No. After looking at what we have, I think I’ll just work in the existing test-techniques file, with the class TestTechniques. I tend to keep more tests together than some folks do, and, well, I don’t make recommendations but if I did, I wouldn’t recommend emulating me in this regard. So but anyway let’s find an easy Sudoku and start writing a test around it.

easy_1 = [
        '069015708',
        '500703240',
        '073000600',
        '090157380',
        '002096000',
        '000028001',
        '130002004',
        '000001527',
        '728000060',
    ]

I think I’m going to regret working in the same file so I’ll create a new test class and move it soon if not immediately.

class TestHumanSolver:
    easy_1 = [
        '069015708',
        '500703240',
        '073000600',
        '090157380',
        '002096000',
        '000028001',
        '130002004',
        '000001527',
        '728000060',
    ]

    def test_hookup(self):
        assert 2 + 2 == 4

To move this to a new file, I just select the class name and hit F6, which is Move. Done. Now let’s see about sneaking up on solving this easy puzzle. My guess is that we won’t even need NakedPairs for this one, but we will probably need more than whatever half techniques we have built up.

We’ll do the solving in place at first, move to classes as they begin to take shape.

    def test_easy_1(self):
        puzzle = Puzzle.from_list(self.easy_1)
        for i in range(1000):
            if puzzle.is_correctly_solved:
                break
        assert puzzle.is_correctly_solved

How do you feel about that break? I don’t think I’ve ever used one before, at least not this century. But it’s kind of like a guard clause.

The idea here is that if we knew we’d crack it, we’d do while not solved, but we don’t know that we’ll crack it, so we write a long but finite loop and if we fall out of it while still unsolved, the test fails.

Now we want to try our techniques. I guess that means we should look at what we have available. The field is pretty nearly bare. In addition to NakedPairs, which we surely need not apply but will anyway, we just have this:

class SudokuTechniques:
    only_one = 0

    def __init__(self, puzzle):
        self.puzzle = puzzle

    def apply(self):
        self.only_one_possible_value()
        self.only_one_possible_position()
        return self.puzzle

    def only_one_possible_value(self):
        changed = True
        while changed:
            changed = False
            for cell in self.puzzle.unknown_cells():
                available = self.puzzle.possible_answers(cell)
                SudokuTechniques.only_one += 1
                if len(available) == 1:
                    self.puzzle = Puzzle.new_puzzle_trying_guess(self.puzzle, available[0], cell)
                    changed = True

    def only_one_possible_position(self):
        pass

We see here that the convenient SudokuTechniques class applies the techniques that it knows, just once, and returns a possibly new puzzle. This will give us another chance to break out of the loop, this time with a failure. So let’s see …

Here’s what I have, with some prints that I just added.

    def test_easy_1(self):
        puzzle = Puzzle.from_list(self.easy_1)
        print()
        print(puzzle)
        for i in range(1000):
            old_puzzle = puzzle
            if puzzle.is_correctly_solved:
                break
            techniques = SudokuTechniques(puzzle)
            puzzle = techniques.apply()
            if puzzle is old_puzzle:
                break
        print(i)
        print(puzzle)
        assert puzzle.is_correctly_solved

The prints say:

<puzzle.Puzzle object at 0x105e9e4d0>
1
<puzzle.Puzzle object at 0x1046d33d0>

I think we need a better printout for our puzzles. Let’s do a really simple one:

class Puzzle:
    def __repr__(self):
        lines = []
        for line in range(9):
            lines.append(self.game[9*line:9*(line+1)])
        return '\n'.join(lines)

What confuses me most about this is that there has been a lot of solving going on, and yet the value of i is just one. Ah. That’s because our only live solution method, the one that finds forced cells, does all the ones it can see. So this puzzle is nearly solved by force.

I am slightly distressed because I don’t know the right solution to this thing, which suggests to me that I have to solve it, because the page I got it from 1) displays a random puzzle and b) took me to one of those fake Norton Virus trap pages. So I guess I have to solve it myself.

Oh, wait. I have a solver. :)

And the Solver does not solve the puzzle. I must have typed it incorrectly. I find a better site and replace the puzzle. My test file is now:

class TestHumanSolver:
    easy_1 = [
        '089005140',
        '300817006',
        '710604380',
        '043900000',
        '970000014',
        '000008730',
        '096402071',
        '400159002',
        '021700490'
    ]

    def test_hookup(self):
        assert 2 + 2 == 4

    def test_easy_1(self):
        puzzle = Puzzle.from_list(self.easy_1)
        solver = Solver(puzzle, apply_techniques=True)
        solved = solver.solve()
        print()
        print(puzzle)
        print()
        print(solved)
        for i in range(1000):
            old_puzzle = puzzle
            if puzzle.is_correctly_solved:
                break
            techniques = SudokuTechniques(puzzle)
            puzzle = techniques.apply()
            if puzzle is old_puzzle:
                break
        print(i)
        print(puzzle)
        assert puzzle.is_correctly_solved

The test passes. This must truly be an easy puzzle. My print says:

So apparently on this new site, easy really does mean easy, since just looking for forced values solved it. I am curious to see what happened. Let’s trace, just for fun:

Here’s part of the trace:

forced cell=8 = 7
forced cell=10 = 5
forced cell=16 = 2
forced cell=20 = 2
forced cell=22 = 9
forced cell=26 = 5
forced cell=35 = 8
forced cell=46 = 6
forced cell=47 = 5
forced cell=48 = 2
...

That makes sense to me. Earlier traces seemed to be solving 3 by force, first, which is not valid. Cell 3 doesn’t turn up in the list for quite a while.

What we have learned here, first of all, is that this easy_1 can be solved by simple forces alone. There is always a cell whose row, plus column, plus sub-grid contains eight of the nine possible values. Since our solver loops, it finds them all:

    def apply(self):
        self.only_one_possible_value()
        self.only_one_possible_position()
        return self.puzzle

    def only_one_possible_value(self):
        changed = True
        while changed:
            changed = False
            for cell in self.puzzle.unknown_cells():
                available = self.puzzle.possible_answers(cell)
                # print(f'{cell} {available}')
                SudokuTechniques.only_one += 1
                if len(available) == 1:
                    print(f'forced {cell=} = {available[0]}')  # trace
                    self.puzzle = Puzzle.new_puzzle_trying_guess(self.puzzle, available[0], cell)
                    changed = True

So we can assert on the only_one variable. The puzzle has only 39 empty cells, if my count is correct. Let’s assert:

        assert puzzle.is_correctly_solved
        assert SudokuTechniques.only_one == 39

Fails, gets 80. Oh, the count is ticked on each time through the loop, not just the ones we process. Change that:

    def only_one_possible_value(self):
        changed = True
        while changed:
            changed = False
            for cell in self.puzzle.unknown_cells():
                available = self.puzzle.possible_answers(cell)
                # print(f'{cell} {available}')
                if len(available) == 1:
                    SudokuTechniques.only_one += 1
                    # print(f'forced {cell=} = {available[0]}')
                    self.puzzle = Puzzle.new_puzzle_trying_guess(self.puzzle, available[0], cell)
                    changed = True

Now the test passes.

I’ve really not accomplished much this morning. I spent a lot of time that you don’t see here, looking for puzzles, typing them in, and chasing after that thing where it seemed to be solving cell 3 sooner than it should have. I got confused about how Solver works (and still am confused) and that slowed me down without any words appearing here. It’s time for a summary and a break.

Summary

Commit: steps toward human solver.

We’ve actually accomplished some useful things.

We’ve learned that our exiting SudokuTechniques object, with just its one technique, discovering cells with only one possible answer, can solve sufficiently simple problems.

We’ve learned that easy Sudoku might be too easy. We’ve found a source for solved puzzles that doesn’t try to trap our browser and scam us.

We’ve devised what will turn into a good way to test these “human” techniques: we can run the brute solver on the puzzle, and compare its answer to the techniques’ result. That may come in handy if our techniques make mistakes: comparing with the real solution could find the first mistake.

We have a sketch of how we might apply the techniques. As things stand, the SudokuTechniques object applies each technique once, in some order that we’ll define. Each technique can apply itself as many times as it wishes, as the only_one technique does. And then in the test, we create and apply the techniques over and over, until we solve or give up.

This will need refinement, but we have the basics in place.

I would frankly prefer to have had things go more smoothly, but they didn’t, and, unlike some times, when we know exactly where we went wrong, today I don’t know what happened. Things got a bit ragged, but we learned a lot and don’t have any really big concerns facing us.

I call that a win. See you next time!

Not As Interesting As It Sounds ↩
Yes, I do know what that word means. ↩
Knowing me, that day will in fact come. I already know what I’d like to work on next and am just holding off to see if anyone wants to join me. I work on what interests me, and when a problem ceases to interest me, I move to a new one. Frequent readers will have noticed. ↩