Sudoku: Next?
Let’s review our notes and see what to do next. Is there a way to wrap this up semi-neatly? Quasi-neatly? Not yet, but progress is good.
I have some notes written on cards1 that need review. I decide to pitch all the undated ones. I consider the 4 Aug ones to be done, although perhaps exploring the stats would be useful. Right now I have no questions. I’m left with these:
- 6 Aug: NakedPairs code bounces around a lot
- 6 Aug: NPTechnique has puzzle member unused
- 6 Aug: SudokuTechniques does the loop?? (for NP)
- 6 Aug: No NakedPairs occur in the 9x9 sample?
- 6 Aug: hack check for linesize in SudokuTechniques / NakedPairs?
- 5 Aug: Naked / Hidden change looping (refers to who does it?)
Some of these are related. Let me put it this way:
- Looping
- In NakedPairs, the SudokuTechniques class has a method that loops NakedPairs technique, which only processes one provided Component. But HiddenPairs includes the loop over Components. We should pick an approach and use it.
Let’s go after that. We need to install HiddenPairs soon and normalizing the style will make sense before we do that.
- Wait
- That’s easy to say. There are two approaches we could take. We could decide now which way things go and adjust whichever class needs to change. I think I’m assuming looping in the detailed Technique is better than in SudokuTechniques.
-
But it would be perfectly valid to install HiddenPairs in its existing style and then decide what to do with the similarities and differences. It’s not appropriate to just wave hands and say we should decide before we do anything else.
-
In fact, now that I’ve allowed myself to question the assumption, I think we might do better to install HiddenPairs and then review the actual code. More reality, less speculation, and not likely any more work.
-
I’m glad we had this little chat.
Plan
Let’s install HiddenPairsTechnique and see what things look like on the other side.
Here’s the class in question:
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):
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)
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
This class is still in the test file. Let’s move it, with PyCharm help, to its own file. F6, type file name, done.
Tests are green. Commit: move HiddenPairsTechnique to own file.
The class has its own apply method, which checks every puzzle component. (I do think this is how things should be done when we’re finished. Why should SudokuTechniques know what HiddenPairsTechique wants to think about?)
So I think we can just plug it into SudokuTechniques, whose interesting bits look like this:
class SudokuTechniques:
def __init__(self, puzzle):
self.puzzle = puzzle
self. changed = False
def apply(self):
self.changed = True
while self.changed:
self.changed = False
self.changed |= self.only_one_possible_value()
self.changed |= self.only_one_possible_position()
self.changed |= self.naked_pairs()
return self.puzzle
I think it’s pretty clear what we’ll want here, a new line in apply, and a small new method instantiating a HiddenPairsTechnique and calling its apply. But we do expect it to return a True/False changed result. We are not returning one at present.
class HiddenPairsTechnique:
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 = [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)
We need to know if the code in check_component actually changed either of the notes_a or notes_b. Let’s see what that become does.
class Notes:
def become(self, values):
self.owner.set_candidates_at(self.pos, values)
We would like to return True if we are actually making a change. And, while we are at it, let’s not make a change if the values are already right.
It’s pretty clear how to do this, just check to see if the candidates at self.pos are equal to our values parameter and if so return False (not changed) otherwise set them and return True (changed).
I have little doubt in my ability to code that right now. But we might do well to have a test for that logic, don’t you think?
Do we have any tests for this thing at all?
Well, yes, we have a decent test. We also have two identical tests with the technique written out longhand, as part of developing the little Notes class used above. Ignore those. Here’s a real test:
def test_hidden_pairs_technique(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)
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']
Let’s change this one … no, write another one … that tries the technique twice.
def test_hidden_pairs_technique_returned_changed(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)
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)
changed = technique.apply()
assert changed is True
assert puzzle.candidates.at(7) == ['6', '7']
assert puzzle.candidates.at(8) == ['6', '7']
technique = HiddenPairsTechnique(puzzle)
not_changed = technique.apply()
assert not_changed is False
Now we have a nice failure on changed, so we can implement:
class HiddenPairsTechnique:
def apply(self):
for component in self.puzzle.all_components():
return self.check_component(component)
def check_component(self, component):
changed = False
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]
changed |= notes_a.become(notes)
changed |= notes_b.become(notes)
return changed
And in Notes:
def become(self, values):
if self.owner.candidates_at(self.pos) == values:
return False
self.owner.set_candidates_at(self.pos, values)
return True
And our test passes. Commit: HiddenPairs apply returns changed flag.
Reflection
OK, we can now install HiddenPairs in the obvious way. But we have no reason to do it, because we do not have a test that shows that it isn’t working.
But I think we can write one …
def test_hidden_pairs_is_in_sudoku_techniques(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)
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']
st = SudokuTechniques(puzzle)
changed = st.apply()
assert changed is True
assert puzzle.candidates.at(7) == ['6', '7']
assert puzzle.candidates.at(8) == ['6', '7']
st = SudokuTechniques(puzzle)
not_changed = st.apply()
assert not_changed is True
This fails, presumably because there is no HiddenPairs checking in SudokuTechniques.
Ewww, also SudokuTechniques still returns a puzzle from apply. And it really does need to do that, I think, so long as there are techniques that set new values and there is at least one.
Let me do this:
class SudokuTechniques:
def apply(self):
self.changed = True
while self.changed:
self.changed = False
self.changed |= self.only_one_possible_value()
self.changed |= self.only_one_possible_position()
self.changed |= self.naked_pairs()
return self.puzzle, self.changed # bit of a hack
This breaks a lot of tests but they all just need to accept another value, like this one:
def test_easy_1(self):
Logger.initialize()
puzzle = Puzzle.from_list(self.easy_1)
for i in range(1000):
old_puzzle = puzzle
if puzzle.is_correctly_solved:
break
techniques = SudokuTechniques(puzzle)
puzzle, _changed = techniques.apply() # <===
if puzzle is old_puzzle:
break
assert puzzle.is_correctly_solved
assert int(Logger.log()["Techniques only_one"]) == 39
Quickly, I am down to my actual test, which fails because HiddenPairs isn’t in there yet. I’d like to commit everything else but I don’t want to commit this broken test. Let’s just make it work it, it should be trivial.
def apply(self):
self.changed = True
while self.changed:
self.changed = False
self.changed |= self.only_one_possible_value()
self.changed |= self.only_one_possible_position()
self.changed |= self.naked_pairs()
self.changed |= self.hidden_pairs()
return self.puzzle, self.changed
def hidden_pairs(self):
if self.puzzle.line_size != 9:
return False
hp_technique = HiddenPairsTechnique(self.puzzle)
return hp_technique.apply()
Hm, test fails. Oh, I didn’t fix up this one. LOL.
def test_hidden_pairs_is_in_sudoku_techniques(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)
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']
st = SudokuTechniques(puzzle)
_puzzle, changed = st.apply()
assert changed is True
assert puzzle.candidates.at(7) == ['6', '7']
assert puzzle.candidates.at(8) == ['6', '7']
st = SudokuTechniques(puzzle)
_puzzle, not_changed = st.apply()
assert not_changed is True
Unfortunately, it still fails, saying False at that first check, which I thought should be true.
I will wager that one of the other techniques found something, probably naked pairs?
Let’s check some stats.
Puzzle Count: 47
Techniques only_one: 42
Techniques only_one_position: 5
As I suspected, we found lots of other things first, and never found the hidden pairs.
I can verify that it’s in there by briefly commenting out the other checkers, which will break a lot of other things but should let this test pass.
However, when I do that, my new test still fails saying nothing was changed. What is curious is that when I comment out the check for changed, the check for the candidates gets the right answer. So the technique has run … oh … oh hell … SudokuTechniques loops until it has not changed anything. We cannot check the flag in our test. We can only check the result. So let’s undo that sill changed return and work from there.
def test_hidden_pairs_is_in_sudoku_techniques(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)
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']
Logger.initialize()
st = SudokuTechniques(puzzle)
new_puzzle: Puzzle = st.apply()
assert puzzle.candidates.at(7) == ['6', '7']
assert puzzle.candidates.at(8) == ['6', '7']
assert new_puzzle is not puzzle # more has been done
assert new_puzzle.candidates.at(7) == []
assert new_puzzle.candidates.at(8) == []
assert new_puzzle.is_correctly_solved
I am confident that the feature has run, but let’s log it to be sure.
def check_component(self, component):
changed = False
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]
changed |= notes_a.become(notes)
changed |= notes_b.become(notes)
if changed:
Logger.log().count("Hidden Pair Count")
return changed
And the test, modified to check, passes:
def test_hidden_pairs_is_in_sudoku_techniques(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)
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']
Logger.initialize()
st = SudokuTechniques(puzzle)
new_puzzle: Puzzle = st.apply()
assert int(Logger.log()['Hidden Pair Count']) == 1 # <===
assert puzzle.candidates.at(7) == ['6', '7']
assert puzzle.candidates.at(8) == ['6', '7']
assert new_puzzle is not puzzle # more has been done
assert new_puzzle.candidates.at(7) == []
assert new_puzzle.candidates.at(8) == []
assert new_puzzle.is_correctly_solved
Let’s sum up.
Summary
Got a bit ragged there. The fundamental issue, I think is that we do not have, and as far as I can tell, generally cannot readily have, tests where we can easily predict exactly how many of which techniques will apply. I emphasize “readily” and “easily”. Such puzzles surely exist, but creating them isn’t easy.
Since we do have a check to ensure that a puzzle is correctly solved, we can write tests like the one above, that can check to see if a technique was applied at least once, or a known number of times that we might hand check, and if the puzzle winds up solved we can be pretty confident that we didn’t mess something up.
It’s not ideal but it seems endemic to the situation: Sudoku puzzles are hard to solve and harder to create, if you want specific properties.
But then I went in the wrong direction for a while, assuming that I could return a “changed” flag from SudokuTechniques apply, which is not the case, because it loops until nothing has changed as far as it knows.
So I had modified 8 tests to have that useless result and decided to modify them back.
I think we could have left that change in, useless though it was, made our existing test pass, committed, and then changed the 8 back. The way I chose made what could have been two small steps into one larger one. I think the other way would be the better choice, because the work is the same and the steps smaller.
But no harm done.
Summary Summary
We have HiddenPairs installed, tested, and working. New card:
- 10 Aug
- Decide about NakedPairs loop in SudokuTechniques. Should be in NakedPairs?
Any cleanup aside, including the work above, all the techniques that we have implemented or really thought much about are now installed. We could wrap up now and call it a day, moving on to something else. I certainly feel that I have reclaimed any honor lost when I stopped working on the thing last time. Or …
- 10 Aug
-
More puzzles from Internet?
We could read in some more puzzles, try to solve them, see if another technique or two are called for.
Right now, that doesn’t interest me much. We should at least clean up what we have, assess the code, and assess the overall effort.
Summary Summary Summary
A decent day. A bit ragged, I’d score myself about 0.8 on a scale where 1 is my best day. Maybe I’m being too generous to myself, but I feel about 0.8 because I was never confused and do not seem to have made any egregious errors.
Maybe next time! Stop by and find out! See you then!