Sudoku: Progress
We seem to have working code for hidden pairs. It is not yet a suitable object: more of a working prototype. Let’s step back half a step and assess where we are and what to do next. We narrowly avoid a bear bite.
In all too many real software shops, we would be under undue pressure to complete the “hidden pairs” story, so that we could take on whatever is next, so that we could ship the whole thing, so that they could start us on the next high-pressure effort. We would be offered no real slack time, no substantial opportunities to assess where we were, nor to improve our ability to deliver, even the next most important demands features they had in mind.
In such a shop, it would be to the advantage of the team, but also to the advantage of the company, if the team could learn to take very brief chunks of time to raise up their heads, look around, think a bit, and decide what to do. Even in a team that does get time for a weekly retrospective, too often that time turns into an hour or so of complaining about things that will never get fixed, with very little consideration of the things we might do to make our lives, and the code, better.
I propose to take just a few minutes here, to look around and decide what to do. I freely grant that at other idle moments in the evening and morning, I may have mused about things. But not deeply.
The idea of “notes” is a good one, I think. In many Sudoku apps where humans can solve the puzzle, the app provides the ability to put tiny numbers in the cells, indicating values that are possible for that cell. And that, of course, is the same idea as our Candidates and now, our Notes. We’ll review it shortly, not because we’re reviewing code but because we always read the code a bit before we change it, but my feeling is that the brand new Notes object was helpful.
Thinking just a bit more deeply, the notes are a property of the puzzle, not of a row, column, or box. We certainly can access them via those components, but the notes themselves reflect the situation as defined by all three components impacting that cell. So it makes sense, I think, to work toward our Notes object being focused on the puzzle. I think currently it is created by and focuses on a component.
In addition, Notes treats that component as its owner, and it has a pointer to that owner.
I generally find that when a collection element includes a pointer back to the collection, things tend to get complicated. So, if possible, I’d prefer that our Notes object won’t be directly tied to its owner, but, instead, will be passed the owner when it is needed. I honestly do not know whether this will be feasible. If we really want to hold on to a notes object and change its contents, at least as we do it today, it seems that we need to set it back into its owner.
Maybe we can have it be that the Puzzle has the Notes and the Notes are mutable, so we can erase a value from a Notes instance and not have to store a new one.
There’s one more issue that we may encounter: we currently create a ListEditor, I think it’s called, when we push down a copy of the puzzle in preparation for making a guess. That object saved us from having to copy 81 lists on a push. We’ll need to deal with that, if we do decide to make Notes a first-class object held on to by the Puzzle.
All this is just thinking, to bring issues forward in our mind, in preparation for whatever work we do this morning, so that when we get close to these issues, we are more prepared. Let’s choose some work.
- Note:
- The above design thinking, counting writing it up, took just 12 minutes. I think it will turn out to be worth it. And even on the highest-pressure teams, a few folks can grab a few minutes to work something out. They might have to look busy, but they can surely find the time.
I think we should work today on creating a new Technique, HiddenPairsTechnique, and using it as part of our puzzle-solving.
- Oh
-
Oh, that reminds me. I’ve been thinking that we should have two approaches to solving, one that just runs our brute guessing Solver, and one that uses the Techniques. I think, instead, what we’ll try is to run our Techniques until they run out of gas, and only then make a guess. We’ll consider that a bit of a failure for the techniques team, but, after all, it is quite simple to produce a Sudoku puzzle where guessing is the only possible approach. Such a puzzle isn’t considered good by Sudoku players, but it can happen.
-
Anyway, that’s kind of how the Solver works already, and we’ll bless that as the official way. I intend, before we get to the end of this series, to read in and try to solve a collection of puzzles, and when we do that, we’ll want to keep score of which techniques, including guessing, came into play. We’ll feel good about most of them, and bad about the guessing. All that is for another day.
Hidden Pairs So Far
We have tests that exercise our hidden pairs code, which is currently just running as naked functions in the test file. Here’s our most comprehensive test so far:
def test_hidden_pairs_sets_notes_class(self):
# https://www.sudokuwiki.org/Hidden_Candidates
puzzle_list = [
'000000000',
'904607000',
'076804100',
'309701080',
'708000301',
'051308702',
'007502610',
'005403208',
'000000000',
]
puzzle = Puzzle.from_list(puzzle_list)
row_0 = Component.row(puzzle, 0)
row_notes = row_0.notes()
for notes_a, notes_b in combinations(row_notes, 2):
comp = [notes for notes in row_notes if notes is not notes_a and notes is not notes_b]
pairs = hidden_pairs(notes_a, notes_b, comp)
if pairs:
notes = pairs[0]
notes_a.become(notes)
notes_b.become(notes)
assert row_0.candidates_at(7) == ['6', '7']
assert row_0.candidates_at(8) == ['6', '7']
We do not have, if memory serves, any code that runs over all the components in the whole puzzle for hidden pairs. We will have to devise that as part of what we work toward today.
Here we have the hidden_pairs function and its subordinate:
def hidden_pairs(notes_a, notes_b, complement):
if len(notes_a) < 2 or len(notes_b) < 2:
return []
# Is 2 correct here? Are the two required to be more than 2?
for value_1, value_2 in combinations(notes_a, 2):
if is_hidden_pair(value_1, value_2, notes_b, complement):
return [[value_1, value_2]]
return []
def is_hidden_pair(value_1, value_2, notes_b, complement):
# could be more efficient
pair_also_in_notes_b = value_1 in notes_b and value_2 in notes_b
n1_nowhere_else = all([value_1 not in c for c in complement])
n2_nowhere_else = all([value_2 not in c for c in complement])
return pair_also_in_notes_b and n1_nowhere_else and n2_nowhere_else
I’ll spare us the verbal description of these. We’ve been there and done that. They are tested and we are confident (p > 0.8) that they work as needed.
Let’s create a test for a new HiddenPairsTechnique. I’ll rip off the test from the one above and edit it as needed. I find copy-pasta to be OK in a case like this where we are happy to get the same result, just from some objects that don’t exist yet.
def test_hidden_pairs_technique(self):
# https://www.sudokuwiki.org/Hidden_Candidates
puzzle_list = [
'000000000',
'904607000',
'076804100',
'309701080',
'708000301',
'051308702',
'007502610',
'005403208',
'000000000',
]
row_0 = Component.row(puzzle, 0)
assert row_0.candidates_at(7) == []
assert row_0.candidates_at(8) == []
puzzle = Puzzle.from_list(puzzle_list)
technique = HiddenPairsTechnique(puzzle)
technique.apply()
assert row_0.candidates_at(7) == ['6', '7']
assert row_0.candidates_at(8) == ['6', '7']
We’ll fill in the starting values from the initial testing. I could look them up but I’m happy to do an approval on this situation.
Now let’s have the class. I’ll build it in the test file and move it later.
class HiddenPairsTechnique:
def __init__(self, puzzle):
pass
def apply(self):
pass
That’s enough to let me get the values for my first check. Oops, had the test set up wrong. Here we go:
puzzle = Puzzle.from_list(puzzle_list)
row_0 = Component.row(puzzle, 0)
assert row_0.candidates_at(7) == []
assert row_0.candidates_at(8) == []
technique = HiddenPairsTechnique(puzzle)
technique.apply()
assert row_0.candidates_at(7) == ['6', '7']
assert row_0.candidates_at(8) == ['6', '7']
I had the puzzle being initialized after referencing it. Now then, we discover:
Expected :[]
Actual :['2', '3', '4', '5', '6', '7', '9']
Right, plug that in and get the next one.
Expected :[]
Actual :['3', '4', '5', '6', '7', '9']
Plug that in and watch the test fail on the penultimate assertion.
Expected :['6', '7']
Actual :['2', '3', '4', '5', '6', '7', '9']
Perfect. Might have to do with the rather empty class. Let’s implement.
I think I’ll scarf up those two functions and make them (static) methods in the new Technique.
def hidden_pairs(self, notes_a, notes_b, complement):
if len(notes_a) < 2 or len(notes_b) < 2:
return []
# Is 2 correct here? Are the two required to be more than 2?
for value_1, value_2 in combinations(notes_a, 2):
if self.is_hidden_pair(value_1, value_2, notes_b, complement):
return [[value_1, value_2]]
return []
def is_hidden_pair(self, value_1, value_2, notes_b, complement):
# could be more efficient
pair_also_in_notes_b = value_1 in notes_b and value_2 in notes_b
n1_nowhere_else = all([value_1 not in c for c in complement])
n2_nowhere_else = all([value_2 not in c for c in complement])
return pair_also_in_notes_b and n1_nowhere_else and n2_nowhere_else
It seems that “all we have to do” now is iterate hidden_pairs for all components and all pairs within them. We have code that some of that. Anyway, by intention:
Hm. Do we really have no way of getting all the components? Let’s review the other likely techniques.
- Oh, wow.
- I just found the NakedPairsTechnique, which is aimed at a single component. and we have never actually used it in anger. Need to finish that up, close out the Jira. Make a note of that.
In SudokuTechniques class, we find this:
def get_all_components(self):
puzzle = self.puzzle
rows = [Component.row(puzzle, pos) for pos in range(0, 81, 9)]
cols = [Component.column(puzzle, pos) for pos in range(9)]
subs = [Component.sub_grid(puzzle, pos) for pos in [0, 3, 6, 27, 30, 33, 54, 57, 60]]
return cols + rows + subs
This, my friends, is what we call “feature envy”, which I consider a bit of a misnomer, but, well, things get names and that’s what we call this thing where a method on one class refers only to another class. In this case, puzzle. This method wants to be on Puzzle.
We’ll divert for a moment and provide it, because we want it too.
PyCharm, marvelous though it is, can’t help me here, or if it can, I can’t figure out how. We’ll just move the thing and fix it up.
class SudokuTechniques:
def fixed_a_lonely_one(self):
components = self.puzzle.all_components()
for component in components:
lonely_ones = component.get_lonely_ones()
for lonely_value, lonely_cell in lonely_ones:
self.puzzle = Puzzle.evolve_with_change(self.puzzle, lonely_value, lonely_cell)
return True
return False
class Puzzle:
def all_components(self):
rows = [Component.row(self, pos) for pos in range(0, 81, 9)]
cols = [Component.column(self, pos) for pos in range(9)]
subs = [Component.sub_grid(self, pos) for pos in [0, 3, 6, 27, 30, 33, 54, 57, 60]]
return cols + rows + subs
That’s a substantive change. I’ll commit that: create and use all_components in Puzzle.
I do not commit the unfinished test, of course. But now:
class HiddenPairsTechnique:
def __init__(self, puzzle):
self.puzzle = puzzle
def apply(self):
for component in self.puzzle.all_components():
self.check_component(component)
def check_component(self, component):
OK, how do we do check_component? We need to get set up to call this, multiple times:
def hidden_pairs(self, notes_a, notes_b, complement):
We have code in a test that tells me to do this:
def apply(self):
for component in self.puzzle.all_components():
self.check_component(component)
def check_component(self, component):
component_notes = component.notes()
for notes_a, notes_b in combinations(component_notes, 2):
complement = component.complement(notes_a, notes_b)
self.hidden_pairs(notes_a, notes_b, complement)
I had high hopes for this. Also, remind me to praise PyCharm. But not right now, because the test is still failing and I rather thought it would pass. Let’s see. Maybe we just haven’t connected all the wires yet.
> complement = component.complement(notes_a, notes_b)
E AttributeError: 'Component' object has no attribute 'complement'
Huh. I’da sworn I saw that in the code. Hallucination, I guess. Anyway, for now, jam it in thus:
def check_component(self, component):
component_notes = component.notes()
for notes_a, notes_b in combinations(component_notes, 2):
complement = [notes for notes in component_notes if notes is not notes_a and notes is not notes_b]
self.hidden_pairs(notes_a, notes_b, complement)
Still failing. I’m wishing I had taken a smaller step. What’s the test unhappy about now?
Expected :['6', '7']
Actual :['2', '3', '4', '5', '6', '7', '9']
Nothing happened. Let’s instrument with a print or two and see if it found something and didn’t record it, or didn’t find anything.
Oh, never mind. We just aren’t doing anything. hidden_pairs returns them. It doesn’t fix them up.
def check_component(self, component):
component_notes = component.notes()
for notes_a, notes_b in combinations(component_notes, 2):
complement = [notes for notes in component_notes if notes is not notes_a and notes is not notes_b]
pairs = self.hidden_pairs(notes_a, notes_b, complement)
if pairs:
notes = pairs[0]
notes_a.become(notes)
notes_b.become(notes)
Unfortunately, still same result. Now for the print.
found pairs=[['2', '3']]
found pairs=[['1', '8']]
Interesting. Maybe there are more than just our expected hidden pair in the puzzle. I notice that we are doing columns first, then rows, so I change all_components to do rows first, and we get this:
found pairs=[['6', '7']]
found pairs=[['2', '3']]
found pairs=[['1', '8']]
And the test still fails but in an interesting new way:
Expected :['6', '7']
Actual :['2', '3']
Ah. If we change a Notes, maybe we can’t just continue looping over the notes.
class Notes:
def __init__(self, component, pos):
self.owner = component
self.pos = pos
def __len__(self):
return len(self.owner.candidates_at(self.pos))
def __iter__(self):
return iter(self.owner.candidates_at(self.pos))
def become(self, values):
self.owner.set_candidates_at(self.pos, values)
That sure looks to me as if a subsequent reference to a given Notes that had been updated would see the updated values.
The mature thing to do right now would be to say “well, that didn’t work” and roll back. The best argument in favor of continuing a bit is that I don’t understand quite what is going on and getting more info before starting over has some merit. The downside is that we might find and fix the bug and miss out on a better idea. We’ll risk it.
What does the component do when it is created and when it updates? If it is caching values … that’s our problem.
class Component:
def __init__(self, puzzle, start, steps):
self.puzzle = puzzle
self.start = start
self.positions = [start + step for step in steps]
def notes(self):
return [Notes(self, pos) for pos in range(9)]
def candidates_at(self, position):
puzzle_cell_index = self.positions[position]
if self.puzzle.cell_at(puzzle_cell_index) != '0':
return []
else:
return self.puzzle.candidates.at(puzzle_cell_index)
That sure doesn’t look like caching values. Let’s see if we can instrument Notes to dump some information.
class Notes:
def puzzle_address(self):
return self.owner.positions[self.pos]
def become(self, values):
print(f'setting {self.pos=} {self.puzzle_address()=} to {values}')
self.owner.set_candidates_at(self.pos, values)
That gives me this:
found pairs=[['6', '7']]
setting self.pos=7 self.puzzle_address()=7 to ['6', '7']
setting self.pos=8 self.puzzle_address()=8 to ['6', '7']
found pairs=[['2', '3']]
setting self.pos=0 self.puzzle_address()=2 to ['2', '3']
setting self.pos=8 self.puzzle_address()=74 to ['2', '3']
found pairs=[['1', '8']]
setting self.pos=1 self.puzzle_address()=1 to ['1', '8']
setting self.pos=4 self.puzzle_address()=10 to ['1', '8']
Is there something wrong with my test? It looks to me as if we have found some other hidden pairs, but that we have set 7 and 8 as we should have. Review the test.
puzzle = Puzzle.from_list(puzzle_list)
row_0 = Component.row(puzzle, 0)
assert row_0.candidates_at(7) == ['2', '3', '4', '5', '6', '7', '9']
assert row_0.candidates_at(8) == ['3', '4', '5', '6', '7', '9']
technique = HiddenPairsTechnique(puzzle)
technique.apply()
assert row_0.candidates_at(7) == ['6', '7']
assert row_0.candidates_at(8) == ['6', '7']
I don’t know what happened there but what if we check the puzzle directly?
puzzle = Puzzle.from_list(puzzle_list)
row_0 = Component.row(puzzle, 0)
assert row_0.candidates_at(7) == ['2', '3', '4', '5', '6', '7', '9']
assert row_0.candidates_at(8) == ['3', '4', '5', '6', '7', '9']
technique = HiddenPairsTechnique(puzzle)
technique.apply()
assert puzzle.candidates.at(7) == ['6', '7']
assert puzzle.candidates.at(8) == ['6', '7']
# assert row_0.candidates_at(7) == ['6', '7']
# assert row_0.candidates_at(8) == ['6', '7']
That fails the same way. The puzzle has received the wrong values in those cells, somehow.
Take a short walk and let brain refresh.
What must be happening is that our indirect addressing is picking up a mistaken value, somehow. I need more info.
def set_candidates_at(self, position, candidates):
self.puzzle.set_candidates_at(position, candidates)
Ah. That’s not mapping the coordinates. How does this ever work? Let’s check senders: most of them must be doing the mapping themselves. Or our tests around setting are bad. A look at usages makes me think that we’re confusing the position in the component with the position in the component’s positions member. Hard to see how that naming helps.
Let’s see if we can produce a failing test.
A quick review of test_component.py shows me very few tests of Component directly, essentially none. It was tested indirectly quite a bit. Here’s a test that should fail:
def test_accesses_correct_cell(self):
puzzle = Puzzle.empty()
col = Component.column(puzzle, 0)
assert puzzle.candidates.at(8) == ['1', '2', '3', '4', '5', '6', '7', '8', '9']
col.set_candidates_at(8, ['1', '2'])
assert puzzle.candidates.at(8) == ['1', '2', '3', '4', '5', '6', '7', '8', '9']
assert puzzle.candidates.at(72) == ['1', '2']
This will fail, I predict, on the second check of 8, with ['1', '2']
Expected :['1', '2', '3', '4', '5', '6', '7', '8', '9']
Actual :['1', '2']
Fix it:
def set_candidates_at(self, position, candidates):
puzzle_cell_index = self.positions[position]
self.puzzle.set_candidates_at(puzzle_cell_index, candidates)
Guess what! All the tests pass, including our new HiddenPairsTechnique one.
Find and remove my prints.
Commit: HiddenPairsTechnique test passes after fix to Component.set_candidates_at.
Let’s sum up and revisit this next time.
Summary
Well, that was kind of weird. The defect was in a trusted, but very poorly tested object: Component. Most of the tests that give us confidence in Component are actually tests that use it, with the thinking being, if they work, then it works. That turns out not to be the case.
I think that we’ll find that the tests either do not set candidates (most of them), or, if they do, they happen to do it using row_0, which is really convenient to test but also happens to be a component where the positions in the component happen to match the positions in the underlying puzzle. So things work that really shouldn’t.
Here again, while my better side was starting to call for a rollback, my other side was calling for more information, which is often just a less guilty way of saying “I want to debug this”. I would say that quite often, I’d be a wiser man if I were to ignore that other side. However, this time, getting more information was the thing to do, because all the code we wrote today, and for a couple of days before, was correct. There was a hidden flaw in a subordinate object and redoing the upper level would have gained nothing.
So, yes, for the second time recently, I’ve been feeling the roll back urge, put it off, and profited. It may still not be the way to bet.
I’ve made three notes today:
- Finish NakedPairsTechnique
- Component tests
- HiddenPairs extras?
- How far can we iterate? (Wrong about three.)
That “extras” one invites me to explore the fact that the hidden pairs test, while it did find the pair I knew about, seems to have found two others. We would be wise to check the original test and see whether there are those additional cases.
And the fourth one, which just occurred to me, asks me to think about how long we can safely iterate some Technique like HiddenPairs, and when we need to start over from the top. I believe that it is safe to iterate any technique that just adjusts notes, and that a technique that sets an cell must stop and adjust the notes. (But perhaps should not just recalculate, since the notes have information beyond the elementary Sudoku rules.)
But once hidden pairs has done its work, identifying the hidden [‘6’, ‘7’] pair, I think the NakedPairsTechnique, if we’d just get off the dime and finish it, would then see a NakedPair and that it would therefore adjust other notes in all the components impacted by those cells.
I’m kind of flying a bit blind here, because I’ve not found any discussion on the topic of how the techniques interact.
It’s probably coming up time to load in a bunch of puzzles and start seeing how many our techniques can solve. That’ll be interesting.
For now, I’m confident in HiddenPairsTechnique … and want to delve a bit further into it.
- Delving into Delving
- While Sudoku isn’t a likely candidate for a real world project, there are real-world efforts with a similar situation. Two examples are: an advertising server that has many strategies, and a stock trading program, again with many strategies.
-
In these situations, we might be quite certain that the individual strategies work, as we are coming to be confident in our Sudoku techniques. But we might not know much at all about the impact of the order in which we apply the strategies. I worked with a team who were maintaining an ad server that had hundreds of rules of thumb, if he’s bought bread and he’s bought jelly, offer him peanut butter kind of thing. They sort of applied the strategies one after another but they knew that they could interact, and had no really good way of assessing which order was best. And, of course, the strategies really might want to be combined, and the only way that ever happened was if someone in the ad department decided to change the rules, or, more commonly add one.
-
We have a very similar situation here. We can become quite sure that our techniques work. But we know very little about the impact of order in applying them, whether for optimal performance, or just to avoid errors.
-
My point being … even these toy programs that we work with, small enough so that we can come close to understanding them … even these toy programs give rise to the same problems we encounter in real world larger problems. Programming is like that, elephants all the way down.
Anyway, today we found a small but important defect down in Component, and once it was fixed, our HiddenPairsTechnique test worked, and I, for one, am pretty confident in it. Not so confident that I won’t look further, but I think it’s good.
- Testing Simple Objects
-
And have we learned a lesson about testing even simple objects that are in common use? it would be will if we have …
See you next time. We’ll find out if I am surprised upon further exploration.