#!/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
