#!/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 # May 25, 2010 bar tz_os_priority # June 8, 2011 bar allow one long ... string for input # update the exception raises # May 27, 2012 bar doxygen namespace # August 12, 2012 bar put name in thread # May 28, 2014 bar put thread id in threads # October 16, 2014 bar strip -+ lines in input # August 19, 2015 bar pyflakes # January 21, 2017 bar conversion to string rtns handle boards that have numbers rather than dicts in each cell -1==ouch 0==space 1...==cell_value # July 7, 2018 bar pyflakes # September 16, 2018 bar simple_pass_all() - remove redundancies generally (but make the rest of the program much slower, so we use the old simple_pass() for most things) # April 29, 2019 bar make simple_pass_all() able to just tell us what's the first known-able cell # and print it in any case # May 8, 2019 bar beef up the simply-solve logic to find other situations # May 11, 2019 bar show how far simple_pass_all gets if the board is not simply and newly solvable # add some more to the "new" simply-solvable logic # December 13, 2019 bar is_solved() really makes sure now # --eodstamps-- ## \file # \namespace tzpython.tz_sudoku # # # # 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 itertools import re import random import string import sys import threading import time 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(range(1, 10))) def new_board() : """ A board is an 81 (9x9) element array of dictionaries keyed by numbers from 1 through 9, those numbers being the possible values for the 81 "cells". One key:value? The key is the cell's value. """ 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 - 9 rows, 9 columns, and 9 squares # 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 columns groups += [ [ (r * 9) + c for c in xrange(9) ] for r in xrange(9) ] # add all the rows group_sets = [ frozenset(gg) for gg in groups ] group_names = [ "S%u" % c for c in xrange(1, 10) ] + [ "C%u" % c for c in xrange(1, 10) ] + [ "R%u" % c for c in xrange(1, 10) ] combos = [] for i in xrange(1, 5) : combos += [ frozenset(c) for c in itertools.combinations(range(1, 10), i) ] # create all combinations of up-to-4-length groups of possible values. [1], [2], ... [ 5,6,8,9], 5,7,8,9], [6,7,8,9] def rotate_board(brd, way = 1) : """ Rotate the board 1==clockwise 2=counter-clockwise 3==half-around. """ nb = copy.deepcopy(brd) i = 0 for r in xrange(9) : for c in xrange(9) : if way == 3 : nb[(9 * (9 - 1 - r)) + (9 - 1 - c)] = copy.deepcopy(brd[(r * 9) + c]) elif way == 2 : nb[(9 * (9 - 1 - c)) + r] = copy.deepcopy(brd[(r * 9) + c]) elif way == 1 : nb[(9 * c) + (9 - 1 - r)] = copy.deepcopy(brd[(r * 9) + c]) i += 1 pass return(nb) def board_str(brd, hilite = None) : """ Return a string that is a pretty-print of the given board. """ cs = max([ (hasattr(bv, '__len__') and hasattr(bv, 'keys') and (((len(bv) == 1) and len(str(bv.keys()[0]))) or 1)) or (((bv > 0) and len(str(bv))) or 1) for bv in brd ]) cs += 1 spc = " " * (cs - 1) dsh = " " + ("-" * ((cs * 9) + 7)) + "\n" ps = "\n" ps += dsh 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 i is hilite : hii = len(ps) v = brd[i] if hasattr(v, '__len__') and hasattr(v, 'keys') : if len(v) > 1 : ps += spc + "." elif not len(v) : ps += spc + "*" else : ps += "%*u" % ( cs, v.keys()[0], ) pass elif not v : ps += spc + "." elif v < 0 : ps += spc + "*" else : ps += "%*u" % ( cs, v, ) pass pass ps += " |" + "\n" ps += dsh if hilite != None : ps = list(ps) ps[hii] = "[" ps[hii + cs] = "]" ps = string.join(ps, "") return(ps) def show_board(brd, hilite = None) : """ Print the board. """ print board_str(brd, hilite = hilite) def show_full_board(brd) : db = [] for c in brd : na = c.keys() na.sort() n = 0 while len(na) : n *= 10 n += na.pop(0) db.append(n) show_board(db) 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 hasattr(bc, '__len__') and hasattr(bc, 'keys') : if len(bc) == 1 : ps += str(bc.keys()[0]) else : ps += "." pass elif bc <= 0 : ps += "." else : ps += "%u" % bc pass i += 1 ps += "\n" return(ps) def xy_array(a) : return([ [ (ci / 9) + 1, (ci % 9) + 1 ] for ci in a ]) 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") sa = [ ss for ss in sa if not re.search(r'^\s*\+*\s*$', ss) ] if len(sa) == 1 : sa = sa[0] sa = [ "".join([ sa[i + j] for j in xrange(9) ]) for i in xrange(0, 9 * 9, 9) ] if len(sa) > 9 : print sa raise ValueError("Too many rows %u" % ( len(sa) ) + str(sa)) for si in xrange(len(sa)) : s = sa[si] if len(s) > 9 : raise ValueError("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. Returns None if the board is impossible to solve - a bad board. Otherwise returns an array of [ number of possible values, cell number ], for each unknown-value cell. That is, if the array is empty, the board is solved. """ 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) # print "@@@@" # show_board(brd) done_one = True pass pass else : if len(bc) == 0 : raise AssertionError("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) def simple_pass_all(brd, find_only_one = False, do_new = False) : """ Try hard to get rid of logically deducted non-possibilities. This code currently eliminates possibilities that can't be true because they are all taken by cells that only have those values. Or possible values that are redundant because the other values for cells having them are needed. Also, the "new" logic handles situations where all particular values of a combination of values are in single (or double) other group, so the values can be eliminated from other cells in the other group. This logic does not handle the X-wing/swordfish/jellyfish/N-fish situations: ..5....5. With, say, no other possible 5's on the row ......... ......... ......... ......... ..5....5. With, say, no other possible 5's on the row ......... ......... ......... Implies than columns 3 and 8 can't have any other 5's either. Same thing if: ..5..5.5. With no other possible 5's on the row ......... ..5..5.5. With no other possible 5's on the row ......... ......... ..5..5.5. With no other possible 5's on the row ......... ......... ......... Etc. This one is caught by the old logic: 5...7.492 ..42..... .2..947.. 2.6...... 1..823..9 ......2.5 ..314?.7. ..*..93*. .8*.3..*4 Notice that the star-pairs must have 2's and so the ? must be a 2. This one is caught by the old logic: 5..@7.492 &&42...** .2.@947.. 2.6...... 1..823..9 ......2.5 ..314..7. .....93.. .8..3...4 Notice the & cells must be 7 and 9. So 3's must be in the top and bottom rows of the top left square. And, they can only be in the @ cells of the top middle square. So the two * cells must have a 3 in them. And the cells below the stars cannot have a 3. """ def _remake_board(db) : """ Make a board from the working set. """ brd = [] for c in db : brd.append(tzlib.make_dictionary(list(c))) return(brd) db = [ set(c.keys()) for c in brd ] fnd = True while fnd : fnd = False for combo in combos : for gi, group in enumerate(groups) : fa = [] na = [] for ci in group : if not len(db[ci] - combo) : # does this cell only have values in the combo? fa.append(ci) else : na.append(ci) pass if len(fa) > len(combo) : return(None) # too many cells only have the values in the combo - bad board if len(fa) == len(combo) : for ci in na : if len(db[ci] & combo) : fnd = True db[ci] -= combo # remove the combo's values from the other cells in this group because there are N possible cells in the group with only the N values in the combo if find_only_one and (len(db[ci]) == 1) : return(_remake_board(db)) # the caller doesn't want us to solve the puzzle, only to know what cell has a known value, given the input pass pass pass fa = [] for ci in group : if len(db[ci] & combo) : # does this cell have any values in the combo? fa.append(ci) pass if len(fa) < len(combo) : return(None) # not enough cells have the values in the combo - bad board if len(fa) == len(combo) : for ci in fa : if len(db[ci] - combo) : fnd = True db[ci] &= combo # remove the non-combo values from the cells with combo values because these cells in fa (with the combo values) use all the combo's values if find_only_one and (len(db[ci]) == 1) : return(_remake_board(db)) # the caller doesn't want us to solve the puzzle, only to know what cell has a known value, given the input pass pass pass if do_new : # do outside fa's cells being the only cells with combo values because, say, a single digit can be in two cells that are in another group, which we'll want to strip the single digit from for v in combo : cs = set([ ci for ci in fa if v in db[ci] ]) for g2i, g2 in enumerate(group_sets) : if (g2 != group) and cs.issubset(g2) : # for debugging reasons, let the group we are doing sort itself out in the older logic above for ci in g2 : if (ci not in cs) and (v in db[ci]) : fnd = True db[ci].discard(v) # remove the combo value from the other cells in g2 because v is only in g2 cells. # print "@@@@", "from", (ci / 9) + 1, (ci % 9) + 1, "removing", v, "in combo", combo, "now only possible", db[ci], "where", v, "is only in", xy_array(cs), "doing group:", group_names[gi], "g2:", group_names[g2i] if find_only_one and (len(db[ci]) == 1) : return(_remake_board(db)) # the caller doesn't want us to solve the puzzle, only to know what cell has a known value, given the input pass pass pass pass pass pass pass pass pass return(_remake_board(db)) def is_solved(brd) : if brd is None : return(False) for c in brd : if len(c) != 1 : return(False) pass for g in group_sets : gd = dict([ [ brd[gi].keys()[0], True ] for gi in g ]) if len(gd) != 9 : return(False) pass return(True) 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", i / 9 + 1, i % 9 + 1, v 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 AssertionError("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 different 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) fbrd = None sc = simple_pass(tbrd) random.shuffle(sc) # note: I think this is done to try to ferret out bugs in the algorithm. t = tzlib.elapsed_time() 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) tt = tzlib.elapsed_time() if (i > 2) and (tt - t >= 5.0) : t = tt print "one_solutioning", i, "of", len(sc) pass if retval : retval.brd = fbrd or tbrd # try to give him back a solved board 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(threading.Thread) : """ Create a random board, doing so in a thread. Set me.brd when the board is created. """ def __init__(me) : threading.Thread.__init__(me, name = __file__) me.tid = None me.give_up = False me.brd = None def run(me) : me.tid = tzlib.get_tid() 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_os_priority import tz_parse_time import replace_file help_str = """ python %s (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 """ tz_os_priority.set_proc_to_idle_priority() program_name = sys.argv.pop(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 % os.path.basename(program_name) 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_solvable(fo, brd) : fbrd = simple_pass_all(brd) if fbrd != None : if not is_solved(fbrd) : fo.write(" ... is not simply solvable") if is_solved(simple_pass_all(brd, do_new = True)) : fo.write(" but is newly solvable") fo.write('.\n\n') pass pass 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") fo_solvable(fo, brd) 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 ValueError("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) sbrd = simple_pass_all(brd) if sbrd is None : errs = True print "Bad board" continue do_one_new = False obrd = brd if is_solved(sbrd) : print "Simply solvable." else : do_one_new = True obrd = sbrd fbrd = simple_pass_all(brd, do_new = True) if fbrd is None : errs = True print "Bad board" continue if is_solved(fbrd) : print "Not simply solvable but newly solvable." else : print "This board is not newly solvable:" show_board(fbrd) show_full_board(fbrd) pass fbrd = simple_pass_all(obrd, find_only_one = True, do_new = do_one_new) oi = -1 for ci, c in enumerate(obrd) : if (len(c) > 1) and (len(fbrd[ci]) == 1) : if oi >= 0 : oi = -1 break oi = ci pass if oi >= 0 : print "The first cell known:", (oi / 9) + 1, (oi % 9) + 1 show_board(fbrd, hilite = oi) show_full_board(fbrd) fbrd = simple_pass_all(brd, do_new = True) if fbrd is None : errs = True print "Bad board" continue if not is_solved(fbrd) : fbrd = solve_board(copy.deepcopy(brd)) if fbrd is None : errs = True print "Bad board" continue pass 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 AssertionError("Bad random board!") if board_spec_str(fbrd) != board_spec_str(rbrd) : errs = True show_board(rbrd) raise AssertionError("Two'r boards!") pass pass pass if errs : sys.exit(101) pass # # # # eof