#!/usr/bin/python## This programs solves SuDoku problems as seen in The Times.# It takes a filename as an argument.## sudoku.py puzzle.txt## The file should contain a 9x9 grid of numbers at _s for blank spaces# A simple example is given below.# # _ 2 _ 8 1 _ 7 4 _# 7 _ _ _ _ 3 1 _ _# _ 9 _ _ _ 2 8 _ 5# _ _ 9 _ 4 _ _ 8 7# 4 _ _ 2 _ 8 _ _ 3# 1 6 _ _ 3 _ 2 _ _# 3 _ 2 7 _ _ _ 6 _# _ _ 5 6 _ _ _ _ 8# _ 7 6 _ 5 1 _ 9 _# Sudoku.py - A Sudoku solver written in Python# 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 2# 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, write to the Free Software# Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.import Queue, bisect, copy#class PriorityQueue(Queue.Queue):# def _put(self, item):# bisect.insort(self.queue, item)class PriorityQueue(list): def put(self, item): bisect.insort(self, item) def get(self): item = self[0] del self[0] return itemmemo = ([], [([False for x in range(9)], [False for x in range(9)], [[False for x in range(3)] for x in range(3)]) for n in range(9)])def readFile(filename): fp = open(filename) data = fp.read() fp.close() table = [] for line in data.split("\n"): row = [] if line == "": continue for element in line.split(" "): if element == "_": row.append(None) elif element.strip() == "": pass else: row.append(int(element)) assert len(row) == 9 table.append(row) assert len(table) == 9 return tabledef printTable(initial, table): print "------------------------------------------------------------------" for y in range(len(table)): for x in range(len(table[y])): if table[y][x] is None: print "_\t", elif initial[y][x] is None: print table[y][x]+1, "\t", else: print "%c[33;1m%i%c[0m\t" % (27, table[y][x]+1, 27), print "" print "------------------------------------------------------------------"def prefill(memo, table): for y in range(9): for x in range(9): v = table[y][x] if v is None: memo[0].append((x,y)) continue assert v >= 1 and v <= 9 v = v - 1 table[y][x] = v memo[1][v][0][x] = True memo[1][v][1][y] = True memo[1][v][2][x/3][y/3] = True return len(memo[0])def findSpace(memo, table): if len(memo[0]) == 0: return None else: return iter(memo[0])def chooseNumber(memo, x, y): return filter(lambda n: not memo[1][n][0][x] and not memo[1][n][1][y] and not memo[1][n][2][x/3][y/3], range(9))tries = 0def markNumber(n, x, y, memo, table): global tries tries += 1 print "\r", tries, table[y][x] = n memo[0].remove((x,y)) memo[1][n][0][x] = True memo[1][n][1][y] = True memo[1][n][2][x/3][y/3] = Truedef clearNumber(n, x, y, memo, table): table[y][x] = None memo[0].append((x,y)) memo[1][n][0][x] = False memo[1][n][1][y] = False memo[1][n][2][x/3][y/3] = Falsedef solve(memo, table, depth=0): fs = findSpace(memo, table) if fs is None: print "\nSolution after %i tries" % (tries, ) printTable(initial, table) return queue = PriorityQueue() for x, y in fs: nums = list(chooseNumber(memo, x, y)) if len(nums) == 0: return queue.put((len(nums), x, y, nums)) c, x, y, nums = queue.get() for n in nums: markNumber(n, x, y, memo, table) solver = solve(memo, table, depth+1) clearNumber(n, x, y, memo, table)import systable = readFile(sys.argv[1])print "Minimum solve: ", prefill(memo, table)initial = copy.deepcopy(table)solver = solve(memo, table)print "No more solutions after %i tries" % (tries, )