Partial solution to http://www.datagenetics.com/blog/december12014/index.html

functions.py

def tryRemove(_SET, _ELE):
  try:
    _SET.remove(_ELE)
  except:
    pass

def generateHammingTwo(s):
  lookup = {'0':'1','1':'0'}
  for i in range(len(s)):
    for j in range(i+1, len(s)):
      yield s[:i]+lookup[s[i]]+s[i+1:j]+lookup[s[j]]+s[j+1:]

def checkAnyLeft(left, D):
  for x in left:
    if len(D[x]) == 1:return x
  return False

def fitConstraint1(D):
  C = sizeCount(D)
  if 0 in C.keys() and C[0] > 0:
    raise Exception('overconstrained')
  left = set(D.keys())
  changed = False
  while True:
    nextConstrain = checkAnyLeft(left, D)
    if not nextConstrain:break
    remove_this = iter(D[nextConstrain]).next()
    for item in generateHammingTwo(nextConstrain):
      if remove_this in D[item]:
        changed = True
        D[item].remove(remove_this)
    left.remove(nextConstrain)
  return changed

def fitConstraint2(D):
  C = sizeCount(D)
  if 0 in C.keys() and C[0] > 0:
    raise Exception('overconstrained2')
  niceD = sorted(D.items())
  sizeD = len(niceD)
  changed = False
  for i in range(0, sizeD/2):
    first_key = niceD[i][0]
    second_key = niceD[sizeD-i-1][0]
    le_intersection = D[first_key] & D[second_key]
    if len(le_intersection) == len(D[first_key]) == len(D[second_key]):
      pass # nothing to be changed
    else:
      changed = True
      D[first_key] = D[second_key] = le_intersection
  return changed

def initialConstraint(D):
  num_bits = len(list(D.keys())[0])
  constraint_randomness = range(num_bits)
  random.shuffle(constraint_randomness)
  for k in range(num_bits):
    D['0'*k+'1'+'0'*(num_bits-k-1)] = set([constraint_randomness[k]])
  

def attemptSolution(num_bits, debug_this=True):
  tries = 0
  while True:
    tries += 1
    try:
      D = tryWithColor(num_bits, num_bits)
      initialConstraint(D)
      while fitConstraint1(D) or fitConstraint2(D):pass
      while 0 not in sizeCount(D):
        S = sizeCount(D)
        if len(S.keys()) == 1 and 1 in S:
          if debug_this:print 'tries:',tries
          return D
        randomConstrain(D)
        while fitConstraint1(D) or fitConstraint2(D):pass
    except KeyboardInterrupt:
      print 'interrupted, tries:',tries
      return
    except Exception,e:
      if debug_this:print str(e)

def fitConstraint(D):
  C = sizeCount(D)
  if 0 in C.keys() and C[0] > 0:
    raise Exception('overconstrained')
  left = set(D.keys())
  while True:
    nextConstrain = checkAnyLeft(left, D)
    if not nextConstrain:break
    for item in generateHammingTwo(nextConstrain):
      tryRemove(D[item], iter(D[nextConstrain]).next() )
    left.remove(nextConstrain)

def tryWithColor(num_bits, num_colors):
  D = {}
  colors = range(num_colors)
  for i in xrange(0,2**num_bits):
    D[bin(i)[2:].zfill(num_bits)] = set(colors)
  return D

def sizeCount(D):
  COUNT = {}
  for k in D:
    try:
      COUNT[len(D[k])] += 1
    except:
      COUNT[len(D[k])] = 1
  return COUNT

import random

def randomConstrain(D):
  C = sizeCount(D)
  max_C_K = max(C.keys())
  constrain_this = random.choice(filter(lambda x:len(x[1]) == max_C_K, D.items()))
  D[constrain_this[0]] = set([random.choice(tuple(constrain_this[1]))])

def keepTrying(num_bits, num_colors, debug_this=True):
  tries = 0
  while True:
    tries += 1
    try:
      D = tryWithColor(num_bits, num_colors)
      randomConstrain(D)
      fitConstraint(D)
      while 0 not in sizeCount(D):
        S = sizeCount(D)
        if len(S.keys()) == 1 and 1 in S:
          if debug_this:print 'tries:',tries
          return D
        randomConstrain(D)
        fitConstraint(D)
    except KeyboardInterrupt:
      print 'interrupted, tries:',tries
      return
    except:
      pass

def repeatedRuns(num_bits, num_runs):
  runlist = []
  for i in range(num_runs):
    runlist.append(keepTrying(num_bits, num_bits, False))
    print i,
  stat_list = []
  for item in runlist:
    stat_list.append({})
    D = {}
    for K in range(num_bits):
      D[list(item['0'*K+'1'+'0'*(num_bits-K-1)])[0]] = K
    for k,v in item.items():
      stat_list[-1][k] = D[list(v)[0]]
  thingehh = {}
  for i in stat_list:
    try:
      S = ''.join(map(lambda x:str(x[1]), sorted(i.items())))
      thingehh[S] += 1
    except:
      thingehh[S] = 1
  return thingehh

Impossible Escape

I was trying to solve this conundrum:
http://www.datagenetics.com/blog/december12014/index.html

So I tried to solve the problem in the general case with n squares, instead of 64 for a chess board. I show that the problem is equivalent to solving the graph coloring problem with n colors of a graph where vertices represent every bit string of length n and edges connect all vertices which are exactly Hamming distance 2 away from each other. I found a few symmetries but not even close to enough to solve the problem in the general case for 64 squares.

Here's my rough writeup:

===================

attempting solution for http://www.datagenetics.com/blog/december12014/index.html

construct some function F which takes n bit string and returns an integer in {1...n}
for every n bit string S1, {all F(S2) where S2 is every string with Hamming distance one away from S1} is just {1...n}
which is equivalent to
F(S2) is unique for all S2 where S2 is string with Hamming distance one away from S1; for all n bit strings S1

let  S = s1,s2,s3,...,sn
and let S' = s1',s2,s3,...,sn
and let S'' = s1,s2',s3,...,sn
and let S''' = s1',s2',s3,...,sn

(where s is a bit)

F(S'') != F(S')
F(S''')!= F(S')
F(S''')!=F(S'')

also notice that all the numbers X where F(X) = 1 can be switched for all the numbers where F(Y) = 2 in the function so that F(X) = 2 and F(Y) = 1 and that's fine
so we can pick arbitrary values for F(S) and some S, and go from there

let's say S = 0^n

F(0^n) = 1
F(0^(k-1) 1 0^(n-k)) = k
so F(000...) = F(1000...) = 1
and F(0100...) = 2

so now F(1100...) != 2 and F(11

blah blah - 

hamming distance 2 means always different
hamming distance 1 means different usually but same in one case

hamming distance 2 always different seems to be an equivalent problem

and we can use initialization like above
then we can say all those two away are different, and remove the number of this one from them
so try this in python with 16 bits and see if it's underconstrained

yes it is underconstrained, even with deduction it doesn't seem easy to propagate further values from this initialization

wrote a bunch of python code...

and after calling repeatedRuns(4,250) I got this list of possible solutions to the 2x2 problem:
2011203333021102
1012230330322101
0013212332123100
3010212332120103
3011202332021103
0012213333122100
3012210330122103
1013202332023101
0013221331223100
1012203333022101
3012201331022103
0011223333221100
2010213333120102
3011220330221103
0011232332321100
2010231331320102
1010223333220101
2013201331023102
3010221331220103
0012231331322100
1013220330223101
2013210330123102
2011230330321102
1010232332320101

notice anything strange? ALL THE SOLUTIONS ARE PERFECTLY SYMMETRICAL

so I'm not sure if this is the only other necessary constraint but now I will try to run this with a 16 board and see what happens

also funny thing : sketch out the n=3 version of this problem and it's easy to convince yourself it's impossible. by symmetry and the initialization discussed earlier?

why does symmetry make sense? those numbers are the furthest hamming distance apart; so it makes sense that they'd be the same. 



ran the code with the two constraints: symmetry and connected edges cannot be the same. STILL UNDERCONSTRAINED! UGGH :(

but it runs much faster now and worked for 8 squares giving these two outputs:
2760547143530206353560711622174427105433651471264146620200773355164213457071623504072326546157303652006735044127715375142263461001643622415735177214405376002563037516456232704053261707543124615533770020266414621741563345017244712261170653536020353417450672
6423114067533572321102464750057675752360001124643604575746221133502657371104460270756435236423114246031132377655110364225567704004077655224630115567732311306424113246325346570720644011737562053311226475754063464211000632575767500574642011232753357604113246
(second one doesn't have 0-7 in right order)

AGH I GIVE UP!!!!!
:-(

================================
then the strategy is:
take the n bit string representing the board
flip the coin which would generate a new n bit string S where F(S) = index given by jailer