import sys

if (len(sys.argv) < 2):
    print ""
    print "Usage is:"
    print "   python listroads3.py removeAt"
    print ""
    print " lists roads to solutions"
    sys.exit()

done = False
state = 0
solution = []
solutionKey = ""
solutions = {}
bd = {}
rules = []
possibilities = []
possibilitiesIX = 0

def initBoard():
    global bd
    i = 1
    while i <= 15:
        bd[i] = "1"
        i += 1

def removeAt(p):
    global bd
    bd[p] = " "

def listPossibilities():
    global bd, possibilities,possibilitiesIX
    possibilities = []
    possibilitiesIX = 0
    for i in range(len(rules)):
        if bd[rules[i][0]] == "1" and bd[rules[i][1]] == "1" and bd[rules[i][2]] == " ":
            possibilities.append(i)

def getSolutionKey(s):
    sk = ""
    for i in range(len(s)):
        sk += str(s[i]) + ","
    return sk

def jump(i):
    global bd
    bd[rules[i][0]] = " "
    bd[rules[i][1]] = " "
    bd[rules[i][2]] = "1"

def unjump(i):
    global rules, bd
    bd[rules[i][0]] = "1"
    bd[rules[i][1]] = "1"
    bd[rules[i][2]] = " "

def displaySolution():
    global bd,solution,rules
    i = 0
    print "\"solution:",
    while i < len(solution) - 1:
        p = solution[i]
        print str(rules[p][0]) + "-" + str(rules[p][2]) + ",",
        i += 1
    
    p = solution[i]
    print str(rules[p][0]) + "-" + str(rules[p][2]),
    
    print "\",",
    i = 1
    pegsleft = []
    while i <= 15:
        if bd[i] == "1": pegsleft.append(i)
        i += 1
    print "\"pegs left: (",
    i = 0
    while i < len(pegsleft) - 1:
        print str(pegsleft[i]) + ",",
        i += 1
    print str(pegsleft[i]) + ")\"," + str(len(pegsleft))
    
# initialize
def state0():
    global state,rules
    
    rules.append((1,2,4))
    rules.append((1,3,6))
    rules.append((2,4,7))
    rules.append((2,5,9))
    rules.append((3,5,8))
    rules.append((3,6,10))
    rules.append((4,2,1))
    rules.append((4,5,6))
    rules.append((4,7,11))
    rules.append((4,8,13))
    rules.append((5,8,12))
    rules.append((5,9,14))
    rules.append((6,3,1))
    rules.append((6,5,4))
    rules.append((6,9,13))
    rules.append((6,10,15))
    rules.append((7,4,2))
    rules.append((7,8,9))
    rules.append((8,5,3))
    rules.append((8,9,10))
    rules.append((9,5,2))
    rules.append((9,8,7))
    rules.append((10,6,3))
    rules.append((10,9,8))
    rules.append((11,7,4))
    rules.append((11,12,13))
    rules.append((12,8,5))
    rules.append((12,13,14))
    rules.append((13,12,11))
    rules.append((13,8,4))
    rules.append((13,9,6))
    rules.append((13,14,15))
    rules.append((14,13,12))
    rules.append((14,9,5))
    rules.append((15,10,6))
    rules.append((15,14,13))
    
    initBoard()
    # print "removeAt(" + sys.argv[1] + ")"
    print "SOLUTION,PEGS_LEFT,NUM_PEGS_LEFT"
    removeAt(int(sys.argv[1]))
    listPossibilities()
    state = 1

# search all the current possibilities
def state1():
    global state,possibilities,possibilitiesIX,solution,solutions
    
    if possibilitiesIX == len(possibilities):
        state = 2
    else:
        p = possibilities[possibilitiesIX]
        possibilitiesIX += 1
        solution.append(p)
        key = getSolutionKey(solution)
        if key in solutions:
            del solution[len(solution)-1]
            # in this state, try the next possibility
        else:
            solutions[key] = True
            # print "jump: " + str(rules[p][0]) + "-" + str(rules[p][2])
            jump(p)
            listPossibilities()
            if len(possibilities) == 0: 
                displaySolution()
                state = 2

# if we're not finished, unjump the last move, and make sure all possibilities have been searched at that point.
def state2():
    global state,solution,done
    
    if len(solution) == 0:
        done = True
    else:
        p = solution.pop()
        # print "p: " + str(p)
        # print "unjump: " + str(rules[p][0]) + "-" + str(rules[p][2])
        unjump(p)
        listPossibilities()
        state = 1

states = {
    0:state0,
    1:state1,
    2:state2
}

while not done:
    states[state]()

# print "Finished OK."