Граф содержит не более 1024 вершин. Поиск в ширину без всяких оптимизаций.
import collections
R0, R1, R2, R3, R4, R5 = 0, 1, 2, 3, 4, 5
G0, G1, G2, G3, G4, G5 = 0, 6, 2, 7, 8, 9
SIZE = 10
def r_m(p):
p[R0], p[R1], p[R2], p[R3], p[R4], p[R5] = \
p[R1], p[R2], p[R3], p[R4], p[R5], p[R0]
def r_p(p):
p[R1], p[R2], p[R3], p[R4], p[R5], p[R0] = \
p[R0], p[R1], p[R2], p[R3], p[R4], p[R5]
def g_m(p):
p[G0], p[G1], p[G2], p[G3], p[G4], p[G5] = \
p[G1], p[G2], p[G3], p[G4], p[G5], p[G0]
def g_p(p):
p[G1], p[G2], p[G3], p[G4], p[G5], p[G0] = \
p[G0], p[G1], p[G2], p[G3], p[G4], p[G5]
def done(p):
return \
all(p[r] == 'r' for r in (R1, R3, R4, R5)) and \
all(p[g] == 'g' for g in (G1, G3, G4, G5))
def solve(start):
def bfs(start):
visited = set()
queue = collections.deque()
queue.append((start, None, None))
visited.add(start)
while queue:
item = queue.popleft()
p, _, _ = item
yield item
for op in r_m, r_p, g_m, g_p:
q = list(p)
op(q)
q = tuple(q)
if q not in visited:
queue.append((q, op, item))
visited.add(q)
def moves(path):
names = {
r_m: ('red', 'm'),
r_p: ('red', 'p'),
g_m: ('green', 'm'),
g_p: ('green', 'p')
}
def moves(path):
while path is not None:
_, op, path = path
if op is None:
break
yield names[op]
return tuple(moves(path))[::-1]
for p in bfs(start):
if done(p[0]):
return moves(p)
return None
def main():
start = [None] * SIZE
start[R0] = 'r'
start[R1] = 'g'
start[R2] = 'r'
start[R3] = 'g'
start[R4] = 'r'
start[R5] = 'r'
start[G1] = 'g'
start[G3] = 'r'
start[G4] = 'g'
start[G5] = 'g'
print(solve(tuple(start)))
main()
Анализ всех 1024 стартовых позиций показывает что самая длинная последовательность ходов до выигрыша - 8 ходов. Например для
start[R0] = 'r'
start[R1] = 'g'
start[R2] = 'r'
start[R3] = 'g'
start[R4] = 'g'
start[R5] = 'g'
start[G1] = 'r'
start[G3] = 'g'
start[G4] = 'r'
start[G5] = 'g'
(('red', 'm'), ('red', 'm'), ('green', 'p'), ('green', 'p'), ('red', 'm'), ('green', 'm'), ('red', 'p'), ('red', 'p'))