#!/usr/bin/env python # Author: Brian Schott # Date: April 9, 2007 # License: # This program is free software; you can redistribute it and/or # modify it under the terms of the GNU General Public License version # 2 as published by the Free Software Foundation. # # 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 gtk import sys class Sudoku: def __init__(self): self.array = [[0 for i in range(9)] for i in range(9)] def setCell(self, x, y, n): self.array[x][y] = n # Solves the puzzle recursively. # This is somewhat of a brute-force method, but it works def solve(self, x, y): if (self.checkColumn(x) == True and self.checkRow(y) == True and \ self.checkBlock(x/3, y/3) == True): if self.checkFull() == True: # The puzzle is solved return True else: # The puzzle in its current state cannot be solved return False for x in range(9): for y in range(9): if self.array[x][y] == 0: # This code will only try to fill in one blank cell for n in range(1, 10): # It tries every valid value in the cell self.array[x][y] = n if self.solve(x, y) == True: return True else: # This branch of the recursion produced an # unsolvable puzzle. Reset this cell to blank and # try again self.array[x][y] = 0 if n == 9: # If n reaches 9 return False return False """Checks that a given row does not invalidate the puzzle. Returns False if the puzzle is invalid, True otherwise""" def checkRow(self, y): usedList = [False for i in range(10)] for x in range(9): if self.array[x][y] != 0: if usedList[self.array[x][y]] == True: return False else: usedList[self.array[x][y]] = True return True def checkColumn(self, x): """Checks that a given column does not invalidate the puzzle. Returns False if the puzzle is invalid, True otherwise""" usedList = [False for i in range(10)] for y in range(9): if self.array[x][y] != 0: if usedList[self.array[x][y]] == True: return False else: usedList[self.array[x][y]] = True return True def checkBlock(self, i, j): x1 = i * 3 x2 = x1 + 3 y1 = j * 3 y2 = y1 + 3 usedList = [False for i in range(10)] for x in range(x1, x2): for y in range(y1, y2): if self.array[x][y] != 0: if usedList[self.array[x][y]] == True: return False else: usedList[self.array[x][y]] = True return True def check(self): for x in range(9): if self.checkColumn(x) != True: return False for y in range(9): if self.checkRow(y) != True: return False for x in range(3): for y in range(3): if self.checkBlock(x, y) != True: return False return True # I don't claim that this is efficient... def checkFull(self): for i in self.array: for j in i: if j == 0: return False return True # This is useful for making a command-line version of the program def string(self): s = "" for y in range(9): for x in range(9): s = s + "%d " % self.array[x][y] s = s + '\n' return s class SudokuInterface(gtk.Window): def __init__(self): gtk.Window.__init__(self, gtk.WINDOW_TOPLEVEL) self.set_title("Sudoku Solver") self.entries = [[gtk.Entry() for i in range(9)] for j in range(9)] self.sudoku = Sudoku() vbox = gtk.VBox(False, 2) for i in range(3): hbox = gtk.HBox(True, 2) for j in range(3): hbox.add(self.buildFrame(j, i)) vbox.add(hbox) for i in self.entries: for j in i: j.set_max_length(1) j.set_width_chars(2) j.set_text("0") self.statusEntry = gtk.Entry() self.statusEntry.set_text("Python is slower than Java or C++.") buttonBox = gtk.HBox() self.solveButton = gtk.Button("Solve"); self.solveButton.connect("clicked", self.solve) self.checkButton = gtk.Button("Check"); self.checkButton.connect("clicked", self.check) self.resetButton = gtk.Button("Reset") self.resetButton.connect("clicked", self.reset) buttonBox.add(self.resetButton) buttonBox.add(self.checkButton) buttonBox.add(self.solveButton) frame = gtk.Frame() tempBox = gtk.VBox() tempBox.add(self.statusEntry) tempBox.add(buttonBox) frame.add(tempBox) vbox.add(frame) self.add(vbox) self.connect("delete_event", gtk.main_quit) self.show_all() # x and y are either 0, 1, or 2 def buildFrame(self, x, y): frame = gtk.Frame() vbox = gtk.VBox() for b in range((y * 3), (y * 3) + 3): hbox = gtk.HBox() for a in range((x * 3), (x * 3) + 3): hbox.add(self.entries[a][b]) vbox.add(hbox) frame.add(vbox) return frame def solve(self, data): self.loadPuzzle() self.statusEntry.set_text("Solving...") if self.sudoku.solve(0, 0): self.statusEntry.set_text("Solved") self.displayPuzzle() else: self.statusEntry.set_text("The puzzle is not solvable") """This is attached to the "Check" button""" def check(self, data): self.loadPuzzle() if self.sudoku.check(): self.statusEntry.set_text("The puzzle is solvable") else: self.statusEntry.set_text("The puzzle is not solvable") """Parses the values from the text entries and loads them into the puzzle""" def loadPuzzle(self): for x in range(9): for y in range(9): if self.entries[x][y] != "": try: n = int(self.entries[x][y].get_text()) self.sudoku.setCell(x, y, n) except ValueError: self.statusEntry.set_text("Invalid entry in cell\ (%d,%d" % (x, y)) else: self.sudoku.setCell(x, y, 0) """Takes the values from the puzzle and loads them back into the text entries""" def displayPuzzle(self): for y in range(9): for x in range(9): self.entries[x][y].set_text("%d" % (self.sudoku.array[x][y])) """Resets all the cells in the puzzle to 0""" def reset(self, stuff): for i in self.entries: for j in i: j.set_text("0") if __name__ == "__main__": s = SudokuInterface() gtk.main()