[Yubi]

yubi.py

from itertools import chain

RULES = {
  1: {2: 3, 4: 7, 5: 9},
  2: {5: 8},
  3: {2: 1, 5: 7, 6: 9},
  4: {5: 6},
  5: {},
  6: {5: 4},
  7: {4: 1, 5: 3, 8: 9},
  8: {5: 2},
  9: {5: 1, 6: 3, 8: 7},
}

all_places = [1, 2, 3, 4, 5, 6, 7, 8, 9]

def list_candidates(current, visited):
  return (
    p
    for p in all_places
    if
      p != current
      and p not in visited
      and p not in (
        RULES[current].get(b)
        for b in RULES[current].keys()
        if b not in visited
      )
  )

def list_patterns(current, rest, visited, found, nest):
  # print '  ' * nest, current, rest, visited, found
  if found:
    new_found = list(list(chain(f, (current,))) for f in found)
  else:
    new_found = [[current]]
  new_visited = visited + [current]
  more_founds = (
    list_patterns(
      r0,
      list(r for r in rest if r != r0),
      new_visited,
      new_found,
      nest + 1
    )
    for r0 in list_candidates(current, visited)
  )
  for p in new_found:
    yield p
  for ps in more_founds:
    for p in ps:
      yield p

def list_valid_patterns(current, rest, visited, found):
  for p in list_patterns(current, rest, visited, found, 0):
    if 4 <= len(p):
      yield p

def list_all_valid_patterns():
  for i0 in all_places:
    for p in list_valid_patterns(i0, list(i for i in all_places if i != i0), [], []):
      yield p

def main():
  print len(list(list_all_valid_patterns()))
  if False:
    for i0 in all_places:
      print (
        i0,
        list(i for i in all_places if i != i0),
        len(list(list_valid_patterns(i0, list(i for i in all_places if i != i0), [], [])))
      )
  if False:
    print '----'
    print (list(find_pattern(8, [], [1, 2, 3, 4, 5, 6, 7, 9], [(1, 2)])))
    print '----'
    print (list(find_pattern(8, [7, 9], [1, 2, 3, 4, 5, 6], [])))
    print '----'
    print list(list_candidates(7,  [1, 2, 3, 4, 5, 6]))
    print list(find_pattern(7, [8, 9], [1, 2, 3, 4, 5, 6], []))
  if False:
    print list(list_candidates(1, ()))
    print list(list_candidates(1, (2,)))
    print list(list_candidates(1, (3,)))
    print list(list_candidates(1, (2, 3)))
    print list(list_candidates(2, ()))
    print list(list_candidates(2, (5,)))
    print list(list_candidates(5, ()))

main()