Solving the puzzle from the university quest using Python

Black and White is one of the most interesting puzzles in the University of Melbourne’s 2010 Puzzle Hunt. According to the plot of the game, you are chasing a mysterious participant of the TV show, hoping to reveal his identity. You manage to get into the studio first, and then into the dressing room. There in his clothes you find a piece of paper. One of its sides is occupied by a message, the other by a puzzle and a set of instructions for it.

“Arrange each of the charts below into 1×1, 1×2, or 1×3 strips in such a way that no grid contains strips with the same black and white pattern, including turns.”

The puzzle has 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 cell 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, all these strips contain 26 cells. This means that you will have to use all 1×3 strips, all 1×2 strips, and only one of the 1×1 strips to decompose each field. Since the location of the strip from 1 cell follows from the location of the remaining 9 strips, it can be ignored in the decomposition. So, the task can be reformulated as follows: it is necessary to place on each field 6 unique strips of size 1×3 and 3 unique strips of size 1×2 in such a way that the colors of the cells of the field and the colors of the cells of the strips coincide. Let’s try to solve this task using Python.

Let’s represent the strips using a tuple of rows in random order, where the symbols of each row will indicate the colors of the corresponding cells of the strip (‘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 line of the field. At the same time, the line symbols 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 lines, underlines and spaces. In addition, when outputting, we will arrange several schemes on one horizontal level so that the result corresponds to the location of the fields in the task. Let’s provide a parameter that will indicate the number of solutions at the same level when outputting, and set it to five.

# number of outlines of placings in one row for the output
outlines_per_row = 5

The program starts 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 output

Its inputs are a field tuple, a strip tuple, and an output parameter. To decompose each field, the program will place strips on it in turn according to their order in the tuple; therefore, before starting the search, it makes sense to sort the bars according to their length in descending order. As a result, the search will consider fewer potential options on the way to a solution, which will greatly simplify the task. For searching, it will be convenient to imagine each field in the form of a dictionary, in which the keys will be tuples of two numbers denoting the column number and row number of the cell, and the values will be strings of one character denoting the color of this cell (w or b). For each field from the tuple, the function forms such a representation, and then runs a depth-first search with it. The found solution is then transformed into a scheme that will be added to the common tuple. After this process is completed, the function has the schemes by 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 False

First, this function checks that the strips tuple is not empty. If this is the case, then all the bars are already placed, and it remains to return the resulting arrangement. Otherwise, the function tries to place the first strip from the tuple on the field, and then, if successful, passes the tuple from the remaining strips to the next call. Possible strip positions are generated using the get_strip_positions function. This function returns a generator that will provide positions as needed; while each of them will be represented in two different ways using a tuple of two elements. The first representation is used for lookups: it’s a dictionary, where the keys are tuples of two numbers denoting the location of the strip cells on the field, and the values are strings of one character denoting the colors of the strip cells (‘w’ or ‘b’). The second representation will be used to form the answer to the task, because it is more convenient for further decision. This representation is a tuple of three elements: the first element denotes the lower left cell of the strip at this position as a tuple of 2 numbers; the second element represents the orientation of the strip in the form of a line (‘horizontal’ or ‘vertical’); the third element represents the length of the strip as a number. The function uses the first representation to check that the colors of the strip cells match the colors of the field cells 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 cells of the field, adds a second representation of the strip to the solution, and continues the search with new data.

Consider 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 of all, it “unfolds” the strip by 180 degrees and checks whether the result coincides with the initial version. If this is not the case, then both location options should be considered. First, the function forms all possible horizontal positions of the strip, considering one by one the rows of the field, then vertical, considering one by one the columns of the field.

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

First, this function extracts from the solution all field cells whose left side is not the boundary of any strip, and all field cells whose bottom side is not the boundary of any strip. The function then uses horizontal lines, underscores, and spaces to create a solution diagram in the form of a list of rows, each of which represents one level of the diagram. In doing so, one additional row must be considered to display the top border of the field, and one additional column to display the right border of the field.

The outline of each solution is added to a common tuple, which is then passed to the get_output function, which produces 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 output

This function combines the decision schemes of each horizontal output level into a single list. Initially, each level of output is simply the first circuit in that level. The following schemes are added to the list by level with a space added. After the 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, data in the task and outputting their solution schemes.

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 obtained decision schemes must now be superimposed on the source images.

Notice the bars from one cell for each solution. The letters in these cells, taken together, form the message: “ONE MORE GRID. USE BLACK STRIPS” (ANOTHER FIELD. USE BLACK STRIPS). At the same time, each strip from one cell occupies a unique position. Thus, one more field of 5×5 size can be made from these cells without spaces and overlays.

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 display 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 execution can be seen below.

 _ _ _ _ _ 
|_ _|_ _ _|
|_ _ _|_ _|
| |_|_ _ _|
| |_ _ _| |
|_|_ _ _|_|

Next, we will apply the scheme to 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, attention must be paid to the strips consisting only of black cells. The letters inside these strips form the word DOMINO. It is the answer to the task.

The program code can be found here.

All about information technology’s blog

Solving the puzzle from the university quest using Python