import itertools

def encode(state):
  s = ''
  for l in state:
    if l:
      s = s + l[0]
    else:
      s = s + '_'
  return s

def pretty(state):
  return '|'.join([''.join(slot) or '_' for slot in state])

def mutate(state, dirs):
  fr, to = int(dirs[0])-1, int(dirs[1])-1
  l = state[fr].pop(0)
  state[to].insert(0,l)
  return

def iteration(state, decider):
  dirs = decider[encode(state)]
  mutate(state, decider[encode(state)])
  return

slots = ["","Q","A","K","QA","QK","KA","KQ","AQ","AK","QAK","QKA","KQA","KAQ","AQK","AKQ"]

def final(state):
  if ''.join(state[0]) == "AKQ" and len(state[1])==0 and len(state[2])==0:
    return True
  else:
    return False

def gen_states():
  list_slots = [list(x) for x in slots]
  for L in list_slots:
    ls = set(itertools.chain(*L))
    for M in list_slots:
      ms = set(itertools.chain(*M))
      if ls.intersection(ms):
        continue
      for R in list_slots:
        rs = set(itertools.chain(*R))
        if ls.intersection(rs) or ms.intersection(rs):
          continue
        if len(ls | ms | rs) != 3:
          continue
        yield([list(L),list(M),list(R)])


def loop(state, decider):
  known = set()
  chain = ''
  while True:
    chain += pretty(state)
    if final(state):
      return True, chain
    if pretty(state) in known:
      return False, chain  # loop
    known.add(pretty(state))
    iteration(state, decider)
    chain += '  -->  '
  return  # shouldn't reach

def test_decider(decider):
  states = list(gen_states())
  for s in states:
    res, chain = loop(s, decider)
    if not res:
      print "FAILED:"
    print chain
    if not res:
      return

decider = {
  "Q__": "12",
  "K__": "12",
  "A__": "12",
  "_Q_": "12",
  "_K_": "12",
  "_A_": "12",
  "__Q": "12",
  "__K": "12",
  "__A": "12",

  "KA_": "12",
  "K_A": "12",
  "_KA": "12",
  "AK_": "12",
  "A_K": "12",
  "_AK": "12",

  "AQ_": "12",
  "_QA": "12",
  "Q_A": "12",
  "QA_": "12",
  "_AQ": "12",
  "A_Q": "12",

  "KQ_": "12",
  "_QK": "12",
  "Q_K": "12",
  "QK_": "12",
  "_KQ": "12",
  "K_Q": "12",

  "QKA": "12",
  "QAK": "12",

  "KQA": "12",
  "KAQ": "12",
  "AQK": "12",
  "AKQ": "12",
}

test_decider(decider)