Sudoku: A Clue

Tomas provides a clue. Whatever might we do with it? Ideas, experiments, and a decision not to go ahead with the ideas … yet.

The Clue

On Mastodon, Tomas points out:

@RonJeffries I think your heuristic of available or permissible values could be smarter.

For example, in the top left subgrid, there’s only one open square that allows a 6 - the top right cell in that subgrid (I think it’d have index 2 in your string representation). All other open cells in that subgrid “see” a 6 in either their column or row, or both.

So a human solver [wc]ould start by putting a 6 there, but your code thinks almost any number is possible.

Here’s the chunk Tomas refers to:

Now that it has been pointed out, it is easy enough for us to see that Tomas is correct, that top-right cell is the only one in the sub-grid that can contain a 6, and we should plug it in.

Now in fairness to the machine, a human solver would not have the list of all the possible values, and would have to do a lot of checking to observe the uniqueness … unless she were scanning that area asking where she might put a six, in which case it would be pretty clear from the original puzzle:

There can be no six in the first column, nor second row (column 0 and row 1 in my notation), which leaves only the possibility Tomas identifies.

My Research

Ive done a bit of reading on human approaches to solving Sudoku, and there are some amazing rules that have been observed, with names like X-wing, Naked Pairs (not as interesting as it sounds), Hidden Pairs, Swordfish, and many more. At a single reading, most of these were not obvious to me, and I can’t imagine how anyone could remember them all.

It might be interesting to implement some of these, for small values of “might” and “interesting”, but that’s not for today. Our brute force solver was what we set out to do, and … I can already feel it coming over me, thinking that one way to learn these strategies would be to implement them in code … get thee behind me Sudoku, thou foul fiend!

Back to Tomas’ observation. How might we formulate the idea a bit more formally?

How about this

If in any Component (row, column sub-grid), considering the available values at each location, if there is any value that appears exactly once, it must be assigned at that location.

Or this

Given a list of the available values for each position in a Component, eliminate from each location, all the values that occur at another location … no, that seems worse.

I should mention that I like to think about little algorithms this way, in words rather than code, because it lets me chunk ideas that don’t pop out immediately as code.

This?

Given a component, consider the union of the available values at each position. For each element of the union, determine how many of the individual sets contain that value. If there is only one, that value must be assigned at that location.

This makes me wonder about symmetric difference. The symmetric difference of two sets consists of all the elements that are in one of the sets but not the other. SymDif of {1,2,3} and {2,3,4} is {1,4}. Would the symmetric difference of all the sets be interesting?

Let’s find out.

    def test_symmetric_difference(self):
        s1 = {1, 3, 8, 9}
        s2 = {2}
        s3 = {1, 3, 5, 6, 8, 9}
        s4 = {1, 8, 9}
        s5 = {1, 5, 9}
        s6 = {1, 5, 8, 9}
        s7 = {1, 3, 9}
        s8 = {7}
        s9 = {4}
        diff = s1 ^ s2 ^ s3 ^ s4 ^ s5 ^ s6 ^ s7 ^ s8 ^ s9
        assert diff == {2, 3, 4, 5, 6, 7}
        diff = s1 ^ s3 ^ s4 ^ s5 ^ s6 ^ s7
        assert diff == {3, 5, 6}

OK, those results aren’t helpful. And yet, it seems to me that there’s something in the idea.

Suppose we did this:

    def test_pairwise_symmetric_difference(self):
        s1 = {1, 3, 8, 9}
        s2 = {2}
        s3 = {1, 3, 5, 6, 8, 9}
        s4 = {1, 8, 9}
        s5 = {1, 5, 9}
        s6 = {1, 5, 8, 9}
        s7 = {1, 3, 9}
        s8 = {7}
        s9 = {4}
        p1 = s3 ^ s1
        p2 = s3 ^ s2
        p4 = s3 ^ s4
        p5 = s3 ^ s5
        p6 = s3 ^ s6
        p7 = s3 ^ s7
        p8 = s3 ^ s8
        p9 = s3 ^ s9
        result = p1 & p2 & p4 & p5 & p6 & p7 & p8 & p9
        assert result == {6}

Ha! Gotcha!

We can do better:

    def test_better_symmetric_difference(self):
        s1 = {1, 3, 8, 9}
        s2 = {2}
        s3 = {1, 3, 5, 6, 8, 9}
        s4 = {1, 8, 9}
        s5 = {1, 5, 9}
        s6 = {1, 5, 8, 9}
        s7 = {1, 3, 9}
        s8 = {7}
        s9 = {4}
        others = s1 | s4 | s5 | s7 | s7
        result = s3 ^ others
        assert result == {6}

We need not to include any other singletons. That makes me suspect that my preceding test is probably order dependent.

I’m beginning to think that this line of thought is a dead end, for a few reasons. First of all, for most readers, a complex set expression is going to be difficult to understand. Second, if I’m right about one of my tests being order dependent, the ideas are error prone even for me, and I am slightly more adept with set theory than some. Third, an algorithm like this seems, if not better, at least more clear:

for i in range(9):
	if i_occurs_only_once_in(component):
		set_the_corresponding_position_to_i()

Hold on here, bunkie

Let’s back off a bit and think about this. As things stand, we only really calculate the available values for a single cell, the one we are currently trying in our recursion. We only created that matrix of available values because I wanted to look at it.

If we were to calculate it every time, that would be pretty costly. We could, however, change our approach to calculate the set of available numbers once, at the beginning of things, and then merely update it every time we make a decision. Then we’d only update, oh, 27 of the 81. Three times faster. But might that lead to problems in backtracking?

Maybe not. But I think yes. We can’t just stuff the backtrack value into all the others, because it may have been outlawed by a component we’re not looking at.

But we do create a new puzzle instance every time. So …

1. Suppose the puzzle contains, not just the current solution state, but also, for each of the 81 cells, the available values for that cell. So when we do our new_puzzle_trying method, we’d
2. Create a new puzzle that copied all those values … then
3. Assign our guess … and then
4. Recompute the available values for the position’s components, which
5. Can be done either by removing the guess or recalculating, whichever is better.

Then what would we do? We could then go over every available set, or maybe just the ones in the changed components, looking for the Tomas pattern, to see if there is a value to force. I think we could just treat it as if it were given, or as if we guessed more than one value at a time. If subsequent recursion solves, the change was good. and if it does not, we’ll back out both our initial guess and any subsequent force values when we pop that puzzle off the stack.

I think it could work. My subjective odds are around 10 to 20 to one that we could do it.

Should we do it? Well, not right now. I’m considering whether it would be amusing to implement some of the human techniques of Sudoku, and it we go that way, this idea might possibly fit in. And it might not … it isn’t easy to do with the human mind, assuming without evidence that I have one on hand.

Anyway, an interesting thing to think about. In sum:

Summary

Collaboration is worth 20 IQ points, maybe more. Another brain on the effort, even for a few moments, can provide insights, answers, even questions that are very helpful.

Imagining solutions in somewhat high-level terms has value. I find it useful to think about aggregates, chunks, collections, sets … and imaginary operations on those aggregates.

Programming by intention, such as with this “code”:

for i in range(9):
	if i_occurs_only_once_in(component):
		set_the_corresponding_position_to_i()

… is valuable both as pseudo-code to firm up an idea, but also quite valuable because often we can just fill in the blanks and make it work. By its nature, it tends to create chunked ideas that we can implement.

And often … not doing a thing is as valuable as doing it.

The trick, of course, is in deciding. And that takes practice … and that’s why I practice all the time.

See you next time!