Skip to content

Instantly share code, notes, and snippets.

@williame
Created November 16, 2012 13:45
Show Gist options
  • Save williame/4087469 to your computer and use it in GitHub Desktop.
Save williame/4087469 to your computer and use it in GitHub Desktop.
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("}")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment