Sudoku - Python
A quick little sudoku solver.
#!/usr/bin/env python3 # # Copyright 2012 Cory Lutton # # This program is free software: you can redistribute it and/or modify # it under the terms of the GNU General Public License as published by # the Free Software Foundation, either version 3 of the License, or # (at your option) any later version. # # This program is distributed in the hope that it will be useful, # but WITHOUT ANY WARRANTY; without even the implied warranty of # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the # GNU General Public License for more details. # # You should have received a copy of the GNU General Public License # along with this program. If not, see <http://www.gnu.org/licenses/>. """ Sudoku Solver based on reading: http://norvig.com/sudoku.html Here are the cells, a typical puzzle, and a puzzle solution: A1 A2 A3| A4 A5 A6| A7 A8 A9 4 . . |. . . |8 . 5 4 1 7 |3 6 9 |8 2 5 B1 B2 B3| B4 B5 B6| B7 B8 B9 . 3 . |. . . |. . . 6 3 2 |1 5 8 |9 4 7 C1 C2 C3| C4 C5 C6| C7 C8 C9 . . . |7 . . |. . . 9 5 8 |7 2 4 |3 1 6 ---------+---------+--------- ------+------+------ ------+------+------ D1 D2 D3| D4 D5 D6| D7 D8 D9 . 2 . |. . . |. 6 . 8 2 5 |4 3 7 |1 6 9 E1 E2 E3| E4 E5 E6| E7 E8 E9 . . . |. 8 . |4 . . 7 9 1 |5 8 6 |4 3 2 F1 F2 F3| F4 F5 F6| F7 F8 F9 . . . |. 1 . |. . . 3 4 6 |9 1 2 |7 5 8 ---------+---------+--------- ------+------+------ ------+------+------ G1 G2 G3| G4 G5 G6| G7 G8 G9 . . . |6 . 3 |. 7 . 2 8 9 |6 4 3 |5 7 1 H1 H2 H3| H4 H5 H6| H7 H8 H9 5 . . |2 . . |. . . 5 7 3 |2 9 1 |6 8 4 I1 I2 I3| I4 I5 I6| I7 I8 I9 1 . 4 |. . . |. . . 1 6 4 |8 7 5 |2 9 3 10000 Puzzle file from: http://1gravity.com/index.php?option=com_content&view=article&id=65&Itemid=68 """ __version__ = ".1" import itertools import time class Sudoku: """ A Puzzle Solver """ def __init__(self): self.digits = "123456789" self.rows = "ABCDEFGHI" self.cols = self.digits self.peers = dict([(row + col, self.init_peers(row + col)) for (row, col) in itertools.product(self.rows, self.cols)]) def init_peers(self, cell): """ Initialize the peers - remove the cell post creation """ row, col = cell[0], cell[1] rowslice = self.rows[self.rows.index(row) // 3 * 3: self.rows.index(row) // 3 * 3 + 3] colslice = self.cols[self.cols.index(col) // 3 * 3: self.cols.index(col) // 3 * 3 + 3] # [row] + [col] + [region] peers = ([(r + c) for (r, c) in itertools.product(self.rows, col)] + [(r + c) for (r, c) in itertools.product(row, self.cols)] + [(r + c) for (r, c) in itertools.product(rowslice, colslice)]) peers = sorted([value for value in peers if value != cell]) return peers def reset_cells(self): """ Setup the initial cell values """ cells = dict([(row + col, self.digits) for (row, col) in itertools.product(self.rows, self.cols)]) return cells def solve(self, line): """ Solve the puzzle """ cells = self.reset_cells() self.puzzle = line self.solution = "" for i, cell in enumerate(sorted(cells)): if(line[i] != "0"): cells = self.assign_value(cells, cell, line[i]) if not cells: print("Impossible first values") return # Brute Force Search for solution cells = self.search(cells) for cell in sorted(cells): self.solution += cells[cell] self.printout() def search(self, cells, depth=0): """ Perform a recursive search. """ for cell in sorted(cells): # Only look in cells with no value already if len(cells[cell]) == 1: continue for p in cells[cell]: tcells = cells.copy() tcells[cell] = tcells[cell].replace(p, "") cells = self.assign_value(cells, cell, p) if cells: # Continue Forward cells = self.search(cells, depth + 1) if not cells: # Revert back cells = tcells if len(cells[cell]) is not 1: # No solution found return False return cells def assign_value(self, cells, cell, value): """ Assign value to a cell, adjust all peers. """ cells[cell] = value for peer in self.peers[cell]: # Conflict Detected - a peer has this answer if(cells[peer] == value): return False if(value in cells[peer]): cells[peer] = cells[peer].replace(value, "") # Propigate if(len(cells[peer]) == 1): return self.assign_value(cells, peer, cells[peer]) # Conflict Detected - a peer has no possibilities when this happens if(cells[peer] == ""): return False return cells def printout(self): """ Print the puzzle and solution """ print(self.puzzle) print(self.solution) def solve_all(s): for puzzle, line in enumerate(open("puzzles.txt")): puzzletime = time.time() s.solve(line.strip()) print("Puzzle " + str(puzzle) + " Runtime :" + str(time.time() - puzzletime), "\n") if(puzzle > 99): break def tests(s): line = "200040005506100000001002080000001200000000063304000050030007840002604000000090002" solu = "283746915546189327791352684657431298918275463324968751139527846872614539465893172" s.solve(line) if(s.solution == solu): print("Correct") line = "980000006000030080030002900020097000300000004000450060008300050060070000100000048" solu = "982715436547936281631842975824697513356281794719453862298364157465178329173529648" s.solve(line) if(s.solution == solu): print("Correct") line = "081600090000000000004037600600400500030000070007002004005210300000000000070004810" solu = "281645793763928145594137628629473581438591276157862934845219367312786459976354812" s.solve(line) if(s.solution == solu): print("Correct") line = "000200041000070006002005080300000008040003600006050070000080010908004200170500000" solu = "785269341439871526612345987351627498847193652296458173523986714968714235174532869" s.solve(line) if(s.solution == solu): print("Correct") line = "000190000010000090000030801060004930005080100094500080903040000020000070000059000" solu = "638192754412875693759436821861724935275983146394561287983647512526318479147259368" s.solve(line) if(s.solution == solu): print("Correct") def main(): s = Sudoku() #solve_all(s) tests(s) if __name__ == "__main__": #import cProfile #cProfile.run('main()') main()