|
| 1 | +## Solve Every Sudoku Puzzle |
| 2 | + |
| 3 | +## See http://norvig.com/sudoku.html |
| 4 | + |
| 5 | +## Throughout this program we have: |
| 6 | +## r is a row, e.g. 'A' |
| 7 | +## c is a column, e.g. '3' |
| 8 | +## s is a square, e.g. 'A3' |
| 9 | +## d is a digit, e.g. '9' |
| 10 | +## u is a unit, e.g. ['A1','B1','C1','D1','E1','F1','G1','H1','I1'] |
| 11 | +## grid is a grid,e.g. 81 non-blank chars, e.g. starting with '.18...7... |
| 12 | +## values is a dict of possible values, e.g. {'A1':'12349', 'A2':'8', ...} |
| 13 | + |
| 14 | +import os |
| 15 | + |
| 16 | +def cross(A, B): |
| 17 | + "Cross product of elements in A and elements in B." |
| 18 | + return [a+b for a in A for b in B] |
| 19 | + |
| 20 | +digits = '123456789' |
| 21 | +rows = 'ABCDEFGHI' |
| 22 | +cols = digits |
| 23 | +squares = cross(rows, cols) |
| 24 | +unitlist = ([cross(rows, c) for c in cols] + |
| 25 | + [cross(r, cols) for r in rows] + |
| 26 | + [cross(rs, cs) for rs in ('ABC','DEF','GHI') for cs in ('123','456','789')]) |
| 27 | +units = dict((s, [u for u in unitlist if s in u]) |
| 28 | + for s in squares) |
| 29 | +peers = dict((s, set(sum(units[s],[]))-set([s])) |
| 30 | + for s in squares) |
| 31 | + |
| 32 | +################ Unit Tests ################ |
| 33 | + |
| 34 | +def test(): |
| 35 | + "A set of tests that must pass." |
| 36 | + assert len(squares) == 81 |
| 37 | + assert len(unitlist) == 27 |
| 38 | + assert all(len(units[s]) == 3 for s in squares) |
| 39 | + assert all(len(peers[s]) == 20 for s in squares) |
| 40 | + assert units['C2'] == [['A2', 'B2', 'C2', 'D2', 'E2', 'F2', 'G2', 'H2', 'I2'], |
| 41 | + ['C1', 'C2', 'C3', 'C4', 'C5', 'C6', 'C7', 'C8', 'C9'], |
| 42 | + ['A1', 'A2', 'A3', 'B1', 'B2', 'B3', 'C1', 'C2', 'C3']] |
| 43 | + assert peers['C2'] == set(['A2', 'B2', 'D2', 'E2', 'F2', 'G2', 'H2', 'I2', |
| 44 | + 'C1', 'C3', 'C4', 'C5', 'C6', 'C7', 'C8', 'C9', |
| 45 | + 'A1', 'A3', 'B1', 'B3']) |
| 46 | + print('All tests pass.') |
| 47 | + |
| 48 | +################ Parse a Grid ################ |
| 49 | + |
| 50 | +def parse_grid(grid): |
| 51 | + """Convert grid to a dict of possible values, {square: digits}, or |
| 52 | + return False if a contradiction is detected.""" |
| 53 | + ## To start, every square can be any digit; then assign values from the grid. |
| 54 | + values = dict((s, digits) for s in squares) |
| 55 | + for s,d in list(grid_values(grid).items()): |
| 56 | + if d in digits and not assign(values, s, d): |
| 57 | + return False ## (Fail if we can't assign d to square s.) |
| 58 | + return values |
| 59 | + |
| 60 | +def grid_values(grid): |
| 61 | + "Convert grid into a dict of {square: char} with '0' or '.' for empties." |
| 62 | + chars = [c for c in grid if c in digits or c in '0.'] |
| 63 | + assert len(chars) == 81 |
| 64 | + return dict(list(zip(squares, chars))) |
| 65 | + |
| 66 | +################ Constraint Propagation ################ |
| 67 | + |
| 68 | +def assign(values, s, d): |
| 69 | + """Eliminate all the other values (except d) from values[s] and propagate. |
| 70 | + Return values, except return False if a contradiction is detected.""" |
| 71 | + other_values = values[s].replace(d, '') |
| 72 | + if all(eliminate(values, s, d2) for d2 in other_values): |
| 73 | + return values |
| 74 | + else: |
| 75 | + return False |
| 76 | + |
| 77 | +def eliminate(values, s, d): |
| 78 | + """Eliminate d from values[s]; propagate when values or places <= 2. |
| 79 | + Return values, except return False if a contradiction is detected.""" |
| 80 | + if d not in values[s]: |
| 81 | + return values ## Already eliminated |
| 82 | + values[s] = values[s].replace(d,'') |
| 83 | + ## (1) If a square s is reduced to one value d2, then eliminate d2 from the peers. |
| 84 | + if len(values[s]) == 0: |
| 85 | + return False ## Contradiction: removed last value |
| 86 | + elif len(values[s]) == 1: |
| 87 | + d2 = values[s] |
| 88 | + if not all(eliminate(values, s2, d2) for s2 in peers[s]): |
| 89 | + return False |
| 90 | + ## (2) If a unit u is reduced to only one place for a value d, then put it there. |
| 91 | + for u in units[s]: |
| 92 | + dplaces = [s for s in u if d in values[s]] |
| 93 | + if len(dplaces) == 0: |
| 94 | + return False ## Contradiction: no place for this value |
| 95 | + elif len(dplaces) == 1: |
| 96 | + # d can only be in one place in unit; assign it there |
| 97 | + if not assign(values, dplaces[0], d): |
| 98 | + return False |
| 99 | + return values |
| 100 | + |
| 101 | +################ Display as 2-D grid ################ |
| 102 | + |
| 103 | +def display(values): |
| 104 | + "Display these values as a 2-D grid." |
| 105 | + width = 1+max(len(values[s]) for s in squares) |
| 106 | + line = '+'.join(['-'*(width*3)]*3) |
| 107 | + for r in rows: |
| 108 | + print(''.join(values[r+c].center(width)+('|' if c in '36' else '') |
| 109 | + for c in cols)) |
| 110 | + if r in 'CF': print(line) |
| 111 | + print() |
| 112 | + |
| 113 | +################ Search ################ |
| 114 | + |
| 115 | +def solve(grid): return search(parse_grid(grid)) |
| 116 | + |
| 117 | +def search(values): |
| 118 | + "Using depth-first search and propagation, try all possible values." |
| 119 | + if values is False: |
| 120 | + return False ## Failed earlier |
| 121 | + if all(len(values[s]) == 1 for s in squares): |
| 122 | + return values ## Solved! |
| 123 | + ## Chose the unfilled square s with the fewest possibilities |
| 124 | + n,s = min((len(values[s]), s) for s in squares if len(values[s]) > 1) |
| 125 | + return some(search(assign(values.copy(), s, d)) |
| 126 | + for d in values[s]) |
| 127 | + |
| 128 | +################ Utilities ################ |
| 129 | + |
| 130 | +def some(seq): |
| 131 | + "Return some element of seq that is true." |
| 132 | + for e in seq: |
| 133 | + if e: return e |
| 134 | + return False |
| 135 | + |
| 136 | +def from_file(filename, sep='\n'): |
| 137 | + "Parse a file into a list of strings, separated by sep." |
| 138 | + with open(filename) as f: |
| 139 | + return f.read().strip().split(sep) |
| 140 | + |
| 141 | +def shuffled(seq): |
| 142 | + "Return a randomly shuffled copy of the input sequence." |
| 143 | + seq = list(seq) |
| 144 | + random.shuffle(seq) |
| 145 | + return seq |
| 146 | + |
| 147 | +################ System test ################ |
| 148 | + |
| 149 | +import time, random |
| 150 | +from concurrent.futures import ThreadPoolExecutor |
| 151 | + |
| 152 | + |
| 153 | +def solve_all(grids, name='', showif=0.0, nbthreads=1): |
| 154 | + """Attempt to solve a sequence of grids. Report results. |
| 155 | + When showif is a number of seconds, display puzzles that take longer. |
| 156 | + When showif is None, don't display any puzzles.""" |
| 157 | + def time_solve(grid): |
| 158 | + start = time.time() |
| 159 | + values = solve(grid) |
| 160 | + t = time.time()-start |
| 161 | + ## Display puzzles that take long enough |
| 162 | + if showif is not None and t > showif: |
| 163 | + display(grid_values(grid)) |
| 164 | + if values: display(values) |
| 165 | + print('(%.2f seconds)\n' % t) |
| 166 | + return (t, solved(values)) |
| 167 | + with ThreadPoolExecutor(max_workers=nbthreads) as e: |
| 168 | + times, results = zip(*e.map(time_solve, grids)) |
| 169 | + N = len(grids) |
| 170 | + if N > 1: |
| 171 | + print("Solved %d of %d %s puzzles (avg %.2f secs (%d Hz), max %.2f secs)." % ( |
| 172 | + sum(results), N, name, sum(times)/N, N/sum(times), max(times))) |
| 173 | + |
| 174 | +def solved(values): |
| 175 | + "A puzzle is solved if each unit is a permutation of the digits 1 to 9." |
| 176 | + def unitsolved(unit): return set(values[s] for s in unit) == set(digits) |
| 177 | + return values is not False and all(unitsolved(unit) for unit in unitlist) |
| 178 | + |
| 179 | +def random_puzzle(N=17): |
| 180 | + """Make a random puzzle with N or more assignments. Restart on contradictions. |
| 181 | + Note the resulting puzzle is not guaranteed to be solvable, but empirically |
| 182 | + about 99.8% of them are solvable. Some have multiple solutions.""" |
| 183 | + values = dict((s, digits) for s in squares) |
| 184 | + for s in shuffled(squares): |
| 185 | + if not assign(values, s, random.choice(values[s])): |
| 186 | + break |
| 187 | + ds = [values[s] for s in squares if len(values[s]) == 1] |
| 188 | + if len(ds) >= N and len(set(ds)) >= 8: |
| 189 | + return ''.join(values[s] if len(values[s])==1 else '.' for s in squares) |
| 190 | + return random_puzzle(N) ## Give up and make a new puzzle |
| 191 | + |
| 192 | +grid1 = '003020600900305001001806400008102900700000008006708200002609500800203009005010300' |
| 193 | +grid2 = '4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......' |
| 194 | +hard1 = '.....6....59.....82....8....45........3........6..3.54...325..6..................' |
| 195 | +hard2 = '8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4..' |
| 196 | + |
| 197 | +if __name__ == '__main__': |
| 198 | + test() |
| 199 | + nbsudoku = 40 |
| 200 | + thread_list = ( 1, 2, 4, 8, 16) |
| 201 | + print(f'there is {os.cpu_count()} logical processors, {os.cpu_count()/2} physical processors') |
| 202 | + reference_delta = 0 |
| 203 | + for nbthreads in thread_list: |
| 204 | + startall = time.time() |
| 205 | + solve_all([hard2]*nbsudoku, "hard2", None, nbthreads=nbthreads) |
| 206 | + new_delta = time.time()-startall |
| 207 | + if reference_delta ==0 : |
| 208 | + reference_delta = new_delta |
| 209 | + ratio = reference_delta/(new_delta) |
| 210 | + print(f'solved {nbsudoku} tests with {nbthreads} threads in {new_delta:.2f} seconds, {ratio:.2f} speed-up' + '\n') |
| 211 | + |
| 212 | + |
| 213 | +## References used: |
| 214 | +## http://www.scanraid.com/BasicStrategies.htm |
| 215 | +## http://www.sudokudragon.com/sudokustrategy.htm |
| 216 | +## http://www.krazydad.com/blog/2005/09/29/an-index-of-sudoku-strategies/ |
| 217 | +## http://www2.warwick.ac.uk/fac/sci/moac/currentstudents/peter_cock/python/sudoku/ |
0 commit comments