luffarschack.py

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("}")