Skip to content

Instantly share code, notes, and snippets.

@williame

williame/luffarschack.py

Created November 16, 2012 13:45
Download ZIP

Revisions

  1. williame created this gist Nov 16, 2012.
    83 changes: 83 additions & 0 deletions luffarschack.py
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,83 @@
    import sys

    queue = ["a"+"-"*9]
    boards = {queue[0]:set()}
    ends = set()

    next = {"a":"b","b":"a"}

    def won(side,board):
    line = side*3
    if board[:3]==line or board[3:6]==line or board[6:]==line:
    return True
    if board[0]+board[3]+board[6]==line or \
    board[1]+board[4]+board[7]==line or \
    board[2]+board[5]+board[8]==line:
    return True
    if board[4] != side:
    return False
    if board[0]+board[4]+board[8]==line or \
    board[2]+board[4]+board[6]==line:
    return True
    return False

    def symmetries(board):
    yield board
    yield board[::-1]
    board = board[6:]+board[3:6]+board[:3]
    yield board
    yield board[::-1]
    board = board[2]+board[5]+board[8]+board[1]+board[4]+board[7]+board[0]+board[3]+board[6]
    yield board
    yield board[::-1]
    board = board[6:]+board[3:6]+board[:3]
    yield board
    yield board[::-1]

    def walk(parent,side,board):
    n = next[side]
    for b in symmetries(board):
    key = n+b
    if key in boards:
    break
    else:
    boards[key] = set()
    if won(side,board):
    ends.add(key)
    else:
    queue.append(key)
    boards[parent].add(key)

    while queue:
    parent = queue.pop()
    side, board = parent[0], parent[1:]
    count = board.count(side)
    for i in range(9):
    if board[i] == "-":
    if count < 3: # lay a new ball
    walk(parent,side,board[:i]+side+board[i+1:])
    else: # move each previous ball to this spot
    for j in range(9):
    if board[j] == side:
    b = board[:j]+"-"+board[j+1:]
    walk(parent,side,b[:i]+side+b[i+1:])
    colours = {
    "a":"red",
    "b":"blue",
    "-":"white",
    };

    print("digraph luffarschack {")
    print("\tnode [shape=none];")
    for p in boards:
    print("\t\"%s\" [label=<<TABLE BORDER=\"1\" BGCOLOR=\"%s\">"%(p,
    colours[next[p[0]] if p in ends else "-"]))
    for y in range(3):
    print("\t\t<TR>",end="")
    for x in range(3):
    print("<TD BGCOLOR=\"%s\"></TD>"%colours[p[y*3+x+1]],end="")
    print("</TR>")
    print("\t</TABLE>>];")
    for n in boards[p]:
    print("\t\"%s\" -> \"%s\";"%(p,n))
    print("}")