Sudoku: Naked Pairs
Still not as interesting as it sounds, but this morning I plan to hunt down some naked pairs. I foresee some issues. And what about that pending issue from yesterday? Results: a bit long, but some shape emerges.
Yesterday’s issue, since you bring it up, was that when running the big 9x9 puzzle, the only_one strategy gets run some 70,000 times, which seems like a lot. I have made a card to explore it, and I did a bit of exploration last night. My hypothesis was that we were applying it more than we should, setting values that were already set. My quick test did not show that to be the case. So the “explore” card is still active.
Nonetheless, I propose to work on naked pairs today, as a mind cleanser and expecting to drive out some improvements in our basic objects.
Naked Pairs
If any Component contains two cells, each with the same pair of possible candidates, then no other cell in that Component can contain either of those candidates, and we should therefore remove the pair elements from any other candidate that includes either of them.
Is that clear? I hope so. Suppose that two cells have just the candidates ‘1’ and ‘2’. Then those two cells must be either ‘1’ in the first, ‘2’ in the second, or ‘2’ in the first, ‘1’ in the second. By the rule of Sudoku, therefore no other cell can contain either of those values.
Design Thinking
I call it thinking, it’s more kind of mumbling in my mind, but it seems clear that this technique is focused on individual components, and only peripherally on the whole puzzle, insofar as a Component is basically a view of part of the Puzzle.
So given a Component, we want to see if it contains two candidate cells, each with exactly the same two values. If we find that situation, we want to remove those two values from all the other candidates in the Component.
It is worth noting that more than one set of naked pairs could, in principle, occur in the same component. I suppose, in principle, there could be four, e.g. ‘12’, ‘34’, ‘56’, ‘78’.
Let’s review Component, with an eye to setting up some tests. Current tests are green, with three slow ones skipped.
As it stands, Component doesn’t know about the Puzzle’s Candidates at all:
class Component:
sub_grid_starts = [
0, 0, 0, 3, 3, 3, 6, 6, 6,
0, 0, 0, 3, 3, 3, 6, 6, 6,
0, 0, 0, 3, 3, 3, 6, 6, 6,
27, 27, 27, 30, 30, 30, 33, 33, 33,
27, 27, 27, 30, 30, 30, 33, 33, 33,
27, 27, 27, 30, 30, 30, 33, 33, 33,
54, 54, 54, 57, 57, 57, 60, 60, 60,
54, 54, 54, 57, 57, 57, 60, 60, 60,
54, 54, 54, 57, 57, 57, 60, 60, 60,
]
def __init__(self, puzzle, start, steps):
self.start = start
self.positions = [start + step for step in steps]
self.used = [puzzle.game[index] for index in self.positions]
def __iter__(self):
return iter(self.used)
@property
def used_numbers(self):
return [c for c in self.used if c != '0']
@property
def is_valid(self):
for c in '123456789':
if c not in self.used:
return False
return True
There are also class methods to fetch a row, column, or sub-grid from the puzzle. (I keep thinking and typing “game”. I wish I would stop doing that. I mean “puzzle”.)
Instead of copying information from the Puzzle, I think Component should be a “view” of the puzzle fetching all its information live from the puzzle. That will be an interesting change, probably quite easy, probably capable of being done incorrectly: I am really good at doing things incorrectly. Let’s see what we have for tests of Component.
We have 43 references to Component of which 8 are outside tests. The tests are simple but extensive:
class TestPuzzle:
def test_row(self):
game = '103000010'
puzzle = Puzzle(game)
assert Component.row(puzzle, 0).used_numbers == ['1', '3']
assert Component.row(puzzle, 1).used_numbers == ['1', '3']
assert Component.row(puzzle, 2).used_numbers == ['1', '3']
assert Component.row(puzzle, 3).used_numbers == []
assert Component.row(puzzle, 4).used_numbers == []
assert Component.row(puzzle, 5).used_numbers == []
assert Component.row(puzzle, 6).used_numbers == ['1']
assert Component.row(puzzle, 7).used_numbers == ['1']
assert Component.row(puzzle, 8).used_numbers == ['1']
def test_column(self):
game = '103000010'
puzzle = Puzzle(game)
assert Component.column(puzzle, 1).used_numbers == ['1', ]
assert Component.column(puzzle, 4).used_numbers == ['1', ]
assert Component.column(puzzle, 7).used_numbers == ['1', ]
assert Component.column(puzzle, 0).used_numbers == ['1', ]
assert Component.column(puzzle, 3).used_numbers == ['1', ]
assert Component.column(puzzle, 6).used_numbers == ['1', ]
assert Component.column(puzzle, 2).used_numbers == ['3', ]
assert Component.column(puzzle, 5).used_numbers == ['3', ]
assert Component.column(puzzle, 8).used_numbers == ['3', ]
And more. They all refer to the used_numbers property, which is pretty much all the Component has to offer at present. If we preserve that property, we should be able to convert to a view of Puzzle readily, like this:
class Component:
def __init__(self, puzzle, start, steps):
self.puzzle = puzzle
self.start = start
self.positions = [start + step for step in steps]
@property
def used_numbers(self):
return [self.puzzle.game[index] for index in self.positions if self.puzzle.game[index] != '0']
Curiously, this passes all but one test. Whazzup with that?
Ah. I forgot to fix is_valid.
@property
def is_valid(self):
for c in '123456789':
if c not in self.used_numbers:
return False
return True
See what I mean about my incredible ability to do things incorrectly? We are green. Commit: Component now views Puzzle for access to cell values.
Now, we know that Puzzle has those Candidates:
class Puzzle:
def __init__(self, a_game_string):
Puzzle.puzzle_count += 1
if len(a_game_string) == 9:
self.available_values = '123'
self.line_size = 3
elif len(a_game_string) == 81:
self.available_values = '123456789'
self.line_size = 9
else:
raise ValueError('problem must have length 9 or 81')
self.candidates = Candidates(a_game_string)
self.game = a_game_string
self.guess_position = self.first_unsolved_position()
There is almost no use made of Candidates, except when the Puzzle is asked for possible_answers:
def possible_answers(self, position):
if self.game[position] != '0':
return [self.game[position]]
return self.candidates.at(position)
Since “naked pairs” is about candidates, now we refresh our mind about that class:
class Candidates:
def __init__(self, a_game_string):
self.game = a_game_string
self.line_size = 0
self.candidates = self.create_raw_c
def create_raw_candidates(self, a_game_string):
if len(a_game_string) == 9:
available_values = '123'
elif len(a_game_string) == 81:
available_values = '123456789'
else:
raise ValueError('problem must have length 9 or 81')
self.line_size = len(available_values)
all_possible = [value for value in available_values]
return [all_possible for cell in range(len(a_game_string))]
def fill_in_solved(self, a_game_string):
for cell, value in enumerate(a_game_string):
if value != '0':
self.candidates[cell] = [value]
row = Component.row(self, cell)
col = Component.column(self, cell)
sub = Component.sub_grid(self, cell)
positions = set(row.positions) | set(col.positions) | set(sub.positions)
positions.discard(cell)
for pos in positions:
self.candidates[pos] = [v for v in self.candidates[pos] if v != value]
self.candidates[cell] = [value]
Ah, yes. We construct the initial candidates by assuming that anything is possible (‘123456789’) and then, for any known value in a position, removing any known values from related positions, and setting the given position to its single known value (as a collection of size 1).
For our foray into Naked Pairs, I would like to work with a known set of values, in a single Component (which is now a view of Puzzle), suggesting that we need to set up a test Puzzle so that its values and categories will be as we intend.
Let’s not do that. Let’s, instead, create a test component, set up just the way we wish. There are at least two ways to go on that.
- Make an actual Component, with a wild new way of setting it up;
- Make a separate kind of TestComponent class, and rely on duck typing.
I think the former is better. I’m not opposed to creating test doubles, but here, I think we’ll do better to rely on the real class Component as much as we can.
So let’s write a test.
def test_naked_pairs(self):
empty = [
'000000000',
'000000000',
'000000000',
'000000000',
'000000000',
'000000000',
'000000000',
'000000000',
'000000000',
]
puzzle = Puzzle.from_list(empty)
puzzle.candidates[0] = [1, 2]
puzzle.candidates[4] = [1, 2]
This is enough to break things, because Candidates does not support item assignment. Yet.
class Candidates:
def __setitem__(self, key, value):
self.candidates[key] = value
That allows the assignment. Now, as I was saying …
def test_naked_pairs(self):
empty = [
'000000000',
'000000000',
'000000000',
'000000000',
'000000000',
'000000000',
'000000000',
'000000000',
'000000000',
]
puzzle = Puzzle.from_list(empty)
puzzle.candidates[0] = [1, 2]
puzzle.candidates[4] = [1, 2]
row = Component.row(puzzle, 0)
assert row.candidates_at[0] == [1, 2]
I figure I should verify here that the row can access candidates and made up the name candidates_at. Which of course fails, but:
class Component:
def candidates_at(self, position):
return self. puzzle.candidates.at[self.positions[position]]
I really thought that would work but the test says:
> assert row.candidates_at[0] == [1, 2]
E TypeError: 'method' object is not subscriptable
I think parens would be good there, not []. Still fails, though.
> return self. puzzle.candidates.at[self.positions[position]]
E TypeError: 'method' object is not subscriptable
I did it twice! At least I’m consistent.
class Component:
def candidates_at(self, position):
return self. puzzle.candidates.at(self.positions[position])
OK! We got our ‘[1, 2]’ back. We can press on. I’ll take that as telling me that the whole candidates collection is OK in our test Component.
Now we have a bit of a design decision to make.
Up until now and heretofore, we have put our techniques in the SudokuTechniques class. Of course, we only have about one and a fraction techniques. But if we think about what the naked pairs thing will need to do, it will need to search through the Component for a pair, then search further for another, then search all the other cells adjusting … .and then do it over again, making sure not to do the first pairs over. And again and again until there are no unprocessed pairs.
That’s a lot even waving our hands at it like that. So I think we’ll want a separate class to handle NakedPairs. We’ll call it … NakedPairsTechnique. And we’ll test it, first, like this:
def test_naked_pairs(self):
empty = [
'000000000',
'000000000',
'000000000',
'000000000',
'000000000',
'000000000',
'000000000',
'000000000',
'000000000',
]
puzzle = Puzzle.from_list(empty)
puzzle.candidates[0] = [1, 2]
puzzle.candidates[4] = [1, 2]
row = Component.row(puzzle, 0)
assert row.candidates_at(0) == [1, 2]
technique = NakedPairsTechnique(row)
technique.apply()
for cell in [1, 2, 3, 5, 6, 7, 8, 9]:
candidates = row.candidates_at(cell)
assert candidates == [3, 4, 5, 6, 7, 8, 9]
I think that’s good. Generate the class. As I often do, I’ll let PyCharm create it here in the test file, because it’s easy to move it later and easier to work with it here, at least while it’s new.
class NakedPairsTechnique:
def __init__(self, component):
self.component = component
def apply(self):
result = [3, 4, 5, 6, 7, 8, 9]
for cell in range(2,9):
self.component.set_candidates(cell, result)
Two things going on here. First is “fake it till you make it”: I’m just setting the correct answer, not really computing it. Second is “by intention”, positing a method on Component to set a candidates element. We’ll write that:
def set_candidates_at(self, position, candidates):
self.puzzle.set_candidates_at(position, candidates)
Since we have candidates_at, I renamed it as above, and changed the technique. Now Puzzle needs to help out:
class Puzzle:
def set_candidates_at(self, position, values):
self.candidates.set_at(position, values)
And we’re still not there until:
class Candidates:
def set_at(self, cell, values):
self.candidates[cell] = values
That’s a long chain and the test is failing, when it seemed to me that it might work. Let’s see:
Expected :[3, 4, 5, 6, 7, 8, 9]
Actual :['1', '2', '3', '4', '5', '6', '7', '8', '9']
OK, we have two issues, one of them being we had better use characters, not integers. I am starting to hate that feature. The second, of course is that we really would have been happier with a match. Let’s work thru the logic, fix up the character / integer stuff, and see where we went wrong:
class NakedPairsTechnique:
def __init__(self, component):
self.component = component
def apply(self):
result = ['3', '4', '5', '6', '7', '8', '9']
for cell in range(2, 9):
self.component.set_candidates_at(cell, result)
So far so good …
class Component:
def set_candidates_at(self, position, candidates):
self.puzzle.set_candidates_at(position, candidates)
class Puzzle:
def set_candidates_at(self, position, values):
self.candidates.set_at(position, values)
class Candidates:
def set_at(self, cell, values):
self.candidates[cell] = values
OK, one thing that is wrong here is that we have not adjusted for the row’s indices, but since row zero’s indices are also 0-8 I feel we should be OK despite that mistake.
If I were wise, I might roll back, but I am not quite that wise, so I am going to see if I can work out what happened.
class Candidates:
def set_at(self, cell, values):
print(f'cand set at {cell=}, {values=}')
self.candidates[cell] = values
print(f'{self.candidates[0:4]}')
That prints what I would have expected:
cand set at cell=2, values=['3', '4', '5', '6', '7', '8', '9']
[[1, 2], ['1', '2', '3', '4', '5', '6', '7', '8', '9'], ['3', '4', '5', '6', '7', '8', '9'], ['1', '2', '3', '4', '5', '6', '7', '8', '9']]
cand set at cell=3, values=['3', '4', '5', '6', '7', '8', '9']
[[1, 2], ['1', '2', '3', '4', '5', '6', '7', '8', '9'], ['3', '4', '5', '6', '7', '8', '9'], ['3', '4', '5', '6', '7', '8', '9']]
It sure seems to be setting them. Is the test wrong?
puzzle = Puzzle.from_list(empty)
puzzle.candidates[0] = [1, 2]
puzzle.candidates[4] = [1, 2]
row = Component.row(puzzle, 0)
assert row.candidates_at(0) == [1, 2]
technique = NakedPairsTechnique(row)
technique.apply()
for cell in [1, 2, 3, 5, 6, 7, 8, 9]:
candidates = row.candidates_at(cell)
assert candidates == ['3', '4', '5', '6', '7', '8', '9']
I’m not seeing the problem. Before I resort to more debugging, let’s use our new setting methods in the test setup. If they don’t work, then the single assert might fail and tell us something.
puzzle = Puzzle.from_list(empty)
row = Component.row(puzzle, 0)
row.set_candidates_at(0, ['1', '2'])
row.set_candidates_at(4, ['1', '2'])
assert row.candidates_at(0) == ['1', '2']
technique = NakedPairsTechnique(row)
technique.apply()
for cell in [1, 2, 3, 5, 6, 7, 8, 9]:
candidates = row.candidates_at(cell)
assert candidates == ['3', '4', '5', '6', '7', '8', '9']
Same issue. I really should roll back and do it over. But I’m feeling the sunk cost too much to do that. I’ll try, as a last resort, a breakpoint. This violates every moral principle I have: I used to pride myself on not even knowing how to use the debugger.
Stopping on the candidates = line, I inspect down thru the row and find that the candidates, in the puzzle, are as I expect, with the ‘3’ ‘4’ etc. Step in to see what candidates_at is doing.
LOL. The bug is, my test and my fake implementation do not match. It should be:
class NakedPairsTechnique:
def __init__(self, component):
self.component = component
def apply(self):
result = ['3', '4', '5', '6', '7', '8', '9']
for cell in [1, 2, 3, 5, 6, 7, 8]:
self.component.set_candidates_at(cell, result)
def test_naked_pairs(self):
empty = [
'000000000',
'000000000',
'000000000',
'000000000',
'000000000',
'000000000',
'000000000',
'000000000',
'000000000',
]
puzzle = Puzzle.from_list(empty)
row = Component.row(puzzle, 0)
row.set_candidates_at(0, ['1', '2'])
row.set_candidates_at(4, ['1', '2'])
assert row.candidates_at(0) == ['1', '2']
technique = NakedPairsTechnique(row)
technique.apply()
for cell in [1, 2, 3, 5, 6, 7, 8]:
candidates = row.candidates_at(cell)
assert candidates == ['3', '4', '5', '6', '7', '8', '9']
We are passing. We are green. Commit: initial test for NakedPairs passes with fake implementation.
Reflection
Time to relax a bit after the scary part.
So that was amusing: the test and the fake were both flaky, referring to different cells in the candidates array. Once they were lined up, the test ran, showing that the sequence of calls to set the candidates down and down and down is working. It is a bit deep:
row -> puzzle -> candidates. And I am slightly concerned about this:
def at(self, cell):
return self.candidates[cell]
def set_at(self, cell, values):
self.candidates[cell] = values
All the way down to here, we say candidates_at, and then in Candidates we switch to at. I’m not sure I love that convention. But saying self.candidates.candidates_at(pos) … is that better?
I don’t know. We’ll let it ride for now, see if we get confused. If we do, we’re primed to fix it, if not, not.
We got away with the debugging, where I finally noticed that the test was fetching item 1 and our fake method had not set it. In this case, rolling back might not have helped. Or would it? If I rolled back the NakedPairsTechnique’s fake method, there’s a good chance I would have made it correctly the next time.
It’s hard to say. Rolling back is hard to do, but it is so often the right step when one has probably made some silly mistake.
Anyway, we did what we did and we are here now.
Should we break, or should we write the next test and make it work?
We’ll break and return either this afternoon, or, more likely, tomorrow.
Summary
We’re jumping around a bit. We have a question outstanding about the only one technique and we have nothing but a place holder for the only_one_position technique, and here we are starting on naked pairs. Is that bad? It depends who’s expecting what? If our mission is to have some interesting progress on techniques this week, we’re in good shape. If we promised someone that only_one_place would work by yesterday, we’re in trouble.
My take is that we are making small steps toward supporting techniques and the naked pairs one is already driving out some useful abstractions and behavior, so we’re doing just fine. But it really does depend on what our team and organization expect from us. As always, collaboration is really important in real projects. I have the luxury of having no boss and it has taken me eight decades to get to that state of affairs, so I am going to enjoy it.
We made more progress than it may seem this morning. We’ve made the Component into a true view of the Puzzle, and given all the objects all the way down accessors for the candidates.
I think there are rough spots needing improvement. Here’s one:
class Component:
@property
def used_numbers(self):
return [self.puzzle.game[index] for index in self.positions if self.puzzle.game[index] != '0']
Component should not know how to rip the guts out of Puzzle. It should ask puzzle for its values, perhaps like this:
self.puzzle.cell_at(index)
I’m not sure what to call it. Let’s do cell_at just to get the proper indirection in place:
class Component:
@property
def used_numbers(self):
return [self.puzzle.cell_at(index) for index in self.positions if self.puzzle.cell_at(index) != '0']
class Puzzle:
def cell_at(self, position):
return self.game[position]
Green. Commit: add Puzzle.cell_at. I’m tiring but let’s quickly scan for self.puzzle to see if there are some other places for cell_at, or other violations to be aware of.
A quick glance looks OK. Let’s fold our tents and mix up a nice iced chai latte.
See you next time!
- Added in Post:
- I see why I keep thinking “game”. The Puzzle has a
gamemember variable. Remind me to change that.