Solving the Octopuszle

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

Aldarion
Posts: 133
Joined: Thu Jul 19, 2007 7:00 pm UTC

Solving the Octopuszle

Postby Aldarion » Sat Jan 19, 2013 4:56 pm UTC

A couple of days ago I discovered a site called Mindsports, where I saw two interesting puzzles.

The first one is called BackSlide, and it's fairly simple.
Take the 16 possible squares with all the combinations of North-East-South-West lines coming from the center:

Image

Now arrange those (without rotating them) in a 4x4 square with all the lines joined up.
There are 652 solutions, here's one for example:

Image

To get the solutions I wrote a fairly simple recursive backtracker in Python:

Code: Select all

import Image, ImageDraw
import psyco

psyco.full()

###### CLASS DEFS ######

class Board:
   def __init__(self):
      # X = Down, Y = Right.
      self.arr = [None]*4
      for i in range(4):
         self.arr[i] = [None] * 4
      self.count = 0
   
   def check(self):
      # Go over the array.
      # If the current cell holds a Tile,
      # Check all the Tile's edge connections.
      # If the adjacent cell is None - it's OK.
      for n in range(16):
         x = n/4
         y = n%4
         
         tilCurr = self.arr[x][y]
         if (None != tilCurr):
            
            if (tilCurr.U):
               if (0 == x):
                  return (False)
               
               tilU = self.arr[x-1][y]
               if (None != tilU):
                  if (not tilU.D):
                     return (False)
            
            if (tilCurr.D):
               if (3 == x):
                  return (False)
               
               tilD = self.arr[x+1][y]
               if (None != tilD):
                  if (not tilD.U):
                     return (False)
                     
            if (tilCurr.L):
               if (0 == y):
                  return (False)
               
               tilL = self.arr[x][y-1]
               if (None != tilL):
                  if (not tilL.R):
                     return (False)
            
            if (tilCurr.R):
               if (3 == y):
                  return (False)
               
               tilR = self.arr[x][y+1]
               if (None != tilR):
                  if (not tilR.L):
                     return (False)
      
      return (True)
   
   def show(self):
      for row in self.arr:
         res = ""
         for tile in row:
            res += tile.Name + " "
         print res
      print "Count:",self.count
   
   def draw(self):
      map = Image.new("RGB", (81, 81), (255, 255, 255))
      
      for x in range(4):
         for y in range(4):
            im = self.arr[x][y].draw()
            
            map.paste(im, (20 * y, 20 * x))
      
      return (map)

class Tile:
   def __init__(self, Name, U, R, D, L):
      self.Name = Name
      self.U = U
      self.R = R
      self.D = D
      self.L = L
   
   def draw(self):
      im = Image.new("RGB", (21, 21), (255, 255, 255))
      draw = ImageDraw.Draw(im)
      # Draw border
      draw.rectangle((0, 0, 20, 20), fill=None, outline="black")
      
      # Draw the lines
      if (self.U):
         draw.line((10, 10, 10, 0), fill="black")
      
      if (self.R):
         draw.line((10, 10, 20, 10), fill="black")
      
      if (self.D):
         draw.line((10, 10, 10, 20), fill="black")
      
      if (self.L):
         draw.line((10, 10, 0, 10), fill="black")
      
      return (im)

###### FUNC DEFS ######

def backtrack(arrTiles):
   global brd
   
   # If arrTiles is empty, we found a winner!
   if (0 == len(arrTiles)):
      print "YESS!"
      brd.count += 1
      brd.show()
      i = brd.draw()
      i.save("EasySols/"+str(brd.count)+".png", "PNG")
      print
      return
   
   # Find the next vacant spot in the board
   v = 16 - len(arrTiles)
   x = v/4
   y = v%4
   
   # Try all tiles in arrTiles
   for tilCurr in arrTiles:
   
      # Place the tile
      brd.arr[x][y] = tilCurr
      
      if (brd.check()):
         
         # The tile matches.
         # Recurse with the rest.
         i = arrTiles.index(tilCurr)
         backtrack(arrTiles[:i]+arrTiles[i+1:])
   
   # Clean up after backtracking
   brd.arr[x][y] = None
   
   return
   
###### MAIN PART ######

# Creating the objects: board and tiles

brd = Board()

tiles = []

tiles.append(Tile("0A", False, False, False, False))

tiles.append(Tile("0B", True, False, False, False))
tiles.append(Tile("0C", False, True, False, False))
tiles.append(Tile("0D", False, False, True, False))
tiles.append(Tile("1A", False, False, False, True))

tiles.append(Tile("1B", True, True, False, False))
tiles.append(Tile("1C", True, False, True, False))
tiles.append(Tile("1D", True, False, False, True))
tiles.append(Tile("2A", False, True, True, False))
tiles.append(Tile("2B", False, True, False, True))
tiles.append(Tile("2C", False, False, True, True))

tiles.append(Tile("2D", False, True, True, True))
tiles.append(Tile("3A", True, False, True, True))
tiles.append(Tile("3B", True, True, False, True))
tiles.append(Tile("3C", True, True, True, False))

tiles.append(Tile("3D", True, True, True, True))

# Backtracking

backtrack(tiles)


The code was fast, the solutions were all quickly rounded up, and so I went merrily on to adapt my code for the harder version: the Octopuszle.

It's basically the same, but now we have diagonals, too:

Image

The board to tile up is 16x16, obviously.

Here's the code, adapted for tiles with diagonals:

Code: Select all

from random import shuffle
import Image, ImageDraw
import psyco

psyco.full()

###### CLASS DEFS ######

class Board:
   def __init__(self):
      # X = Down, Y = Right.
      self.arr = [None]*16
      for i in range(16):
         self.arr[i] = [None] * 16
      self.count = 0
   
   def check(self):
      # Go over the array.
      # If the current cell holds a Tile,
      # Check all the Tile's edge connections.
      # If the adjacent cell is None - it's OK.
      for n in range(256):
         x = n/16
         y = n%16
         
         tilCurr = self.arr[x][y]
         if (None != tilCurr):
            
            if (tilCurr.L):
               if (0 == y):
                  return (False)
               
               tilL = self.arr[x][y-1]
               if (None != tilL):
                  if (not tilL.R):
                     return (False)
            
            if (tilCurr.D):
               if (15 == x):
                  return (False)
               
               tilD = self.arr[x+1][y]
               if (None != tilD):
                  if (not tilD.U):
                     return (False)
            
            if (tilCurr.R):
               if (15 == y):
                  return (False)
               
               tilR = self.arr[x][y+1]
               if (None != tilR):
                  if (not tilR.L):
                     return (False)
            
            if (tilCurr.U):
               if (0 == x):
                  return (False)
               
               tilU = self.arr[x-1][y]
               if (None != tilU):
                  if (not tilU.D):
                     return (False)
            
            if (tilCurr.LU):
               if ((0 == x) | (0 == y)):
                  return (False)
               
               tilLU = self.arr[x-1][y-1]
               if (None != tilLU):
                  if (not tilLU.RD):
                     return (False)
            
            if (tilCurr.DL):
               if ((15 == x) | (0 == y)):
                  return (False)
               
               tilDL = self.arr[x+1][y-1]
               if (None != tilDL):
                  if (not tilDL.UR):
                     return (False)
            
            if (tilCurr.RD):
               if ((15 == x) | (15 == y)):
                  return (False)
               
               tilRD = self.arr[x+1][y+1]
               if (None != tilRD):
                  if (not tilRD.LU):
                     return (False)
            
            if (tilCurr.UR):
               if ((15 == x) | (0 == y)):
                  return (False)
               
               tilUR = self.arr[x+1][y-1]
               if (None != tilUR):
                  if (not tilUR.DL):
                     return (False)
            
      return (True)
   
   def show(self):
      for row in self.arr:
         res = ""
         for tile in row:
            res += tile.Name + " "
         print res
      print "Count:",self.count
   
   def draw(self):
      map = Image.new("RGB", (321, 321), (255, 255, 255))
      
      for x in range(16):
         for y in range(16):
            im = self.arr[x][y].draw()
            
            map.paste(im, (20 * y, 20 * x))
      
      return (map)

class Tile:
   def __init__(self, Name, L, D, R, U, LU, DL, RD, UR):
      self.Name = Name
      self.L = L
      self.D = D
      self.R = R
      self.U = U
      self.LU = LU
      self.DL = DL
      self.RD = RD
      self.UR = UR
   
   def draw(self):
      im = Image.new("RGB", (21, 21), (255, 255, 255))
      draw = ImageDraw.Draw(im)
      # Draw border
      draw.rectangle((0, 0, 20, 20), fill=None, outline="black")
      
      # Draw the lines
      if (self.L):
         draw.line((10, 10, 1, 10), fill="blue")
      
      if (self.D):
         draw.line((10, 10, 10, 19), fill="blue")
      
      if (self.R):
         draw.line((10, 10, 19, 10), fill="blue")
      
      if (self.U):
         draw.line((10, 10, 10, 1), fill="blue")
      
      if (self.LU):
         draw.line((10, 10, 1, 1), fill="red")
      
      if (self.DL):
         draw.line((10, 10, 1, 19), fill="red")
      
      if (self.RD):
         draw.line((10, 10, 19, 19), fill="red")
      
      if (self.UR):
         draw.line((10, 10, 19, 1), fill="red")      
      
      return (im)
   
   def __str__(self):
      return self.Name
      
   def __repr__(self):
      return self.Name

###### FUNC DEFS ######

def backtrack(arrTiles):
   global brd
   
   # If arrTiles is empty, we found a winner!
   if (0 == len(arrTiles)):
      print "YESS!"
      brd.count += 1
      brd.show()
      i = brd.draw()
      i.save("HardSols/"+str(brd.count)+".png", "PNG")
      print
      return
   
   # Find the next vacant spot in the board
   v = 256 - len(arrTiles)
   x = v/16
   y = v%16
   
   # Try all tiles in arrTiles
   for tilCurr in arrTiles:
      
      # Place the tile
      brd.arr[x][y] = tilCurr
      
      if (brd.check()):

         # The tile matches.
         # Recurse with the rest.
         i = arrTiles.index(tilCurr)
         backtrack(arrTiles[:i]+arrTiles[i+1:])

   # Clean up after backtracking
   brd.arr[x][y] = None
   return

def genTile(Ort, Diag):
   # Making a tile based on the binary representation of its coordinates.
   
   strOrt = bin(Ort)[2:].zfill(4)
   strDiag = bin(Diag)[2:].zfill(4)
   
   lstOrt = map(int, list(strOrt))
   lstDiag = map(int, list(strDiag))
   
   lstAll = lstOrt + lstDiag
   
   strName = hex(Ort)[2:] + hex(Diag)[2:]
   strName = strName.upper()
   
   tilRes = Tile(strName, *lstAll)
   
   return (Tile(strName, *lstAll))
   
###### MAIN PART ######

# Creating the objects: board and tiles

brd = Board()

tiles = []

for Ort in range(16):
   for Diag in range(16):
      tiles.append(genTile(Ort, Diag))

# Backtracking

tiles = tiles[::-1]
print tiles

backtrack(tiles)


Well, it seems I've been a bit too optimistic about backtracking; it's better than nothing (i.e. brute-force), of course, but it's still way too slow.
It ran for a couple of hours, and the recursion depth hadn't reached as much as 20...

So - could you recommend a different algorithm for solving this thing?
I'm not good, I'm not nice, I'm just right.

User avatar
Lopsidation
Posts: 183
Joined: Tue Oct 27, 2009 11:29 pm UTC

Re: Solving the Octopuszle

Postby Lopsidation » Sat Jan 19, 2013 8:11 pm UTC

A recursion depth of 20 means that you're hardly even getting past the first row, so something is probably wrong with your block-placing algorithm.

Yep, your check function has a bug. You copied the DL part from the UR part but forgot to change it. So your code never places a block past the first row.

Also, don't check the whole board every time you place a tile. Only check the tile you just placed, it's much faster.

Finally, the only problem I see with a backtracking algorithm is that only a certain category of blocks can be placed on the borders of the square. If your code runs out of those types of blocks, especially the only blocks that go on the final row, it's out of luck. Try ordering your array of blocks so that it considers those last.

Aldarion
Posts: 133
Joined: Thu Jul 19, 2007 7:00 pm UTC

Re: Solving the Octopuszle

Postby Aldarion » Mon Jan 21, 2013 7:19 pm UTC

Ah, much better. Thanks!

Now the recursion depth is 57 when starting with the tiles arranges lexicographically, and significantly more (100 - 190) with random starting arrangements.
But still not a single solution in sight.

And as the site lists not one, but TWO solutons, meaning that it's proved solvable and non-unique, my goal is nothing less than enumerating all the possible solutions. So... sould I move this to the Infinitely Fast Computer thread? :)
I'm not good, I'm not nice, I'm just right.

User avatar
jaap
Posts: 2091
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Solving the Octopuszle

Postby jaap » Mon Jan 21, 2013 7:52 pm UTC

This is an example of an exact cover problem, so you might want to look into algorithm X, or if you are feeling adventurous, DLX.

Aldarion
Posts: 133
Joined: Thu Jul 19, 2007 7:00 pm UTC

Re: Solving the Octopuszle

Postby Aldarion » Sat Jan 26, 2013 6:44 pm UTC

Thanks, jaap! I read the Wikipedia articles, and concluded that implementing Algorithms X, even the vanilla version, is just a leetle too hard for me.
Fortunately, I found this amazing implementation of DLX in Python in only 30 lines by Ali Assaf.

Then it took me a couple of hours trying to adapt the Octopuszle into an Exact Cover problem, but eventually I did it, fed the thing into the algorithm (had to install Python 3 for it... ugh, what a nightmare of an "improvement"), and...

Image

All in all I ran this thing for three hours, producing 16 solutions. Of course, it wasn't nearly finished... so enumerating all the possible solutions is still a bit unfeasible.
I'm not good, I'm not nice, I'm just right.

User avatar
PM 2Ring
Posts: 3668
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

Re: Solving the Octopuszle

Postby PM 2Ring » Sun Jan 27, 2013 4:34 am UTC

Aldarion wrote:Fortunately, I found this amazing implementation of DLX in Python in only 30 lines by Ali Assaf.


Nice! Pity he used Python 3 features in exact_cover(X, Y). Here's a modified version of his example code that ought to work on Python 2.5+

Code: Select all

#! /usr/bin/env python

''' Knuth's Algorithm X for the exact cover problem, using dicts instead of doubly linked circular lists.
Written by Ali Assaf
From http://www.cs.mcgill.ca/~aassaf9/python/algorithm_x.html

Converted to Python 2.5+ syntax by PM 2Ring 2013.01.27
'''

def solve(X, Y, solution=[]):
    if not X:
        yield list(solution)
    else:
        c = min(X, key=lambda c: len(X[c]))
        for r in list(X[c]):
            solution.append(r)
            cols = select(X, Y, r)
            for s in solve(X, Y, solution):
                yield s
            deselect(X, Y, r, cols)
            solution.pop()

def select(X, Y, r):
    cols = []
    for j in Y[r]:
        for i in X[j]:
            for k in Y[i]:
                if k != j:
                    X[k].remove(i)
        cols.append(X.pop(j))
    return cols

def deselect(X, Y, r, cols):
    for j in reversed(Y[r]):
        X[j] = cols.pop()
        for i in X[j]:
            for k in Y[i]:
                if k != j:
                    X[k].add(i)

#----------------------------------------------------------------------
   
def exact_cover(X, Y):
    newX = dict((j, set()) for j in X)
    for i in Y:
        for j in Y[i]:
            newX[j].add(i)
    return newX

#Print dict d, converting all values to lists
def show_dict(d):
    keys = d.keys()
    keys.sort()
    s = ',\n'.join('    %s: %s' % (k, list(d[k])) for k in keys)
    print '{\n%s\n}' % s

#----------------------------------------------------------------------

#Set that we want to find the exact covers of.
X = set([1, 2, 3, 4, 5, 6, 7])
#A collection of subsets of X. We want subcollections of Y that cover X.
#The unique solution is ['B', 'D', 'F']
Y = {
'A': [1, 4, 7],
'B': [1, 4],
'C': [4, 5, 7],
'D': [3, 5, 6],
'E': [2, 3, 6, 7],
'F': [2, 7]
}
   
def main():
    print 'Set to cover [X]:'
    print X
    print 'Subset collection [Y]:'
    show_dict(Y)
    newX = exact_cover(X, Y)
    print 'Inverted subset collection [newX]:'
    show_dict(newX)
   
    print '\nSolution(s)'
    for s in solve(newX, Y):
        print s
     
if __name__ == '__main__': 
    main()

Aldarion
Posts: 133
Joined: Thu Jul 19, 2007 7:00 pm UTC

Re: Solving the Octopuszle

Postby Aldarion » Wed Jan 30, 2013 5:22 pm UTC

Oh, thank you!

It's still as slow, even when using PyPy, but at least I could uninstall Python 3.
I'm not good, I'm not nice, I'm just right.

User avatar
PM 2Ring
Posts: 3668
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

Re: Solving the Octopuszle

Postby PM 2Ring » Thu Jan 31, 2013 3:44 am UTC

No worries!

I was hoping to use this Algorithm X code to generate big Latin Squares, but it's not so suitable for that purpose due to the depth of recursion required for big squares. Besides, the Latin Squares code I posted a few weeks ago in Hacks and snippets thread seems to be much faster. :)

Aldarion
Posts: 133
Joined: Thu Jul 19, 2007 7:00 pm UTC

Re: Solving the Octopuszle

Postby Aldarion » Sat Feb 02, 2013 8:59 am UTC

Anyway, the biggest problem is not speed (unless I'm willing to invent a better algorithm than X).
The biggest problem is persistence: I can't leave my computer on 24/7, so there has to be a way of saving the state of the process.
But the algorithm is written as a generator, and those can't be saved...

I tried Kay Schluehr's picklegenerator module, but it doesn't work propperly.
I'm not good, I'm not nice, I'm just right.

User avatar
PM 2Ring
Posts: 3668
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

Re: Solving the Octopuszle

Postby PM 2Ring » Fri Feb 08, 2013 4:47 am UTC

Oh.

Maybe you can "unroll" the recursion a little, so that it generates one solution at a time?

Aldarion
Posts: 133
Joined: Thu Jul 19, 2007 7:00 pm UTC

Re: Solving the Octopuszle

Postby Aldarion » Sat Mar 02, 2013 7:20 pm UTC

Found a better solution. I'm simply running the script in a VM. :)
That way I can just save the state and resume it whenever I like. It's a bit slower, of course, but if the number of possible solutions is astronomical, it wouldn't matter anyway, right?
I'm not good, I'm not nice, I'm just right.

User avatar
snowyowl
Posts: 464
Joined: Tue Jun 23, 2009 7:36 pm UTC

Re: Solving the Octopuszle

Postby snowyowl » Mon Mar 04, 2013 4:47 pm UTC

I have a related question I would like to ask the panel.

Would it be remotely feasible to use this sort of algorithm to find a De Bruijn torus for m=n=3?
It should be a 32x16 board (probably, as long as it's toroidal and has 512 cells) filled with cells that are either black or white, such that every 3x3 subgrid appears exactly once. (Edges wrap around.)

As far as I'm aware, nobody has ever managed to find even a single solution. This is probably because the amount of computing time is just too ridiculous, since there are quadratically more configurations to test than in the Octopuszle. But I live in hope.
The preceding comment is an automated response.

User avatar
thoughtfully
Posts: 2253
Joined: Thu Nov 01, 2007 12:25 am UTC
Location: Minneapolis, MN
Contact:

Re: Solving the Octopuszle

Postby thoughtfully » Mon Mar 04, 2013 8:59 pm UTC

It's not an elegant solution, but you could run the program in a virtual machine and save its state when you are shutting your computer down.
Image
Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away.
-- Antoine de Saint-Exupery

User avatar
PM 2Ring
Posts: 3668
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

Re: Solving the Octopuszle

Postby PM 2Ring » Fri Mar 08, 2013 6:49 am UTC

snowyowl wrote:Would it be remotely feasible to use this sort of algorithm to find a De Bruijn torus for m=n=3?
It should be a 32x16 board (probably, as long as it's toroidal and has 512 cells) filled with cells that are either black or white, such that every 3x3 subgrid appears exactly once. (Edges wrap around.)


Interesting. I haven't heard of those before, although I read about binary De Bruijn sequences in a Martin Gardner article many years ago.

It does sound like an exact cover problem, so I suppose that it could be solved by Knoth's Algorithm X if you can figure out how to handle the overlapping nature of the bit blocks. I thought I'd figured out a way to do it, but I was wrong. :) OTOH, I'm certainly no expert on expressing problems in exact cover form; all I've used it for is finding Latin squares and map colouring.

snowyowl wrote:As far as I'm aware, nobody has ever managed to find even a single solution. This is probably because the amount of computing time is just too ridiculous, since there are quadratically more configurations to test than in the Octopuszle. But I live in hope.


Well, it'd take a long time to do a naive bit-by-bit brute-force search. :)

Algorithm X isn't particularly fast, and it's certainly not very smart. It's main advantage over a naive brute-force search is that Algorithm X backs out of partial solutions that cannot be consistently completed, but that's also true of other recursive backtracking techniques. I guess that Algorithm X is good if there are lots of solutions, as it tends to "sieve through" the problem space, progressively concentrating the solutions into a smaller & smaller space.

I suspect that an Algorithm X solution to the 3x3 De Bruijn torus puzzle would use a lot of memory, even using the set-based approach rather than the traditional linked list sparse array. But I guess that the memory requirements (and speed) might be acceptable if you come up with a clever way of handling the overlap. The overlap severely restricts which 3x3 bit grid "tiles" can be (overlapping) neighbours of each other; any sane program needs to utilize that information. Still, if I were tackling this problem, I'd be tempted to use a more basic recursive backtracking approach, rather than Algorithm X.


FWIW, it took me about 5 minutes to find a solution to the 2x2 De Bruijn torus by hand. My solution has some interesting symmetries. I don't know if this solution is unique (up to reflection/rotation), but I suspect that it is.

In binary, it's
0001
0010
1011
0111

In hex, it's
0168
25b3
97fe
4cda

Notice that each hex number is 2 units diagonally from its complement, so the xor of each diagonal is 0, and also
the xor of each row and column is f. I suspect that all solutions to the 2x2 problem have these properties, and that similar symmetries exist in any solution to the 3x3 problem.

User avatar
snowyowl
Posts: 464
Joined: Tue Jun 23, 2009 7:36 pm UTC

Re: Solving the Octopuszle

Postby snowyowl » Fri Mar 08, 2013 8:45 am UTC

I don't know if this solution is unique (up to reflection/rotation), but I suspect that it is.

It is unique, but we're on a torus so there are rather more symmetries than usual.
The preceding comment is an automated response.

User avatar
PM 2Ring
Posts: 3668
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

Re: Solving the Octopuszle

Postby PM 2Ring » Sat Mar 09, 2013 4:41 am UTC

snowyowl wrote:
I don't know if this solution is unique (up to reflection/rotation), but I suspect that it is.

It is unique, but we're on a torus so there are rather more symmetries than usual.


Well, I was using the term "rotation" to cover rotations of the torus, too. :)

And yes, it is unique. Here's a little Python program that finds the solution (and its reflection) by brute force. To simplify the search slightly & eliminate most of the symmetries, I put the 2x2 zero block in the centre of the 4x4 bitgrid, but I didn't bother to restrict the search to bitgrids with equal numbers of 0 & 1 bits, since the program completes the search in under a second.

DeBruijn1.py

Code: Select all

#! /usr/bin/env python

'''
  DeBruijn toruses
 
  A brute-force search for 4x4 bitgrid toruses that contain
  each of the 16 2x2 bitgrids exactly once.
  The 2x2 block of zeroes must occur somewhere in the torus,
  so we simplify the search by setting this zero block in the centre
  of the 4x4 bitgrid.
'''

#Print a sequence of sequences as a grid
def putgrid(g):
    print '\n'.join(''.join(str(i) for i in row) for row in g) + '\n'

#Convert integer n to a generator of bits of length w
def itobits(n, w):
    return ((n>>i) & 1 for i in xrange(w-1, -1, -1))
   
#Convert a sequence of bits to integer
def bitstoi(bits):
    s = 0
    for b in bits:
        s = (s<<1) + b
    return s

def DeBruijn():
    r4 = range(4)
    r4a = (1, 2, 3, 0)
    rr = zip(r4, r4a)

    #Initialize the bitgrid to all zeroes
    grid = [4*[0] for i in r4]

    #Make a list of all the grid co-ords in the outer ring
    ring = [(j, i) for j in r4 for i in r4 if i in (0, 3) or j in (0, 3)]
    #putgrid(ring)

    #Test that all grid blocks are unique. If so return them, else return None
    def testblocks():
        blocks = []
        for j, j1 in rr:
            for i, i1 in rr:
                q = ((j, i), (j, i1), (j1, i), (j1, i1))
                block = bitstoi(grid[v][u] for v,u in q)
                if block in blocks:
                    return None
                blocks.append(block)
        return blocks

    for n in xrange(1<<12):
        #Convert n to bits & set them in the outer ring
        for b, (y, x) in zip(itobits(n, 12), ring):
            grid[y][x] = b

        blocks = testblocks()
        if blocks:
            print '%4d\n' % n
            putgrid(grid)
            #Convert block list to a hex grid
            blocks = ['%X' % i for i in blocks]
            blocks = [blocks[i:i+4] for i in xrange(0, 16, 4)]
            putgrid(blocks)
            print

def main():
    DeBruijn()

if __name__ == '__main__':
    main()


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 6 guests