public
Created

  • Download Gist
luffarschack.py
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 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("}")

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.