|
このページは大阪弁化フィルタによって翻訳生成されたんですわ。 |
A1 A2 A3| A4 A5 A6| A7 A8 A9 B1 B2 B3| B4 B5 B6| B7 B8 B9 C1 C2 C3| C4 C5 C6| C7 C8 C9 ---------+---------+--------- D1 D2 D3| D4 D5 D6| D7 D8 D9 E1 E2 E3| E4 E5 E6| E7 E8 E9 F1 F2 F3| F4 F5 F6| F7 F8 F9 ---------+---------+--------- G1 G2 G3| G4 G5 G6| G7 G8 G9 H1 H2 H3| H4 H5 H6| H7 H8 H9 I1 I2 I3| I4 I5 I6| I7 I8 I9
We can implement this in the programming language Python as follows:
def cross(A, B):
return [a+b for a in A for b in B]
rows = 'ABCDEFGHI'
cols = '123456789'
digits = '123456789'
squares = cross(rows, cols)
unitlist = ([cross(rows, c) for c in cols] +
[cross(r, cols) for r in rows] +
[cross(rs, cs) for rs in ('ABC','DEF','GHI') for cs in ('123','456','789')])
units = dict((s, [u for u in unitlist if s in u])
for s in squares)
peers = dict((s, set(s2 for u in units[s] for s2 in u if s2 != s))
for s in squares)
(Note that this uses generator expressions and therefore requires at least Python 2.4.) Now square A1 has units and peers defined as follows:
>>> units['A1']
[['A1', 'B1', 'C1', 'D1', 'E1', 'F1', 'G1', 'H1', 'I1'],
['A1', 'A2', 'A3', 'A4', 'A5', 'A6', 'A7', 'A8', 'A9'],
['A1', 'A2', 'A3', 'B1', 'B2', 'B3', 'C1', 'C2', 'C3']]
>>> peers['A1']
set(['A2', 'A3', 'A4', 'A5', 'A6', 'A7', 'A8', 'A9',
'B1', 'C1', 'D1', 'E1', 'F1', 'G1', 'H1', 'I1',
'B2', 'B3', 'C2', 'C3'])
That is, square A1 has three units: column 1, row A, and the upper-left box. Square A1 has 20 peers (8 in the row, 8 in the column, and 4 in the box that are not in the row nor column). All other squares have the same number of units and peers.
The next step is to set up a board. Again, there does not seem to be a universal format for specifying initial boards, but a good common denominator is a string of characters, with 1-9 indicating a digit, and a 0 or period or dash specifying an empty square (but in some notations, dashes are used to separate boxes, not mark empty squares). Blanks or other characters are ignored. We call such a string a grid.
We want to parse a string of this form into a representation that will be easy to manipulate from here on. One might think that a 9 x 9 array would be the right data structure. But we decided to label squares with names like A1, not [0,0], so we'd have to change that choice if we wanted to use a two-dimensional array. Also, Python doesn't directly support two-dimensional arrays (only arrays of arrays) but it does support dictionaries (hash tables) with keys like A1, so we will represent a board as a dict with squares as keys. The value of each key will be the possible digits for that square. How do we represent a set of digits? We could use a Python set or list, but I chose instead to use a string of digits (we'll see why later). So to represent a board where square A1 is filled in with the digit 7 and A2 is blank we would use the dict {'A1': '7', 'A2': '123456789', ...}.
Here is the code to parse a grid into a dict:
def parse_grid(grid):
"Given a string of 81 digits (or . or 0 or -), return a dict of {cell:values}"
grid = [c for c in grid if c in '0.-123456789']
values = dict((s, digits) for s in squares) ## To start, every square can be any digit
for s,d in zip(squares, grid):
if d in digits and not assign(values, s, d):
return False
return values
There is a second type of constraint that we also want to propagate. Say we have just eliminated 6 as a possible value of A1. Furthermore, suppose we look at the first unit for A1 and find that of all the squares in the unit, only C1 has 6 as a possible value. Then we can assign 6 as the value of C1.
So we want two functions: assign(values, s, d) and eliminate(values, s, d) which will call each other to implement the constraint propagation (we call such functions mutually recursive). It is not obvious yet, but it is possible that we will make a mistake: that we will try to assign a value that is not consistent with the rules of Sudoku. In that case we want assign or eliminate to return False to indicate failure. In the normal case, either function should return the values that were passed to it, suitably updated with the propagated constraints. Here is the implementation:
def assign(values, s, d):
"Eliminate all the other values (except d) from values[s] and propagate."
if all(eliminate(values, s, d2) for d2 in values[s] if d2 != d):
return values
else:
return False
def eliminate(values, s, d):
"Eliminate d from values[s]; propagate when values or places <= 2."
if d not in values[s]:
return values ## Already eliminated
values[s] = values[s].replace(d,'')
if len(values[s]) == 0:
return False ## Contradiction: removed last value
elif len(values[s]) == 1:
## If there is only one value (d2) left in square, remove it from peers
d2, = values[s]
if not all(eliminate(values, s2, d2) for s2 in peers[s]):
return False
## Now check the places where d appears in the units of s
for u in units[s]:
dplaces = [s for s in u if d in values[s]]
if len(dplaces) == 0:
return False
elif len(dplaces) == 1:
# d can only be in one place in unit; assign it there
if not assign(values, dplaces[0], d):
return False
return values
There is a design pattern at work here that I have not seen mentioned elsewhere. The pattern is:
If you have two mutually-recursive functions that both alter the state of an object, try to move almost all the functionality into just one of the functions. Otherwise you will probably end up duplicating code.I learned this pattern after many years of Lisp programming, where mutually-recursive functions are common. See how it is applied in this case: one might think that assign would include the statement values[s] = d, and would then have code to propagate constraints. You can try to write the function that way. I think you will find that you will duplicate code that is in eliminate. So instead of taking that route, I reasoned that what assign is really doing is eliminating all the other values except d, so I wrote it to do just that, and put all the functionality in eliminate.
Now before we can go much further, we will need to be able to examine the state of a board. here's a function to do that:
def printboard(values):
"Used for debugging."
width = 1+max(len(values[s]) for s in squares)
line = '\n' + '+'.join(['-'*(width*3)]*3)
for r in rows:
print ''.join(values[r+c].center(width)+(c in '36' and '|' or '')
for c in cols) + (r in 'CF' and line or '')
print
Now we're ready to go. I picked the first example from a list of easy puzzles and tried it:
>>> grid = """ 003020600 900305001 001806400 008102900 700000008 006708200 002609500 800203009 005010300""" >>> printboard(parse_grid(grid)) 4 8 3 |9 2 1 |6 5 7 9 6 7 |3 4 5 |8 2 1 2 5 1 |8 7 6 |4 9 3 ------+------+------ 5 4 8 |1 3 2 |9 7 6 7 2 9 |5 6 4 |1 3 8 1 3 6 |7 9 8 |2 4 5 ------+------+------ 3 7 2 |6 8 9 |5 1 4 8 1 4 |2 5 3 |7 6 9 6 9 5 |4 1 7 |3 8 2
In this case, the puzzle was completely solved by our constraint propagation! Just by assigning the 32 squares that are given as filled in, our simple constraint propagation rules fill in the rest of the board. Unfortunately, that will not always be the case. Here is the first example from a list of hard puzzles:
>>> grid = '4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......' >>> printboard(parse_grid(grid)) 4 1679 12679 | 139 2369 269 | 8 1239 5 26789 3 1256789 | 14589 24569 245689 | 12679 1249 124679 2689 15689 125689 | 7 234569 245689 | 12369 12349 123469 ------------------------+------------------------+------------------------ 3789 2 15789 | 3459 34579 4579 | 13579 6 13789 3679 15679 15679 | 359 8 25679 | 4 12359 12379 36789 4 56789 | 359 1 25679 | 23579 23589 23789 ------------------------+------------------------+------------------------ 289 89 289 | 6 459 3 | 1259 7 12489 5 6789 3 | 2 479 1 | 69 489 4689 1 6789 4 | 589 579 5789 | 23569 23589 23689
In this case, we are still a long way from solving the puzzle. We start with only 17 squares filled in (this is believed to be the smallest number of filled-in squares that leads to a unique solution) and after constraint propagation only 3 more are filled (although all squares have at least some possibilities eliminated).
What next? We could try to code more sophisticated propagation strategies, as described here. For example, the naked pairs strategy looks for two squares in the same unit that both have the same two possible digits. Suppose both A1 and A4 have the possibilities 2 and 6. We can conclude that 2 and 6 must be in A1 and A4 (although we don't know which is where), and we can therefore eliminate 2 and 6 from every other square in the A row unit. We could code that strategy in a few lines by adding an elif len(values[s]) == 2 test to eliminate.
Coding strategies like this is a possible route, but would lead to many lines of code (there are dozens of these strategies), and we'd never be sure if we could solve every puzzle.
The other route is to search for a solution: to systematically try all possibilities until we hit one that works. The code for this is only a few lines, but we run another risk: that it might take forever to find what we're searching for. Consider that in the hard puzzle above, A2 has 4 possibilities (1679) and A3 has 5 possibilities (12679); right there that's 20 possibilities, and if we keep multiplying out, we get 462838344192000000000000000000000000000 (or about 4 × 1038) possibilities for the whole puzzle. Can that be right? Well there are 61 unfilled squares, and it looks like each of these unfilled squares has on average 4 or 5 possibilities. And indeed 461 < 4 × 1038 < 561. How can we cope with that? There are two choices.
First, we could try a brute force approach. Suppose we have a very clever search algorithm that takes only one instruction to evaluate a position, and that we have access to the next-generation computing technology, let's say a 10GHz processor with 1024 cores, and let's say we could afford a million of them, and while we're shopping, let's say we also pick up a time machine and go back to the origin of the universe and start our program running. We can than compute that we could have searched through almost 1% of the possibilities for that one puzzle by now.
The second chloice is to somehow process much more than one possibility per machine instruction. That seems impossible, but fortunately it is exactly what constraint propagation does for us. We don't have to try all 4 × 1038 possibilities because as soon as we try one we immediately eliminate many other possibilities. For example, square H7 of this puzzle has two possibilities, 6 and 9. We can try 9 and quickly see that there is a contradiction. That means we've eliminated not just one possibility, but fully half of the 4 × 1038 choices.
In fact, it turns out that to solve this particular puzzle we need to look at only 25 possibilities and we only have to explicitly search through 9 of the 61 unfilled squares; constraint propagation does the rest. For the list of 95 hard puzzles, on average we need to consider 64 possibilities per puzzle, and in no case do we have to search more than 16 squares.
What is the search algorithm? Simple: first make sure we haven't already found a solution or a contradiction, and if not choose one unfilled square and consider all its possible values. One at a time, try assigning the square each value, and searching from the resulting position. In other words, we search for a value d such that we can successfully search for a solution from the result of assigning square s to d. This is a recursive search, and we call it a depth-first search because we (recursively) consider all possibilities under values[s] = d before we consider a different value for s.
To avoid bookkeeping nightmares, we create a new copy of values for each recursive call to search. This way each branch of the search tree is independent, and doesn't confuse another branch. (This is why I chose to implement the set of possible values for a square as a string: I can copy values with values.copy() which is simple and efficient. If I implemented sets of possibilities as Python sets or lists I would need to use copy.deepcopy(values), which is inefficient.) The alternative is to keep track of each change to values and undo the change when we hit a dead end. This is known as backtracking search. It makes sense when each step is a single change, but is usually too complicated to bother with when each change can lead to many other changes via constraint propagation.
The only remaining complication is choosing the square s to assign in each step of the search. In the hard puzzle above, suppose we chose B3. It has 7 possibilities (1256789), so we'd expect to guess wrong with probability 6/7. If instead we chose H7 it has only 2 possibilities (69), so we'd expect to be wrong with probability only 1/2. Clearly it is better to chose the square that is more likely to lead to the right answer, so we'll always chose the (or one of the) unfilled square(s) with the fewest possibilities.
Now we're ready to see the search function:
def search(values):
"Using depth-first search and propagation, try all possible values."
if values is False:
return False ## Failed earlier
if all(len(values[s]) == 1 for s in squares):
return values ## Solved!
## Chose the unfilled square s with the fewest possibilities
_,s = min((len(values[s]), s) for s in squares if len(values[s]) > 1)
return some(search(assign(values.copy(), s, d))
for d in values[s])
That's it! We're done; we can now, in principle, solve every Sudoku puzzle. In practice, on the list of 95 hard puzzles, the code solves about 8 puzzles per second; on easy puzzles it goes through 30 per second. (If I rewrote the code for efficiency it could be 10 times faster, but probably 2 to 5 times longer.) It is possible that there is a puzzle that will take an extremely long time, but I think it is unlikely. In a fraction of a second, the code can solve the empty puzzle (81 unfilled squares) as well as the first five puzzles I found under a search for [hardest sudoku]. In particular, a news article describes what Finnish mathematician Arto Inkala calls "the most difficult sudoku-puzzle known so far"; my program solves it in .013 seconds (averaged over 300 trials).
You can see the complete Python file (100 lines) or the output (1140 lines) from running the Python file on the 95 hard puzzles (95 lines).