#!/usr/bin/python # tz_sudoku.py # --copyright-- Copyright 2007 (C) Tranzoa, Co. All rights reserved. Warranty: You're free and on your own here. This code is not necessarily up-to-date or of public quality. # --url-- http://www.tranzoa.net/tzpython/ # --email-- pycode is the name to send to. tranzoa.com is the place to send to. # --bodstamps-- # June 20, 2007 bar stop playing this game # June 21, 2007 bar improve read_board # November 4, 2007 bar different metrics # file outout # keyboard break in creation # November 5, 2007 bar notes # November 6, 2007 bar more metrics # November 12, 2007 bar symetry metric # November 23, 2007 bar allow '0' to fill space on input board # November 26, 2007 bar oooo how did it run with a bad parameter to solve_board()? # November 30, 2007 bar don't try to print a bad board solution # print 2nd possible ambiguous board solution # change program name and put in tzpython # do multiple boards # help_str # December 1, 2007 bar use tzlib's elapsed_time for timing # April 20, 2008 bar comments and change the param order for solve_board() to make more sense, even if the params don't, themselves # x_shape # May 17, 2008 bar email adr # --eodstamps-- # # # # Run with -c or --create to create a puzzle # # Otherwise, solve one. # The input looks like this (spaces, dashes, pipes, and blank lines and lines beginning with semi-colon don't count): # # 24.3..... # 3......8. # 5.......7 # ..5.71.6. # ...4....5 # ......9.. # .....63.. # .71...... # 9....8.42 # # # Ideas: # # Have the thing produce solutions that are similar to other solutions # # Metrics # # fullest puzzle group(s) filled in already # most use of particular value(s) # most symetric (shape first) # most X type patterns of the 10 symbols (normalizing for rotations and reflections) # # Web: # # give rotations of same puzzle # show numbers as pictures or symbols or colors or whatever # # import copy import re import random import sys import time from threading import * import tzlib sys.stderr = sys.stdout # because I run this thing in the background, sorta, all the time, generating 'em every few hours cmt_re = re.compile(r"(^|\n)\s*;[^\n]*", re.DOTALL) def all_numbers_dict() : return(tzlib.make_dictionary( [ v for v in xrange(1, 10) ] )) def new_board() : return( [ all_numbers_dict() for i in xrange(9 * 9) ] ) # # Construct neighbor array - this is an array of arrays of board cell indices that can't have the same value as the indexed item in the array. # [ 9 * 9][n] That is, where all the 'n' elements are the board indices of the cells that can't have the same value as the [9*9] index. # xneys = [] for i in xrange(9 * 9) : neys = [ (i / 9) * 9 + r for r in xrange(9) ] # all items in the same row neys += [ (i % 9) + c for c in xrange(0, 9 * 9, 9) ] # all items in the same column rci = (i / (9 * 3)) * 9 * 3 + ((i % 9) / 3) * 3 # calculate the nw corner of the square this item is in neys += [ rci + r for r in xrange(3) ] # the 3 in the top row of the square rci += 9 neys += [ rci + r for r in xrange(3) ] # the 3 in the middle row of the square rci += 9 neys += [ rci + r for r in xrange(3) ] # the 3 in the bottom row of the square neys = tzlib.make_dictionary(neys) # uniquify them del(neys[i]) # don't include this item, itself neys = neys.keys() neys.sort() # put them in numeric order (needed? probably, for the test of whether there can be a solution) # print neys xneys.append(neys) # # Construct groups # groups = [] for r in xrange(3) : for c in xrange(3) : b = r * 27 + c * 3 g = [ b , b + 1, b + 2, b + 9, b + 10, b + 11, b + 18, b + 19, b + 20, ] groups.append(g) # add this square to the list pass groups += [ [ c + (r * 9) for r in xrange(9) ] for c in xrange(9) ] # add all the rows groups += [ [ (c * 9) + r for r in xrange(9) ] for c in xrange(9) ] # add all the columns def board_str(brd) : """ Return a string that is a pretty-print of the given board. """ ps = "\n" ps += " " + "-" * 25 + "\n" for rl in xrange(3) : for r in xrange(3) : for cl in xrange(3) : ps += " |" for c in xrange(3) : i = (rl * 3 + r) * 9 + cl * 3 + c if len(brd[i]) > 1 : ps += " ." elif not len(brd[i]) : ps += " *" else : ps += " %u" % ( brd[i].keys()[0] ) pass pass ps += " |" + "\n" ps += " " + "-" * 25 + "\n" return(ps) def show_board(brd) : """ Print the board. """ print board_str(brd) def board_spec_str(brd) : """ Return a string that specifies the given board in a way that we take as input. """ ps = "" i = 0 for r in xrange(9) : for c in xrange(9) : bc = brd[i] if len(bc) == 1 : ps += str(bc.keys()[0]) else : ps += "." i += 1 ps += "\n" return(ps) def read_board(s) : """ Do the best we can to try to read the board from a text string. A board is a 9*9 array of dictionaries keyed by the numbers that may be in the cell. """ s = s.replace("\r", "\n") s = s.replace(" ", "") s = s.replace("0", ".") s = cmt_re.sub("", s) s = s.replace("-", "").strip() s = s.replace("|", "").strip() s = re.sub(r"\n+", "\n", s) sa = s.split("\n") if len(sa) > 9 : print sa raise "Too many rows %u" % ( len(sa) ) + str(sa) for si in xrange(len(sa)) : s = sa[si] if len(s) > 9 : raise "Too many columns on line %u: %s" % ( si, s ) pass brd = new_board() i = 0 for r in xrange(len(sa)) : for c in xrange(9) : if c < len(sa[r]) : if re.match(r"\d", sa[r][c]) : brd[i] = { int(sa[r][c]) : int(sa[r][c]) } # print brd[i] i += 1 # print pass return(brd) def elim_simple(brd) : """ For each group (rows, columns, squares), set the board's cells to single values if the cell is the only one in the group that can have the value. """ done_one = False for g in groups : pvs = [ [] for i in xrange(10) ] # possible values: we'll track how many of the group's cells can have each value for i in g : for v in brd[i].keys() : pvs[v].append(i) # note the cell the value can be in pass for v in xrange(1, 10) : pis = pvs[v] if len(pis) == 1 : # if the value can only be in 1 cell i = pis[0] if len(brd[i]) > 1 : # if we didn't know that, then brd[i] = { v : True } # mark the cell as being this value. done_one = True # and tell the caller that we changed the board pass elif not len(pis) : return(None) # no cell in the group can have this value (impossible board) pass pass return(done_one) def simple_pass(brd) : """ This routine is the only "brains" of the program. It simply goes in to a loop that ends when nothing is changed by: Take away possible value from cells that are "neighbors" of cells that are of known values. Set cells to one value if they are in a group that does not contain other cells that can have the value. In other words, it only makes legal changes to the board at the dumbest level. """ done_one = True while done_one : done_one = False sc = [] for i in xrange(len(brd)) : bc = brd[i] if len(bc) == 1 : # the cell is known, take its value away from the possible values of all neighbors. v = bc.keys()[0] for n in xneys[i] : # for all neighbors of the cell if brd[n].has_key(v) : # if the neighbor thinks it can be the value, # print "whacking", n / 9, n % 9, v, len(brd[n]), i / 9, i % 9 del(brd[n][v]) # tell the neighbor otherwise. if not len(brd[n]) : # and tell the caller if this board is impossible (as the neighbor has run out of possibilities) # print "too many whacks" return(None) done_one = True pass pass else : if len(bc) == 0 : raise "lenbc==0 %u %u" % ( i / 9, i % 9 ) sc.append( [ len(bc), i ] ) # keep track of cells that are not solved yet pass r = elim_simple(brd) if r == None : return(None) # tell caller that board is impossible done_one = done_one or r return(sc) # if len(sc)==0 we have found the solution. sc is an array of [ number of possible values, cell number ] arrays, an item for each unknown-value cell def solve_board(brd, cell = 0, # if 'cell' is < 0, choose a cell at random to try a possible value (and the value is randomly chosen from the possible values). # if 'cell' is >= 0, then at the top depth, try a possible value for the top-leftest ambiguous cell at 'cell' location in the simple_pass return array or beyond # and use 'ni' to choose the value to try. ni = 1, # if 'cell' is >= 0, then if ni==1, try the first keys() possible value, otherwise, try the ni'th sorted possible value. rbrd = None, # a_random_boarder, so we can kick out if the random board generator is told to stop. depth = 0 # for printout/debug purposes. ) : """ Return the board, solved, or None if the board is impossible. """ # # Set the recursion values # rcell = cell rni = ni if cell >= 0 : rcell = 0 # when we recurse, we'll start from the upper left rni = 1 # and just do the first value in the possible values ti = 0 while True : if rbrd and rbrd.give_up : return(None) ti += 1 sc = simple_pass(brd) if sc == None : return(None) # dead end (impossible board) if not len(sc) : # print "lensc==0" break # solution found if not (ti % 10) : # print len(sc), depth pass sb = copy.deepcopy(brd) if cell >= 0 : i = sc[min(cell, len(sc) - 1)][1] kys = brd[i].keys() if ni == 1 : v = kys[0] else : kys.sort() v = kys[ni] pass else : i = random.choice(sc)[1] v = random.choice(brd[i].keys()) brd[i] = { v : True } # print "reducing", i / 9, i % 9, v, len(sb[i]) brd = solve_board(brd, rcell, rni, rbrd, depth + 1) if brd : # print "reduce==0" break # solution found brd = sb # print "deleting", i / 9, i % 9, v, len(sb[i]) del(brd[i][v]) # no solution was found, so this possibility is ruled out if not len(brd[i]) : raise "Over-reduced %u %u %u" % ( i / 9, i % 9, v ) # bug - impossible board pass return(brd) def one_solution(brd, retval = None) : """ Return whether the given board has one and only one solution. Stash the first solution found in retval.brd if more than one solution is found. We try to solve the board by tree-searching the possible solutions. The problem is that the tree is too big to solve in a reasonable time. So, either the logic needs to use smart logic, or it needs a trick. The trick is that for each ambiguous cell, if we search the tree starting with the first and with the last possible value, and if in all of these sub-trees we find no other solution than the one we found in the first try, then we figure we won't find a differnent solution starting with all of the other possibilities of those ambiguous cells. """ fbrd = solve_board(copy.deepcopy(brd)) if fbrd == None : return(False) # an impossible board does not have only one solution. fspec = board_spec_str(fbrd) # remember the string representation of the solved board (for board-comparison purposes) tbrd = copy.deepcopy(brd) sc = simple_pass(tbrd) random.shuffle(sc) # note: I think this is done to try to ferret out bugs in the algorithm. for i in xrange(1, len(sc)) : # for all ambiguous cells except the first one (randomly chosen) fbrd = solve_board(copy.deepcopy(tbrd), i, 0) # try solving starting with the first possible value for the given ambiguous cell (note: solve_board() will call simple_pass(tbrd) and get the same ambiguous cell list we got) if board_spec_str(fbrd) != fspec : if retval : retval.brd = fbrd return(False) fbrd = solve_board(copy.deepcopy(tbrd), i, -1) # and try solving starting with the last possible value for the given ambiguous cell if board_spec_str(fbrd) != fspec : if retval : retval.brd = fbrd return(False) if i > 2 : # print "one_solutioning", i, "of", len(sc) pass pass return(True) def find_redundant_cells(brd) : """ Return an array of [ cell, value ] that are redundant on the given board. """ brd = copy.deepcopy(brd) ka = [ i for i in xrange(len(brd)) if len(brd[i]) == 1 ] random.shuffle(ka) # we'll do them randomly, because if we find a redundant cell, we permanently make it ambiguous and then try to find more redundant cells, given that ambiguity fnd = [] while ka : i = ka.pop() ov = brd[i] brd[i] = all_numbers_dict() # make fully ambiguous one of the solution's known cells if not one_solution(brd) : brd[i] = ov # undo our change else : fnd.append( [ i, ov ] ) # leaving the change, remember the cell that could be ambiguous pass return(fnd) def show_better_board(brd) : """ If the board has cells with known values that don't need to be known, print cells that could be unknown (there may be more than the given one(s)). """ fnd = find_redundant_cells(brd) if fnd : brd = new_board() for iov in fnd : brd[iov[0]] = iov[1] # create a board with only the can-be-ambiguous cells known print "Not needed:" show_board(brd) return(brd) return(None) class a_random_boarder(Thread) : """ Create a random board, doing so in a thread. Set me.brd when the board is created. """ def __init__(me) : Thread.__init__(me) me.give_up = False me.brd = None def run(me) : brd = new_board() i = random.randint(0, len(brd) - 1) brd[i] = { random.randint(1, 9) : True } # seed the board with one known cell, picked randomly me.brd = solve_board(copy.deepcopy(brd), -1, rbrd = me) # construct random solution pass # a_random_boarder def create_puzzle(brd, x_shape = False) : """ Eliminate random items on the board until no more can be eliminated without the board going ambiguous. """ brd = solve_board(copy.deepcopy(brd)) ka = [ i for i in xrange(len(brd)) ] if x_shape : ka = tzlib.make_dictionary(ka) for i in xrange(9) : del(ka[i * 9 + i]) r = 9 - 1 - i if r != i : del(ka[i * 9 + r]) pass ka = ka.keys() random.shuffle(ka) while ka : i = ka.pop() ov = brd[i] brd[i] = all_numbers_dict() # undo one of the solution's cells if not one_solution(brd) : brd[i] = ov # print "%u %u %u required" % ( i / 9, i % 9, ov.keys()[0] ) else : # print "%u %u %u not required" % ( 1 / 9, i % 9, ov.keys()[0] ) pass pass # Note: it appears that a board may be created that must always have an extra known cell among the (x_shape) pattern. So, just go with the metrics. return(brd) def create_brd(x_shape = False) : """ Create a random, solvable board. """ while True : t = tzlib.elapsed_time() rbrd = a_random_boarder() rbrd.setDaemon(True) # so that we can kick out of the program while the thread is running rbrd.start() while True : if rbrd.brd : break if tzlib.elapsed_time() - t >= 4.0 : rbrd.give_up = True break time.sleep(0.01) if rbrd.brd and not rbrd.give_up : break pass brd = create_puzzle(rbrd.brd, x_shape) return(brd) def ambig_metric_1(brd) : """ Sum up the cubes of the number of hints in each group. """ tot = 0L for g in groups : gt = 0L for i in g : if len(brd[i]) < 2 : gt += 1 pass tot += gt * gt * gt return(tot) def symetry_tb_lr(brd) : """ Sum up the XOR of the knownness of the board halves top/bottom left/right. """ tot = 0 for r in xrange(9 / 2) : for c in xrange(9) : if (len(brd[(r * 9) + c]) == 1) != (len(brd[((9 - 1 - r) * 9) + c]) == 1) : tot += 1 pass pass for r in xrange(9) : for c in xrange(9 / 2) : if (len(brd[(r * 9) + c]) == 1) != (len(brd[(r * 9) + 9 - 1 - c]) == 1) : tot += 1 pass pass return(tot) if __name__ == '__main__' : import os import TZCommandLineAtFile import TZKeyReady import tz_parse_time import replace_file help_str = """ tz_sudoku.py (options) (puzzle_file_or_puzzle_on_stdin_or_in_parameters) Evaluate, solve or create sudoku puzzles. Options: --timeout h(:m(:s)) Set timeout for stability output of created puzzles or -t h(:m(:s)) implies --create --file_out template_file_name Output created puzzle information to given file. or -f template_file_name implies --create with random naming applied to the output files. --create Create puzzle(s). or -c If timeout is given, create multiple puzzle sets stopping after all puzzle creation methods fail to create a better puzzle with a particular solution. If file_out is given, write each puzzle set to files. --x_shape If creating puzzles, make an X shape of cells all given/known. If no creation option is given, I will evaluate and solve a puzzle given on stdin or from file(s), or with each row given as a command line parameter. I evaluate a given puzzle for ambiguity and for unneeded position information. Puzzle creation is done using several evaluation methods. I continue to find "better" puzzles for each method until stopped or until no better puzzle is found in a given timeout. Boards are 9x9 ASCII text. (9 lines of 9 position characters). Spaces, '-' and '|' characters are ignored. '.' and '0' represent unknown positions. 1..9 represent known positions. Unknown positions at end of line do not need to be filled with '.' or '0'. Blank lines are ignored (put a dot or zero to represent an completely unknown row). Board example: 24.3..... 3......8. 5.......7 ..5.71.6. ...4....5 ......9.. .....63.. .71...... 9....8.42 """ if sys.platform == 'win32' : import win32process phnd = win32process.GetCurrentProcess() win32process.SetPriorityClass(phnd, win32process.IDLE_PRIORITY_CLASS) del(sys.argv[0]) TZCommandLineAtFile.expand_at_sign_command_line_files(sys.argv) timeout = 1000000000000.0 out_fn = None try_random = False x_shape = False while True : oi = tzlib.array_find(sys.argv, [ "--help", "-h", "-?", "/h", "/H" ] ) if oi < 0 : break del sys.argv[oi] print help_str sys.exit(254) while True : oi = tzlib.array_find(sys.argv, [ "--try_random", "-r" ] ) if oi < 0 : break del sys.argv[oi] try_random = True # try random solutions as a debug double-check on the one_solution() logic while True : oi = tzlib.array_find(sys.argv, [ "--x_shape", "-x" ] ) if oi < 0 : break del sys.argv[oi] x_shape = True while True : oi = tzlib.array_find(sys.argv, [ "--timeout", "-t" ] ) if oi < 0 : break del sys.argv[oi] timeout = tz_parse_time.parse_time_zone(sys.argv.pop(oi)) if (not timeout) or (timeout <= 0.0) : print "I do not understand the timeout!" sys.exit(101) sys.argv.append("--create") while True : oi = tzlib.array_find(sys.argv, [ "--file_out", "-f" ] ) if oi < 0 : break del sys.argv[oi] out_fn = sys.argv.pop(oi) sys.argv.append("--create") while True : oi = tzlib.array_find(sys.argv, [ "--create", "-c" ] ) if oi < 0 : break del sys.argv[oi] print "Creating puzzles - any key stops me", if out_fn : print "- writing the best puzzle information to", out_fn print "with file renamed after writing with random characters in the name", print while True : print "Creating puzzle" brd = create_brd(x_shape) solved = solve_board(copy.deepcopy(brd)) show_board(solved) print "Finding puzzles" start_time = tzlib.elapsed_time() no_extras = None puz_cnt = 0 while tzlib.elapsed_time() - start_time < timeout : nx = not find_redundant_cells(brd) if (no_extras == None) or ((not no_extras) and nx) : print "Restarting metrics, no redundants?", nx no_extras = nx puz_cnt = 0 lh_bcnt = -1 lh_bcnt_brd = None m1_lest = 10000000000000000L m1_lest_brd = None m1_most = 0 m1_most_brd = None m1_slst = 10000000000000000L m1_slst_brd = None m1_smst = 0 m1_smst_brd = None stblr_lst = 100000 stblr_l_brd = None stblr_mst = 0 stblr_m_brd = None puz_cnt += 1 m1 = ambig_metric_1(brd) if m1_lest > m1 : m1_lest = m1 print "; Amb1 least puzzle:", m1 show_board(brd) m1_lest_brd = copy.deepcopy(brd) start_time = tzlib.elapsed_time() if m1_most < m1 : m1_most = m1 print "; Amb1 most puzzle:", m1 show_board(brd) m1_most_brd = copy.deepcopy(brd) start_time = tzlib.elapsed_time() stblr = symetry_tb_lr(brd) if stblr_lst > stblr : stblr_lst = stblr print "; Sym tb/lr least puzzle:", stblr show_board(brd) stblr_l_brd = copy.deepcopy(brd) start_time = tzlib.elapsed_time() if stblr_mst < stblr : stblr_mst = stblr print "; Sym tb/lr most puzzle:", stblr show_board(brd) stblr_m_brd = copy.deepcopy(brd) start_time = tzlib.elapsed_time() tbrd = copy.deepcopy(brd) sa = simple_pass(tbrd) m1 = ambig_metric_1(tbrd) if m1_slst > m1 : m1_slst = m1 print "; Amb1 least after simple pass puzzle:", m1 show_board(brd) m1_slst_brd = copy.deepcopy(brd) start_time = tzlib.elapsed_time() if m1_smst < m1 : m1_smst = m1 print "; Amb1 most after simple pass puzzle:", m1 show_board(brd) m1_smst_brd = copy.deepcopy(brd) start_time = tzlib.elapsed_time() if lh_bcnt < len(sa): lh_bcnt = len(sa) print "; blanks", lh_bcnt, "after simple pass", 9 * 9 - len(sa), "puzzle:" show_board(brd) lh_bcnt_brd = copy.deepcopy(brd) start_time = tzlib.elapsed_time() if TZKeyReady.tz_key_ready() : break brd = create_puzzle(brd, x_shape) if puz_cnt and out_fn : def fo_write(fo, name, val, brd) : if brd : s = "" if val > 0 : s = " %u" % ( val ) fo.write(name + s + ":\n") fo.write(board_str(brd)) fo.write("\n") pass fo = open(out_fn, 'w') fo_write(fo, "Solved", -1, solved) fo.write("in %u puzzles tried.\n\n" % puz_cnt) fo_write(fo, "Least amb1", m1_lest, m1_lest_brd) fo_write(fo, "Most amb1", m1_most, m1_most_brd) fo_write(fo, "Least amb1 after simple pass amb1", m1_slst, m1_slst_brd) fo_write(fo, "Most amb1 after simple pass amb1", m1_smst, m1_smst_brd) fo_write(fo, "Sym tb/lr most ", stblr_mst, stblr_m_brd) fo_write(fo, "Sym tb/lr least", stblr_lst, stblr_l_brd) fo_write(fo, "Simple pass count", lh_bcnt, m1_most_brd) fo.close() replace_file.rename_big_file_to_available_N_file_name(out_fn) pass pass fds = [] while True : if not len(sys.argv) : if not fds : print "Reading the puzzle board from console input." print "For help use the command line option, --help" fn = "" fd = "" while True : li = sys.stdin.readline() if not li : break fd += li fds.append(fd) break fn = sys.argv.pop(0) try : fi = open(fn, "r") fd = fi.read() fi.close() fds.append(fd) except IOError : fd = [ fn ] + sys.argv fd = "\n".join(fd) # allows each row to be given as a command line parameter fds.append(fd) break pass errs = False if try_random and (len(fds) > 1) : raise "I can't try_random on more than one board, as I never stop random tries!" for fd in fds : brd = read_board(fd) show_board(brd) fbrd = solve_board(copy.deepcopy(brd)) if fbrd == None : errs = True print "Bad board" continue show_better_board(brd) show_board(fbrd) class a_retval : def __init__(me) : me.brd = None brd2 = a_retval() if not one_solution(brd, brd2) : errs = True show_board(brd2.brd) print "Two boards!" print "For help use the command line option, --help" continue if try_random : print "Running random tries..." while True : rbrd = solve_board(copy.deepcopy(brd), -1) if rbrd == None : errs = True show_board(rbrd) raise "Bad random board!" if board_spec_str(fbrd) != board_spec_str(rbrd) : errs = True show_board(rbrd) raise "Two'r boards!" pass pass pass if errs : sys.exit(101) pass # # # # eof