Instantly share code, notes, and snippets.

# williame/luffarschack.py Created Nov 16, 2012

 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=<"%(p, colours[next[p[0]] if p in ends else "-"])) for y in range(3): print("\t\t
",end="") for x in range(3): print(""%colours[p[y*3+x+1]],end="") print("") print("\t>];") for n in boards[p]: print("\t\"%s\" -> \"%s\";"%(p,n)) print("}")