Solving the Eternity 2 puzzle and other tiling problems using D-Wave BlackBox
Aim, audience and required background
This material was developed to help those interested in the physics of the D-Wave OneTM System to perform some simple experiments and explore some of the interesting science behind the processor technology. This tutorial series is designed to introduce you to quantum computer programming using a practical, hands-on approach.
All of the software necessary for developers to begin learning how to program D-Wave quantum computing systems can be downloaded from the DOWNLOAD DEVKITS page. As the developer portal is currently in BETA test stage, you will need to have a D-Wave developer account to download these packs. To follow this tutorial it may be helpful to have read two of the previous installments: Getting Started: Installing the D-Wave developer pack and an introductory 'hello multiverse' tutorial and Introduction to the BlackBox compiler
The high level programming language used in the included examples and source code is Python 2.6. Some experience of using the Python programming language is helpful but not required.
What you will learn
By following through the material in this white paper, you will learn:
In order to proceed you should install several free software packages.
1.1 - Introduction to the puzzle
The Eternity II TMpuzzle ( sold by Tomy) is a physical jigsaw puzzle which comprises of 256 square pieces with brightly coloured designs on each edge of the pieces.
Figure 1. Some eternity 2 puzzle pieces
The player must align matching designs so that there are no mismatches to solve the puzzle. The interesting thing about this puzzle was that if you are able to put all the puzzle pieces together correctly, you could submit the answer by mail to the makers, and a prize of 2 million dollars was offered for the first correct solution. Sounds simple? Well, the competition closed on 31st December 2010 and no-one won the prize.
Although matching edges of tiles is a very simple idea, Eternity II is a very hard combinatorial optimization problem. The best solution found during the competition's lifetime (winning a runner-up prize of $10,000) was a solution with 467 of 480 matching edges. Since then there are some solutions that have popped up on the internet, see here for example. It is straightforward to see at a high level why this puzzle is a good fit for the D-Wave hardware. It involves discrete optimization (does an edge match or not?), it is combinatorial (the number of possible ways of arranging the pieces grows astronomically fast with the number of pieces), and it is simple to map into a programmatic format (just assign numerical labels to different edge designs). So let's begin looking at this problem in more detail.
1.2 - Creating colors for the edges
The first thing I am going to do is create some visual representations of tiles in the puzzle. It is totally up to you whether or not you like visualizing the output of your programs, but I find it very useful for debugging and to keep track of what mistakes the solver is making. It also makes the tutorial look pretty.
So firstly we will make some edges of different colours. Instead of making complex patterned tiles as in figure 1, we'll just use different colours to denote the different edge-types. There are 23 different types of edge colour possible in the puzzle (including grey which symbolizes the edge of the board). I created these edges as JPG images in a paint program. They are all 100px x 100px. Here are some of them:
Figure 2. Images of the edge colours that will be used to make up the tiles
I named them piece0.jpg, piece1.jpg, etc. where the number in the filename will be the "index" associated with an edge of that colour.
1.3 - Creating tiles
We can write our tiles as a series of 4 of the numbered colored edge pieces above. I created my own solved puzzle. I just drew a 4x4 board and coloured in the tiles randomly but without any mismatching edges. Here's a fun shot from my lab book to prove it:
Figure 3. Creating a tileset by colouring in your lab book.
So to write the tile definitions list we just take each tile in turn (counting left-right, top-bottom) and create an entry for each tile which stores the coloured edges in numeric format, using the structure [top, right, bottom, left]. For example, the first (top left) piece has [grey, red, yellow, grey] so its corresponding numeric string will be [0,1,2,0].
Code snippet 1 - tile definitions
tiles_16_colors = [ [0,1,2,0], [0,3,1,1], [0,2,2,3], [0,0,4,2], [2,3,4,0], [1,1,4,3], [2,4,1,1], [4,0,2,4], [4,1,2,0], [4,2,3,1], [1,2,2,2], [2,0,1,2], [2,3,0,0], [3,4,0,3], [2,3,0,4], [1,0,0,3]]
The next thing is to write as routine to create these tiles from our coloured edge pieces jpegs.
Code snippet 2 - building the tileset
from e2_code_snippet1 import * import Image as im def build_a_piece(piece, piece_index, foldername): '''Creates a jpg image of a piece given a piece object (which is a list of 4 triangles) a piece index for the filename, and a folder to save the piece images in''' [top_piece_number, right_piece_number, bottom_piece_number, left_piece_number] = piece test_piece = im.open("piece_images/test_piece.jpg") top_piece = im.open("piece_images/piece" + str(top_piece_number) + ".jpg") right_piece = im.open("piece_images/piece" + str(right_piece_number) + ".jpg") bottom_piece = im.open("piece_images/piece" + str(bottom_piece_number) + ".jpg") left_piece = im.open("piece_images/piece" + str(left_piece_number) + ".jpg") for y in range(0,100): for x in range(0,100): if y<100-x and y<x: # This is the top triangle in the square rotation_0 = (x,y) rotation_270 = (y,x) rotation_180 = (x,99-y) rotation_90 = (99-y,99-x) pixels = top_piece.getpixel((x,y)) test_piece.putpixel(rotation_0, pixels) pixels = right_piece.getpixel((x,y)) test_piece.putpixel(rotation_90, pixels) pixels = bottom_piece.getpixel((x,y)) test_piece.putpixel(rotation_180, pixels) pixels = left_piece.getpixel((x,y)) test_piece.putpixel(rotation_270, pixels) test_piece.save("piece_images/" + str(foldername) + "/piece_index"+ str(piece_index) + ".jpg") tile_list = tiles_16_colors tile_list_string = "tiles_16_colors" #Here we create the tiles. We only need to do this once. for i in range(len(tile_list)): build_a_piece(tile_list[i], i, tile_list_string)
Here I've used to Python module "Python Imaging Library" (PIL) to do the image manipulations involved in putting each edge piece in the right place for each tile, and save the resulting tiles. This code takes the pixels from each corresponding piece in the edge colours set and places them at the appropriate location in the tile according to your tile_list which we imported from the previous snippet. You will need to make a new folder called 'tiles_16_colors' into which the program can save the tile images. Once you have done this you should see something like this appear in your folder:
Figure 4. The generated set of tiles that correspond to a 4x4 problem with a known solution.
1.4 - Encoding the tile positions and rotations into a bitstring
Because BlackBox deals with binary variables, we must now find some way of 'encoding' our problem into a bitstring format so that BlackBox can optimize the tile placements and rotations.
There are many different ways to do this. I've chosen a simple one, but if you have any better ideas feel free to implement them instead.
In this version of the encoding, we assign a certain number of bits from the bitstring to define what is happening at each board location.
Each tile position has a chunk of X bits allocated to it from the BlackBox bitstring to specify it. The first \(ceiling(log base 2 (n))\) bits in the ith chunk of bits are used to encode the tile that is present at position i. The next 2 bits of the chunk are used to encode the rotation. Here is a diagram to explain this concept:
Figure 5. Encoding the piece positions and rotations into a bitstring.
So for 16 tiles you need 4 + 2 = 6 bits per tile, giving 6*16 = 96 optimization variables. For 256 you would need 8+2 = 10 bits per tile, giving 10*256 = 2560 variables. We are going to be dealing with a 4x4 puzzle to keep the number of variables reasonably small.
We will write a function to grab the indices and rotations of each piece from a given bitstring. This will be necessary as later on we will see that BlackBox will suggest bitstrings, and we must take those bitstrings and figure out what the resulting piece configuration is.
Code snippet 3 - extracting the indices and rotations from a given bitstring
from e2_code_snippet2 import * from math import ceil, log def get_piece_indices_from_bitstring(bitstring, n): '''Takes a bitstring and returns the indices and rotations of all pieces in their decimal format''' piece_indices =  piece_rotations =  index_length = int(ceil(log(n**2, 2))) chunk_length = index_length+2 for i in range(n**2): bitstring_index = bitstring[chunk_length*i:chunk_length*i+index_length] decimal_index = 0 for i in range(len(bitstring_index)): if bitstring_index[i]: counter = 2**(len(bitstring_index)-i-1) decimal_index += counter piece_index = decimal_index piece_indices.append(piece_index) bitstring_rotation = bitstring[chunk_length*i+index_length:chunk_length*i+index_length+2] piece_rotation = bitstring_rotation*2+\ bitstring_rotation piece_rotations.append(piece_rotation) return piece_indices, piece_rotations
It may be worth noting that I have made the code general for a puzzle of any size (nxn) in these early parts of the code (although later on there are some hardcoded values!) but making things general in this way will slow down the code, so for the most efficient solving of a particular choice of nxn you may wish to hardcode values such as n and replace the bitstring indexing code with suitable fixed values.
1.5 - Visualizing the puzzle board
We now write some code to visualize the board given a bitstring, and the tileset that we have created.
In normal operation the bitstring will be supplied by BlackBox, but as we haven't written any BlackBox code yet, we'll have to test out our visualization
routine using a 'dummy' bitstring. Here I just compiled a bitstring called
test_bitstring which has the
same piece repeated 16 times. I picked piece 8 just because I liked it. You might want to change the
test_bitstring to check your understanding of it.
The code just uses PIL to paste the tiles onto a new image. The tiles are resized to 50x50px and the
function computes how big the board should be from this and the value of n. For our example n=4 so
the board is 200x200px. The visualization routine uses the function that we wrote in code snippet 3
to extract the index and the rotation of each tile from the bitstring encoding. It then just places
the tile at the relevant position on the board and rotates it accordingly. Note the PIL rotates things
counter-clockwise, so we specify our rotation list in reverse as
[0, 270, 180, 90]
Once all tiles are placed, the function saves the completed board to the file
Code snippet 4 - Visualization routine running with a 'dummy' bitstring
from e2_code_snippet3 import * def visualize_board(bitstring, tile_description_string, n): '''Loads corresponding tiles from the tile_description_string folder and places them on the board according to the values given in the bitstring. Saves the resulting image to a jpg file''' piece_indices_by_position, piece_rotations_by_position = get_piece_indices_from_bitstring(bitstring, n) small_tile_size = 50 board_size = small_tile_size*n positions_list =  rotations = [0,270,180,90] for j in range(n): for i in range(n): positions_list.append([i*board_size/n,j*board_size/n]) board = im.new("RGB", (board_size,board_size)) for piece in range(len(piece_indices_by_position)): pic_index = piece_indices_by_position[piece] tile = im.open("piece_images/" + str(tile_description_string)+ "/piece_index"+str(pic_index)+".jpg") small_tile = tile.resize((small_tile_size,small_tile_size)) rotated_small_tile = small_tile.rotate(rotations[piece_rotations_by_position[piece]]) board.paste(rotated_small_tile, tuple(positions_list[piece])) board.save("e2_board.bmp") test_bitstring = [1,0,0,0, 0,0, 1,0,0,0, 0,0, 1,0,0,0, 0,0, 1,0,0,0, 0,0,\ 1,0,0,0, 0,0, 1,0,0,0, 0,0, 1,0,0,0, 0,0, 1,0,0,0, 0,0,\ 1,0,0,0, 0,0, 1,0,0,0, 0,0, 1,0,0,0, 0,0, 1,0,0,0, 0,0,\ 1,0,0,0, 0,0, 1,0,0,0, 0,0, 1,0,0,0, 0,0, 1,0,0,0, 0,0, ] n=4 tile_list = tiles_16_colors tile_list_string = "tiles_16_colors" visualize_board(test_bitstring, tile_list_string, n)
Using the test_bitstring defined above, the resulting board output should look something like this!
Figure 6. Output of the visualization routine using the dummy bitstring.
2.1 - Some helper functions
There are a couple of things we'll want to do a lot when figuring out if pieces are in the right locations, so before we start on the main task of crafting our objective function, let's write some helper functions to handle things we might want to do several times. These three helper functions are given in code snippet 5 and explained below.
Code snippet 5 - A few helper functions
from e2_code_snippet4 import * def compute_row_map(n): '''Compute simple list describing which row pieces belong to, e.g. [0,0,0,1,1,1,2,2,2] for 3x3 board''' row_map =  for i in range(n): the_row = [i]*n for each in the_row: row_map.append(each) return row_map def get_piece_adjacency(piece_index, row_map, n): #'''Returns the neighbours of a given piece index, in the format [above, right, below, left]''' piece_above_index = n*(row_map[piece_index]-1) + piece_index%n if piece_index < n: piece_above_index = -1 piece_right_index = piece_index +1 if piece_index % n == (n-1): piece_right_index = -1 piece_below_index = n*(row_map[piece_index]+1) + piece_index%n if piece_below_index >= n**2-n: piece_below_index = -1 piece_left_index = piece_index -1 if not piece_index % n: piece_left_index = -1 return [piece_above_index, piece_right_index, piece_below_index, piece_left_index] def compute_valid_edges(n, row_map): '''Computes the edgeset of an nxn eternity 2 board, by examining each piece in turn and computing the positions of its top and left neighbours (we only do 2 edges so that we do not double count). The remaining uncounted bottom right edges are added on separately. Outer edges are included in the edgeset and their neighbouring edge outside the board area is denoted by the a special '-1' status.''' valid_edges =  for position in range(n**2): adjacency = get_piece_adjacency(position, row_map, n) valid_edges.append([position, 0, adjacency, 2]) # 0 (top) edge matches 2 (bottom) neighbour edge valid_edges.append([position, 3, adjacency, 1]) # 3 (left) edge matches 1 (right) neighbour edge if position % n == (n-1): valid_edges.append([position, 1,adjacency, 3]) for position in range(n**2-n,n**2): adjacency = get_piece_adjacency(position, row_map, n) valid_edges.append([position, 2,adjacency, 0]) return valid_edges
Row numbers are important when looking for adjacent pieces, so the first helper function is a very simple routine that returns a list with entries denoting the row that each piece with the matching index belongs to. I call this function row_map. For a 4x4 board it looks like [0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3]
The second thing we wish to do is when given a board position, we'd like to know the indices of the positions adjacent to it, so we can figure out if the tiles in those positions have matching edges. I called this function get_piece_adjacency. So for example if you feed the function piece index 5, it should return [1,6,9,4]. The pieces along the outer edge of the board are a special case. For these edges we make the neighbour of each outer edge the same - a special index which is denoted -1 so that we know it adjoins the edge of the board.
The third thing we'd like to do is use this adjacency function to figure out a list of valid
edges, so that when we come to check for matching edges later, we know which ones are valid
where puzzle pieces align. This function is called compute_valid_edges. There are a couple
of twists to this function. Note that when we are adding valid edges to the list, we must
check if top of our piece against bottom of its neighbour above, and the right edge of our
piece against the left edge of its neighbour, which means making sure that our indexing is correct when we pull the entries from the list
get_piece_adjacency. This is why index 0 is paired with 2 and index 1 is paired
with 3. The format of an 'edge' list is therefore
[position, position_edge, neighbour_position,
neighbour_position_edge]. We add edges in the following way. For each piece, add the top/neighbour_bottom
and left/neighbour_right edges (Pink edges in figure 7). This avoids double counting the edges. We then end up with some
edges on the far right of the board and the bottom of the board that are uncounted, so we deal
with those separately, by checking if
position % n = (n-1) which tells us that the position
is on the right hand edge of the board (black edges in figure 7), and also checking if
position is in the range \(n^2-n \) to \( n^2\).
which tells us if the piece is on the bottom edge of the board (blue edges in figure 7). The diagram below should help
Figure 7. Adding valid edges to an edge list whilst avoiding double counting. The pink edges are the ones that get counted by iterating over each position on the board, whilst the black edges and blue edges are handled separately.
2.2 - Crafting the objective function
Now we will craft an objective function that penalizes BlackBox for putting pieces in the wrong places, etc. Again there are many different ways to craft an objective function. I have chosen one which is simple but includes several terms to give the solver a little bit of help. Let's start by thinking about what we are trying to do. We are trying to align the pieces so that there are as few edges mismatches as possible. It is clear that our objective function should include a term that increases the 'penalty' every time an edge in the solution does not match its neighbouring edge.
So in the image below, we count up the number of mismatching edges:
Figure 8 - Example of a board with mismatched edges. Mismatches are shown in black.
There are 21 mismatched edges in this example.
But this objective function is really dumb. Why? Because we have more information than that. And the more information we can provide to BlackBox about the structure of the problem the better chance we have of solving it. Think about how you, as a human, would go about solving this puzzle. As an aside, it is kind of cool how everytime you solve a jigsaw puzzle you are actually undertaking an exercise in algorithmics. So to improve our objective function, let's write down some statements that seem obvious to humans when trying to solve E2:
These rules seem really obvious to a human who is trying to solve the problem, but remember that our algorithm is only as smart as we tell it to be! So we need to write functions that capture the idea that there is an additional penalty accrued if any of these concepts are violated. So our smarter objective function is made up of 4 separate penalty terms, which are briefly explained along with a function which implements them:
First penalty: mismatched edges
This is the obvious penalty shown in figure 8 above. The algorithm picks
up a summed penalty for each edge that doesn't match (including outer edges). We got through the list of valid edges
that we already compiled in the function
compute_valid_edges, and check if the edges in each edges-pair (by
grabbing the corresponding piece and applying a rotation to it) are the same.
Code snippet 6 - Calculate mismatches
from e2_code_snippet5 import * def calculate_mismatches(bitstring, tile_list, valid_edges, n): #'''Returns a penalty corresponding to the number of mismatched edges in the whole puzzle #including outer edges. Handles tile rotations''' piece_indices_by_position, piece_rotations_by_position = get_piece_indices_from_bitstring(bitstring, n) mismatches = 0 for i in range(len(valid_edges)): # piece_rotations are [0,1,2,3] format # if it is rotated 0 degrees, you want to add 0 to the edge # if it is rotated 90 degrees, you want to add 1 to the edge # if it is rotated 180 degrees, you want to add 2 to the edge # if it is rotated 270 degrees, you want to add 3 to the edge] # but it has to be modulo arithmetic too #Then get the positions of the pieces to check piece_1_position = valid_edges[i] piece_2_position = valid_edges[i] #Then get the 2 edges to check from these pieces after they have been adequately rotated edge_to_check_1 = (valid_edges[i]-(piece_rotations_by_position[piece_1_position])) % 4 edge_to_check_2 = (valid_edges[i]-(piece_rotations_by_position[piece_2_position])) % 4 #Now get the tiles that are at these positions: tile1 = piece_indices_by_position[piece_1_position] tile2 = piece_indices_by_position[piece_2_position] # Now get the patterns that are at the relevant edge of both tiles (if the second tile is # overflowing the board edge, we check against the "all grey" tile): if piece_2_position == -1: #Check for the grey edges pattern1 = tile_list[tile1][edge_to_check_1] pattern2 = all_grey_tile[edge_to_check_2] if pattern1 != pattern2: mismatches +=1 else: pattern1 = tile_list[tile1][edge_to_check_1] pattern2 = tile_list[tile2][edge_to_check_2] if pattern1 != pattern2: mismatches +=1 return mismatches
Second penalty: Using tiles incorrectly
The algorithm is penalized if it uses the same tile twice (which it can do in this formulation as the tile is specified simply by 4 of the bits in the bitstring). In order to enforce this penalty, each time a tile has been used we remove it from a list of "allowed tiles". If the tile that the solver is trying to put in a particular position is NOT present in allowed tiles, it means that it has already been used, and the penalty is incremented.
Code snippet 7 - Bad tile choice
from e2_code_snippet6 import * def calculate_bad_tile_choice(bitstring, n): '''Returns a summed penalty if piece indices are used more than once in the bitstring. This function is currently hardcoded to a 4x4 board''' allowed_tile_selection = [ [0,0,0,0],[0,0,0,1],[0,0,1,0],[0,0,1,1], [0,1,0,0],[0,1,0,1],[0,1,1,0],[0,1,1,1], [1,0,0,0],[1,0,0,1],[1,0,1,0],[1,0,1,1], [1,1,0,0],[1,1,0,1],[1,1,1,0],[1,1,1,1]] penalty = 0 for i in range(n**2): selection_to_check = list(bitstring[6*i:6*i+n]) if verbose: print len(allowed_tile_selection), allowed_tile_selection if selection_to_check in allowed_tile_selection: allowed_tile_selection.remove(selection_to_check) else: penalty +=3 return penalty
Third penalty: Using edge piece incorrectly
If an edge piece is not placed in a edge
slot, the algorithm accrues a penalty. Again we use a list of allowed edge pieces and remove edge pieces from the list
once they have been used. If BlackBox attempts to put anything other than the pieces in
allowed_edge_pieces, or tries to use them more than once, it is penalized.
Code snippet 8 - Bad edge choice
from e2_code_snippet7 import * def calculate_bad_edge_choice(bitstring): '''Returns a summed penalty if edge pieces as described by the bitstring are not in valid edge locations. This function is currently hardcoded to a 4x4 board''' #decimal values for allowed edge pieces = 1,2,4,7,8,11,13,14 allowed_edge_pieces = [[0,0,0,1],[0,0,1,0], [0,1,0,0],[0,1,1,1], [1,0,0,0],[1,0,1,1], [1,1,0,1],[1,1,1,0]] penalty = 0 #These are the parts of the bitstring that encode the edge positions in a 4x4: for i in [[6,10], [12,16], [24,28], [42,46], [48,52], [66,70], [78,82], [84,88]]: selection_to_check = list(bitstring[i:i]) if selection_to_check in allowed_edge_pieces: allowed_edge_pieces.remove(selection_to_check) else: penalty +=4 return penalty
Fourth penalty: Using corner pieces incorrectly
if a corner piece is not placed in a
corner slot, the algorithm accrues a penalty. Again we create a list of allowed corner pieces and remove corner pieces from the list
once they have been used. If BlackBox attempts to put anything other than the pieces in
allowed_corner_pieces, or tries to use them more than once, it is penalized.
Code snippet 9 - Bad corner choice
from e2_code_snippet8 import * def calculate_bad_corner_choice(bitstring): '''Returns a summed penalty if corner pieces as described by the bitstring are not in valid corner locations. This function is currently hardcoded to a 4x4 board''' #decimal values for corner pieces = 0,3,12,15 allowed_corner_pieces = [[0,0,0,0],[0,0,1,1], [1,1,0,0],[1,1,1,1]] penalty =0 #These are the parts of the bitstring that encode the corner positions in a 4x4: for i in [[0,4], [18,22], [72,76], [90,94]]: selection_to_check = list(bitstring[i:i]) if selection_to_check in allowed_corner_pieces: allowed_corner_pieces.remove(selection_to_check) else: penalty +=5 return penalty
This method can probably be optimized by using e.g. bit-wise XOR functions instead of list manipulations (although Python is very fast with lists so I am not quite sure about that) You can adjust the relative strengths of the 4 penalty terms if you are always getting one type of mistake. I empirically set them to be in the ratio:
penalty_corner : penalty_edge : penalty_tile_choice : penalty_mismatches = 5:4:3:1
You can experiment with different settings for these penalty weighting pre-factors Note that we do not have to include the first 'concept' in the list above, as this is already captured in the fact that the each position has its own 'unique' set of bits in the bitstring.
Once we have all our penalty functions defined, we can incorporate them into a class which creates an object we can pass to BlackBox. Here is the class definition:
Code snippet 10 - Class MismatchFunction
from e2_code_snippet9 import * import array class MismatchFunction(object): '''Crafts the objective function for consumption by BlackBox using the 4 penalty terms defined''' def __init__(self, tile_list, valid_edges, n): # Variables needed to compute overall penalty self.tile_list = tile_list self.valid_edges = valid_edges self.n = n def __call__(self, states, numStates): states_bin = [(item+1)/2 for item in states] # converting to 0/1 from -1/+1 stateLen = len(states)/numStates ret =  for state_number in range(numStates): bitstring = array(states_bin[state_number*stateLen:(state_number+1)*stateLen]) penalty1 = calculate_mismatches(bitstring, self.tile_list, self.valid_edges, self.n) penalty2 = calculate_bad_tile_choice(bitstring, self.n) penalty3 = calculate_bad_corner_choice(bitstring) penalty4 = calculate_bad_edge_choice(bitstring) result = penalty1+penalty2+penalty3+penalty4 ret.append(result) return tuple(ret)
2.3 - Sending the function to BlackBox
Now that we have all the functions written, we can write a main routine to solve the puzzle and visualize the output.
Code snippet 11 - Main routine
from e2_code_snippet10 import * from dwave_sapi import LocalConnection, BlackBoxSolver ##------------------------------------------------------------## ##--------------MAIN ROUTINE----------------------------------## ##------------------------------------------------------------## conn = LocalConnection() solver = conn.get_solver("c4-sw_sample") blackbox_parameter = 12 # Sets strength vs. speed of BB (higher = more powerful/slower). n = 4 num_vars = 96 tile_list = tiles_16_colors tile_list_string = "tiles_16_colors" row_map = compute_row_map(n) valid_edges = compute_valid_edges(n, row_map) #Now we use Blackbox solver to provide the bitstring definition. mismatch_function = MismatchFunction(tile_list, valid_edges, n) blackbox_solver = BlackBoxSolver(solver) blackbox_answer = blackbox_solver.solve(mismatch_function, num_vars, cluster_num = 6, \ min_iter_inner = blackbox_parameter, \ max_iter_outer= blackbox_parameter, \ unchanged_threshold=blackbox_parameter, \ max_unchanged_objective_outer=blackbox_parameter, \ max_unchanged_objective_inner = blackbox_parameter, \ unchanged_best_threshold = blackbox_parameter, verbose=1) print blackbox_answer blackbox_answer_bin = [(item+1)/2 for item in blackbox_answer] # converting to 0/1 from -1/+1 print "The best bit string we found was:",blackbox_answer_bin print "The number of mismatches is:", calculate_mismatches(blackbox_answer_bin, tile_list, valid_edges, n) print "The number of bad tiles is:", calculate_bad_tile_choice(blackbox_answer_bin, n)/3 print "The number of bad corners is:", calculate_bad_corner_choice(blackbox_answer_bin)/5 print "The number of bad edges is:", calculate_bad_edge_choice(blackbox_answer_bin)/4 visualize_board(blackbox_answer_bin, tile_list_string, n)
I tried this code for the 4x4 puzzle on my small laptop (not a very powerful machine) and after 3 attempts with BlackBox parameter set to 12 and numclusters set to 6, the solver found the solution!
Figure 9. Printout from running the main routine showing the BlackBox iteration cycles converging upon the global minimum.
Here is the output image returned:
Figure 10. The solution found by the BlackBox solver
You can see that it is identical to my lab book diagram, but rotated 180 degrees. There are obviously 4 degenerate solutions that Blackbox can find (rotations of the original) - but are there other degeneracies? Who knows. Maybe you could find some :)
2.4 - Extensions
More penalties: Another penalty that I haven't added yet is to enforce edge and corner rotation to be correct (so at the moment the system is rewarded for putting a corner piece in the corner but not yet for rotating it correctly). Currently it relies on the mismatch penalty to do this, which is not the best way to do it as there is extra information in the corner and edge pieces. This penalty is easy to add, I just haven't done it yet.
Better objective functions: Again, remember that this is the simplest way of doing this objective function crafting procedure to keep the tutorial relatively simple. It is up to you to figure out a complex (and better) way!
Better bitstring encoding: A clever way you could reduce the number of optimization variables is to try to enforce constraints such as only selecting each tile in the set once by removing variables / variable fixing instead of by list-checking. What this basically means is that if a tile can only be used in one position then you can enforce constraints between groups of bits, which in practice can be implemented by removing a certain number of bits from the expression. However, this is outside the scope of this tutorial, and is left as an extension for the reader!
And finally: Of course there's the obvious extension - trying to go from this 16 piece puzzle to solving the 256 piece puzzle! Not for the faint hearted. Here is what such a beast would look like, again using a dummy bitstring (randomly generated):
Figure 11. Imagining what the full size puzzle would look like to inspire quantum developers around the world..
Thanks for reading, and happy programming!