## SUDOKU SOLVER # George Wong # imports board and checks for errors def errcheck(board): for a in range(0,9): for b in range(0,9): rowconts = [] colconts = [] boxconts = [] for i in range(0,9): rowconts.append(board[a][i]) for i in range(0,9): colconts.append(board[i][b]) for d in range(0,3): for e in range(0,3): boxconts.append(board[i/3+d][i/3+e]) if((board[a][b] in rowconts) or (board[a][b] in colconts) or (board[a][b] in boxconts)): return True # True means there's an error return False # allows importation of board via user def makeboard(): finalarray = [] print('\nNote you may not name the board \'null\'.') filename = 'null' while(filename == 'null'): filename = raw_input('Enter a name to save the file as: ') board = open(filename, 'w') print 'Enter the values in each row with \'0\' in the place of spaces' print 'e.g. 003245100 == _ _ 3 | 2 4 5 | 1 _ _' for i in range(0,9): row = [] rawrow = raw_input('Enter row: ') board.write(rawrow) board.write('\n') for a in rawrow: row.append(a) finalarray.append(row) board.close() return finalarray,filename # reads text file board into array def readboard(filename): if filename == 'null': filename = raw_input('Board Filename: ') boardstr = open(filename, 'r') board = [] for line in boardstr: lineinboard = [] for char in line: if char.isdigit(): lineinboard.append(int(char)) board.append(lineinboard) boardstr.close() return board # imports the board and prints it to the screen def printboard(board): print chr(201)+chr(205)*17+chr(187) rowcount = 0 for row in board: rowcount += 1 rowstr = chr(186) digitcount = 0 for digit in row: digitcount += 1 if(digit==0): rowstr += '_' else: rowstr += str(digit) if(digitcount==3 or digitcount==6): rowstr += chr(179) elif(digitcount==9): rowstr += chr(186) else: rowstr += ' ' print rowstr if(rowcount==3 or rowcount==6): print chr(186)+(chr(196)*5+chr(197))*2+chr(196)*5+chr(186) elif(rowcount==9): print chr(200)+chr(205)*17+chr(188) # imports board and position, returns def checkbox(a,b,board): possibilities = [1,2,3,4,5,6,7,8,9] # check row for c in range(0,9): if(board[a][c] in possibilities): possibilities.remove(board[a][c]) # check column for c in range(0,9): if(board[c][b] in possibilities): possibilities.remove(board[c][b]) # check 3x3 # :find which 3x3 we're in... for c in range(0,3): for d in range(0,3): # look in the 3x3 for the proper 3x3 if(board[c+(a/3)*3][d+(b/3)*3] in possibilities): possibilities.remove(board[c+(a/3)*3][d+(b/3)*3]) # we should be done return possibilities # returning the board or 'ZERO' if bad def stdcheck(board): change = True while(change): change = False for a in range(0,9): for b in range(0,9): if(board[a][b]==0): pos = checkbox(a,b,board) if(len(pos)==1): board[a][b] = pos[0] change = True elif(len(pos)==0): #error return board #check later to see if there's a change return board #imports the board and returns True if def checkdone(board): for a in range(0,9): for b in range(0,9): if(board[a][b] == 0): return False return True ## GUESSING STUFF def Niserr(num,a,b,board): #NOT iserror boxnums = [] rownums = [] for c in range(0,9): rownums.append(board[a][c]) #populate list rownums.remove(num) #because we loaded it checkrows = [x for x in range(0,9) if x != a] #print checkrows if num in rownums: return False # if error in row, return bad for rp in checkrows: if board[rp][b] == num: return False #cols for rowmod in range(0,3): for colmod in range(0,3): boxnums.append(board[(a/3)*3+rowmod][(b/3)*3+colmod]) #populate list boxnums.remove(num) #because it's already in there if num in boxnums: return False return True def guess_iterative(iteration,board,unknowns): #just keeps guessing # we return True when we run out of iterations/it hits the full extent of # unknown arrays if iteration == len(unknowns): return True # reading from the unknowns array what the row and col # that we should check from later a = unknowns[iteration][0] b = unknowns[iteration][1] for num in range(1,10): board[a][b] = num if((Niserr(num,a,b,board)) and (guess_iterative(iteration+1,board,unknowns))): return True # we failed with this guessing set, let's move on to the next, but # we first have to remember to reset this specific square if(num == 9): board[a][b] = 0 return False ## main getboard = 'K' while((getboard != 'C') or (getboard != 'L')): getboard = raw_input('Enter C to make a board, L to load: ') if(getboard==('C' or 'c')): board,fname = makeboard() #returns the filename and the board board = readboard(fname) break elif(getboard==('L' or 'l')): board = readboard('null') break print '\nloaded:' printboard(board) ## easy stuff board = stdcheck(board) if(checkdone(board)): if(errcheck(board)): print '\nelimination returned:' printboard(board) else: print '\nError occured somewhere along the line...' else: print '\neasy-elimination failed: we have to guess' # create array of all unknown possibilities unknowns = [] for a in range(0,9): for b in range(0,9): if(board[a][b]==0): unknowns.append((a,b)) # if(guess_iterative(0,board,unknowns)): print '\nreturned:' if(errcheck(board)): printboard(board) else: print '\nError occured somewhere along the line...' else: print '\nerror! the entered puzzle is not solvable' omega = raw_input('\n\nPress return to end the program...')