## 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

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: 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: To get the solutions I wrote a fairly simple recursive backtracker in Python:

Code: Select all

`import Image, ImageDrawimport psycopsyco.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 tilesbrd = 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))# Backtrackingbacktrack(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: The board to tile up is 16x16, obviously.

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

Code: Select all

`from random import shuffleimport Image, ImageDrawimport psycopsyco.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   returndef 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 tilesbrd = Board()tiles = []for Ort in range(16):   for Diag in range(16):      tiles.append(genTile(Ort, Diag))# Backtrackingtiles = tiles[::-1]print tilesbacktrack(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.

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

### Re: Solving the Octopuszle

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

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.

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

### Re: Solving the Octopuszle

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

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... 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.

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

### Re: Solving the Octopuszle

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 AssafFrom http://www.cs.mcgill.ca/~aassaf9/python/algorithm_x.htmlConverted 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 colsdef 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 listsdef 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

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.

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

### Re: Solving the Octopuszle

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

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.

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

### Re: Solving the Octopuszle

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

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.

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

### Re: Solving the Octopuszle

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.

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

### Re: Solving the Octopuszle

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. Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away.
-- Antoine de Saint-Exupery

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

### Re: Solving the Octopuszle

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.

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

### Re: Solving the Octopuszle

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.

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

### Re: Solving the Octopuszle

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 griddef 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 wdef itobits(n, w):    return ((n>>i) & 1 for i in xrange(w-1, -1, -1))    #Convert a sequence of bits to integerdef bitstoi(bits):    s = 0    for b in bits:        s = (s<<1) + b    return sdef DeBruijn():    r4 = range(4)    r4a = (1, 2, 3, 0)    rr = zip(r4, r4a)    #Initialize the bitgrid to all zeroes    grid = [4* 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)            printdef main():    DeBruijn()if __name__ == '__main__':    main()`