Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Python Sudoku Module
Index -> Programming, Python -> Python Submissions
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
smaxd




PostPosted: 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
Sponsor
sponsor
Display posts from previous:   
   Index -> Programming, Python -> Python Submissions
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 1 Posts ]
Jump to:   


Style:  
Search: