Sudoku Sovler

sudoku_backtrack.py

import os,time

count = 0
def printBoard(b):
    print " "
    for i in b:
        for x in i:
            print str(x)+" ",
        print " "
    print " "

def validMove(board,x,y,n):
    for i in range(0,9):
        if board[i][y] == n:
            return False
        if board[x][i] == n:
            return False
    for i in range(0,3):
        for j in range(0,3):
            if board[((x/3)*3)+i][((y/3)*3)+j] == n:
                return False
    return True

def main():
    global count
    f = open("puzzle.txt","r")
    
    for s in f:
        board = [[int(s[j*9+i]) for i in range(9)] for j in range(9)]
        printBoard(board)
        solve(board,0,0)
        count+=1
        printBoard(board)
   
    #for i in range(50):
        

def solve(board,x,y):
    if x==9:
        x=0
        y+=1
        if y==9:
            return True
    if board[x][y] != 0:
        return solve(board,x+1,y)
    else:
        for i in range(1,10):
            if validMove(board,x,y,i):
                board[x][y] = i
                if solve(board,x+1,y):
                    return True
    board[x][y] = 0
    return False


if __name__ == "__main__":
    start = time.time()
    main()
    end = time.time()
    elapsed = end - start
    print "Solved "+str(count)+" puzzles"
    print "Time taken: ", elapsed, "seconds"