Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
Python Sudoku Module
Author Message
smaxd

Posted: Sun Nov 25, 2012 9:19 am   Post subject: Python Sudoku Module

This is a module I made for solving Sudoku puzzles. It is a recursive backtracking search that solves most
puzzles pretty quick. I tried to make it as fast as possible and it manages to solve Al Escargot in around 3 seconds on my comp.
In this version Im computing the domains of each empty cell each time i need them. It might be more ideal to keep the domains in a dict so I
might change that.

 code: from copy import deepcopy, copy from time import clock def parseBoard(data):     """     Takes an iterable (but not string) with string elements.     Parses the data into a 2d list of integers to be processed as Sudoku board.     Returns the board with a list of empty squares.     """         board = [[int(x) for x in line.strip()] for line in data]     emptySquares = list((x,y) for x in range(9) for y in range(9) if board[x][y]==0)     return (board,emptySquares) def possibleValues(board, position):     """     Returns a generator of valid values of the square on the board     at position (row,col).     """         r,c = position     adjacent = tuple(board[r][y] for y in range(9)) + tuple(board[x][c] for x in range(9)) + tuple(board[x][y] for x in range(int(r/3)*3,int(r/3)*3+3) for y in range(int(c/3)*3,int(c/3)*3+3))                                                                 for v in range(1,10):         if v not in adjacent: yield v def leastConstrainingValue(board,cell,value):     """     Function used in calculating least constraining value heuristic.     """         r,c = cell     adjacent = {(r,y) for y in range(9)} | {(x,c) for x in range(9)} | {(x,y) for x in range(int(r/3)*3,int(r/3)*3+3) for y in range(int(c/3)*3,int(c/3)*3+3)}     adjacent.discard(cell)                                                                                                                                                       return sum(1 for near in adjacent if value in possibleValues(board,near))       def solve(board,emptyCells):     """     Returns a solved version of the initial Sudoku board.     Board must be 9*9 grid of integers     """         emptyCells.sort(key = lambda cell: len(list(possibleValues(board,cell))))         if len(emptyCells)==0: return board     else: row,col = emptyCells.pop(0)         for value in sorted(possibleValues(board,(row,col)), key = lambda v: leastConstrainingValue(board,(row,col),v)):         newBoard = deepcopy(board)         newBoard[row][col] = value         newBoard = solve(newBoard,copy(emptyCells))         if newBoard: return newBoard         return False #Used for testing algorithm efficiency. """ board, i = parseBoard(['120400300', '300010050', '006000100', '700090000', '040603000', '003002000', '500080700', '007000005', '000000098']) start = clock() board = solve(board,i) end = clock() for line in board: print(line) print(end-start) """
Sponsor
Sponsor

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 1 of 1  [ 1 Posts ]
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: