Solving a University Quest Puzzle with Python
Black and White – one of the interesting puzzles of the game Puzzle Hunt University of Melbourne in 2010. The game has you pursuing a mysterious participant in a TV show in the hopes of uncovering his identity. You manage to get into the studio first, and then into his dressing room. There, in his clothes, you find a piece of paper. One side of it contains a message, the other – a puzzle and a set of instructions for it.
“Spread each of the diagrams below into 1×1, 1×2, or 1×3 strips so that no grid contains strips with the same black and white pattern, including turns.”
The puzzle consists of 25 square fields arranged in 5 rows and 5 columns. In turn, each field is divided into 25 cells by horizontal and vertical lines. The cells have a white or black background, and each of them contains one letter.
First, let's determine which strips we can use to solve this problem. There are 6 different 1×3 strips (WWW, WWB, WBW, WBB, BWB, and BBB), 3 different 1×2 strips (WW, WB, and BB), and 2 different 1×1 strips (W and B). In total, these strips contain 26 cells. This means that to factorize each board, we will have to use all the 1×3 strips, all the 1×2 strips, and only one of the 1×1 strips. Since the location of the 1-cell strip follows from the location of the other 9 strips, it can be ignored in the factorization. Therefore, the problem can be reformulated as follows: we need to arrange 6 unique 1×3 strips and 3 unique 1×2 strips on each board so that the colors of the board cells and the colors of the strip cells match. Let's try to solve this problem using Python.
Let us represent the stripes using a tuple of rows in any order, where the symbols of each row will denote the colors of the corresponding cells of the stripe ('w' or 'b').
# strips for the puzzle
strips = ('ww','wb','bb','www','wwb','wbw','wbb','bwb','bbb')Let's represent each field as a tuple of strings, each of which will denote one row of the field. In this case, the symbols of the strings will represent the colors of the corresponding cells.
# grids for the puzzle
grid01 = ('bwbww','bwbbb','wbwbw','bwwbw','bwwbb')
grid02 = ('bwbwb','bwbwb','wbwbw','wwbbb','wbbww')
grid03 = ('wwwbw','bbwww','bbbww','wwbbw','bbwbb')
grid04 = ('wwbbw','wbwbb','bwwwb','wwbbw','bbbwb')
grid05 = ('wwwwb','bbbbw','bbwbb','bwwbb','wwwwb')
grid06 = ('wbwwb','bwwbw','bbbbb','wwwbw','bwbww')
grid07 = ('wbwww','wwbbw','wbbbw','bbbbw','wbbww')
grid08 = ('wbbww','wwwbb','bwbww','bwbwb','bbwwb')
grid09 = ('bbbww','wwbww','wbbww','bwwwb','bbwbb')
grid10 = ('wwbbb','wbbbb','wbbwb','bwbww','bwwww')
grid11 = ('wwwww','bbbbb','wwbbw','wwbbb','bbbww')
grid12 = ('bbbbb','wwbwb','wwwwb','wwbwb','wwbwb')
grid13 = ('bwbwb','wwwbb','bwbwb','bwbbw','wwbwb')
grid14 = ('wbwwb','wbwbb','wwbbb','wwbbb','wwbbw')
grid15 = ('wwbbw','wwbww','bbbww','bbbww','bbwbw')
grid16 = ('wbwbw','wbwww','bbbbb','bwwww','bwbwb')
grid17 = ('wwwwb','wwwww','bbbbw','bbbwb','bwbbb')
grid18 = ('wbbww','bwwbb','bwwwb','bbbwb','wbwwb')
grid19 = ('bwwbw','wbwww','bwbwb','bwwbw','bbbbw')
grid20 = ('wbbwb','bbwbw','wwwwb','wbbbb','wwbwb')
grid21 = ('bbbwb','bbwbw','wbbww','bbwwb','wwbww')
grid22 = ('wwbbw','wbbbw','bwwwb','bwbbb','bwbww')
grid23 = ('wbwww','wwbwb','bbwww','wbwbb','bbbwb')
grid24 = ('bwwbb','wwwww','bwwww','bbbbb','wwbbb')
grid25 = ('wwwww','bbbww','bbbbw','bwbww','wwbbb')We will also collect all the fields together into one tuple.
# given grids together as a tuple
grids = (grid01,grid02,grid03,grid04,grid05,
grid06,grid07,grid08,grid09,grid10,
grid11,grid12,grid13,grid14,grid15,
grid16,grid17,grid18,grid19,grid20,
grid21,grid22,grid23,grid24,grid25)For clarity, we will convert the solution of each field into a simple scheme consisting of vertical bars, underscores, and spaces. In addition, when outputting, we will place several schemes on one horizontal level so that the result corresponds to the arrangement of fields in the task. We will provide a parameter that will indicate the number of solutions on one level during output, and set it to five.
# number of outlines of placings in one row for the output
outlines_per_row = 5The program will start working with the solve_grids function.
def solve_grids(grids, strips, outlines_per_row):
"""Function for solving grids for puzzle Black and White
from MUMS Puzzle Hunt 2010 competition."""
first_grid = grids[0]
num_rows = len(first_grid)
num_cols = len(first_grid[0])
# sorting strips according to length in decreasing order
# to make the problem easier
strips = tuple(sorted(strips,key = len,reverse = True))
outlines = ()
for grid_values in grids:
# represent the grid as a dictionary for search
grid = {}
for row in range(num_rows):
for col in range(num_cols):
grid[(col,row)] = grid_values[row][col]
# try to find placing with depth-first search
placing = depth_first_search(grid, num_cols, num_rows, strips,(), ())
if placing:
# form outline of a placing
outline = get_placing_outline(placing, num_cols, num_rows)
outlines += (outline,)
else:
return False
# combine outlines
output = get_output(outlines, outlines_per_row)
return outputIts input data are a tuple of fields, a tuple of stripes, and an output parameter. To decompose each field, the program will arrange the stripes on it one by one according to their order in the tuple; therefore, before starting the search, it makes sense to sort the stripes according to their length in descending order. This will result in the search considering fewer potential variants on the way to a solution, which will significantly simplify the task. For the search, it is convenient to represent each field as a dictionary in which the keys are tuples of two numbers denoting the column number and row number of the cell, and the values are single-character strings denoting the color of the given cell ('w' or 'b'). For each field in the tuple, the function forms such a representation and then runs a depth-first search on it. The found solution is then converted into a scheme, which will be added to the overall tuple. After this process is complete, the function arranges the schemes into levels and returns the result.
Let us now consider the depth-first search function.
def depth_first_search(grid, num_cols, num_rows, strips, occupied_cells, placing):
"""Function that perform depth-first search to place the strips on the grid."""
if strips == ():
# all strips are placed
return placing
else:
# current strip of search
current_strip = strips[0]
# strips for further search
next_strips = strips[1:]
# position is used for search, representation is used for answer
for (position,representation) in get_strip_positions(current_strip, num_cols, num_rows):
position_is_possible = True
# check that position is possible
for cell in position:
if position[cell] != grid[cell] or cell in occupied_cells:
position_is_possible = False
break
if position_is_possible:
next_occupied_cells = occupied_cells
for cell in position:
next_occupied_cells += (cell,)
next_placing = placing + (representation,)
final_placing = depth_first_search(grid, num_cols, num_rows, next_strips, next_occupied_cells, next_placing)
if final_placing:
return final_placing
return FalseThis function first checks if the strip tuple is empty. If it is, then all the stripes have been placed and the resulting arrangement is returned. Otherwise, the function attempts to place the first strip of the tuple on the board, and if successful, passes the tuple of the remaining strips to the next call. The possible strip positions are generated by the get_strip_positions function. This function returns a generator that will provide the positions as needed, with each position represented in two different ways, as a 2-tuple. The first representation is used for lookup: it is a dictionary where the keys are 2-tuples denoting the locations of the strip cells on the board, and the values are single-character strings denoting the colors of the strip cells ('w' or 'b'). The second representation will be used to form the answer to the problem, since it is more convenient for subsequent output of the solution. This representation is a 3-tuple: the first element denotes the lower-left cell of the strip at the given position, as a 2-tuple; the second element represents the strip orientation as a string ('horizontal' or 'vertical'); the third element represents the strip length as a number. The function uses the first representation to check that the strip cell colors match the field cell colors at the given position, and to make sure that the corresponding field cells are not occupied by other strips. If the position is possible, the function completes the tuple of occupied field cells, adds the second strip representation to the solution, and continues searching with the new data.
Let's now look at the get_strip_positions function.
def get_strip_positions(strip, num_cols, num_rows):
"""Function that generate possible positions for the given strip
according to the number of columns and rows in the grid."""
strip_len = len(strip)
# we should also consider reversed strip,
# if it is different from the original one
reversed_strip = strip[::-1]
if strip == reversed_strip:
patterns = (strip,)
else:
patterns = (strip, reversed_strip)
# generate horizontal placings of the strip
for row in range(num_rows):
for col in range(num_cols - strip_len + 1):
for pattern in patterns:
position = {}
current_col = col
for colour in pattern:
position[(current_col, row)] = colour
current_col += 1
yield (position, ((col,row),'horizontal',strip_len))
# generate vertical placings of the strip
for col in range(num_cols):
for row in range(num_rows - strip_len + 1):
for pattern in patterns:
position = {}
current_row = row
for colour in pattern:
position[(col, current_row)] = colour
current_row += 1
yield (position, ((col,row),'vertical',strip_len))First, it “turns” the strip 180 degrees and checks whether the result matches the original version. If it does not, then both layout options should be considered. First, the function forms all possible horizontal positions of the strip, considering the field rows in turn, then vertical ones, considering the field columns in turn.
Once a solution is found, the solve_grids function passes it to the get_placing_outline function to generate the grid layout for output.
def get_placing_outline(placing, num_cols, num_rows):
"""Function that creates outline of the placing for output
that consists of bars, underscores and spaces."""
cells_without_left_border = ()
cells_without_lower_border = ()
for strip in placing:
first_cell = strip[0]
col,row = first_cell[0],first_cell[1]
orientation = strip[1]
strip_len = strip[2]
if orientation == 'horizontal':
for strip_index in range(1, strip_len):
cells_without_left_border += ((col + strip_index, row),)
elif orientation == 'vertical':
for strip_index in range(1, strip_len):
cells_without_lower_border += ((col, row + strip_index),)
outline = []
# decremental loop for rows with one additional row for the upper border of the grid
for row in range(num_rows,-1,-1):
level=""
# loop for cols with one additional col for the right border of the grid
for col in range(num_cols+1):
cell = (col,row)
if row < num_rows and (col == 0 or col == num_cols or not cell in cells_without_left_border):
level += '|'
else:
level += ' '
if col < num_cols:
if row == 0 or row == num_rows or not cell in cells_without_lower_border:
level += '_'
else:
level += ' '
outline.append(level)
return outlineFirst, this function extracts from the solution all the cells in the field whose left side is not the boundary of any strip, and all the cells in the field whose bottom side is not the boundary of any strip. Then, using horizontal bars, underscores, and spaces, the function creates a solution diagram as a list of rows, each of which represents one level of the diagram. In this case, it is necessary to consider one additional row to display the upper boundary of the field, and one additional column to display the right boundary of the field.
The schema of each solution is added to a common tuple, which is then passed to the get_output function, which generates the final output.
def get_output(outlines, outlines_per_row):
"""Function that combines outlines to create output
with outlines_per_row outlines in one row."""
outlines_len = len(outlines)
output=""
# determine starting index for every row
for first_index in range(0, outlines_len, outlines_per_row):
last_index = min(first_index + outlines_per_row, outlines_len)
# add first outline to the row
one_row = outlines[first_index]
# add other outlines to the row
for current_outline in outlines[first_index+1:last_index]:
level_index = 0
for level in current_outline:
one_row[level_index] += ' ' + level
level_index += 1
for level in one_row:
output += level + '\n'
return outputThis function combines the decision schemes for each horizontal output level into a single list. Initially, each output level is simply the first scheme in that level. Subsequent schemes are added to the list level by level, with a space added. Once an output level is formed, it is converted to a string with newline characters added.
Now it remains to add commands to the program for decomposing the fields given in the task and outputting the schemes for their solution.
if __name__ == '__main__':
# solve the given grids for the puzzle
answer = solve_grids(grids, strips, outlines_per_row)
print(answer)The result of the program can be seen below.
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| | | |_ _| | |_ _|_ _| | |_ _ _| | |_ _ _| | | |_ _ _|_ _|
| | | | | | | | |_ _ _| |_|_ _ _| | |_ _ _|_| | | |_ _ _|_|
|_|_|_| |_| |_| | | | | |_ _ _|_|_| |_|_ _ _|_| | | | | | |
|_ _ _|_| | |_|_|_| | | |_ _|_ _ _| |_ _ _|_ _| |_|_| | | |
|_|_ _ _|_| |_ _ _|_|_| |_ _|_ _ _| |_ _|_ _ _| |_ _|_|_|_|
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
|_ _ _|_ _| | | |_ _ _| | | |_ _ _| | | |_ _ _| | |_ _ _| |
|_ _ _| | | | |_| |_ _| | |_|_ _ _| |_| |_ _ _| | |_ _ _|_|
| |_ _| | | |_| | | | | |_|_ _ _|_| | |_|_ _| | |_|_|_ _ _|
| | |_|_|_| | | |_| | | |_ _ _|_ _| |_|_ _ _| | |_ _|_ _ _|
|_|_|_ _ _| |_|_|_|_|_| |_ _ _|_ _| |_ _ _|_|_| |_ _ _|_ _|
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
|_ _ _|_ _| | |_|_ _ _| |_ _ _|_ _| |_ _ _| | | | |_ _ _|_|
|_ _ _|_| | | |_ _ _| | | | |_ _ _| | | | | | | | | |_ _ _|
| |_ _ _| | |_| | | | | |_|_|_| | | | |_|_|_|_| |_|_|_ _| |
| | |_ _|_| | | | |_|_| |_ _ _| | | |_|_ _ _|_| | |_ _ _| |
|_|_|_ _ _| |_|_|_|_ _| |_ _ _|_|_| |_ _ _|_ _| |_|_ _ _|_|
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| |_ _ _| | |_ _ _|_| | |_ _ _|_ _| |_ _ _| | | |_ _|_ _ _|
|_| |_ _|_| |_ _ _| | | | |_|_ _ _| | | |_|_|_| | |_ _ _| |
| | |_ _ _| | |_ _| |_| | |_ _ _| | | | |_ _ _| | |_ _ _|_|
| |_|_ _ _| | |_ _|_| | |_|_ _ _|_| |_|_|_ _ _| |_|_|_ _ _|
|_|_ _ _|_| |_|_ _ _|_| |_ _ _|_ _| |_ _|_ _ _| |_ _ _|_ _|
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
|_ _ _| | | | | |_| | | |_ _ _| | | | | |_ _ _| |_|_ _ _| |
|_ _| | |_| | | | | | | |_| | | | | |_| |_ _| | |_ _ _| | |
| | | |_| | |_|_| |_|_| | |_|_|_|_| | |_|_ _| | |_ _ _| |_|
| | |_|_|_| |_ _|_| | | | | |_ _ _| | |_ _ _|_| | |_ _|_| |
|_|_|_ _ _| |_ _ _|_|_| |_|_|_ _ _| |_|_|_ _ _| |_|_ _ _|_|The resulting solution schemes now need to be superimposed on the original images.
Note the single-cell strips for each solution. The letters in these cells, taken together, spell out the message: “ONE MORE GRID. USE BLACK STRIPS.” Each single-cell strip occupies a unique position. Thus, from these cells, one more 5×5 grid can be created without gaps or overlaps.
Let's create a representation of this field.
# final grid for the puzzle
final_grid = ('bwwww','bbwbb','bbbww','wbwbb','wwbbw')Let's add commands to the program to decompose it and output the solution diagram.
if __name__ == '__main__':
# solve the final grid for the puzzle
answer = solve_grids((final_grid,), strips, outlines_per_row)
print(answer)The result of their implementation can be seen below.
_ _ _ _ _
|_ _|_ _ _|
|_ _ _|_ _|
| |_|_ _ _|
| |_ _ _| |
|_|_ _ _|_|Next, we will superimpose the diagram onto the original image (the left border of the cell with the letter T is wrong, the letters B and L should be swapped).
According to the hint, you need to pay attention to the stripes consisting only of black cells. The letters inside these stripes form the word DOMINO. It is answer on assignment.
The full program code can be found Here.
