Solution to the puzzle Black and White.

Black and White - is one of the interesting puzzles of the Melbourne University Puzzle Hunt 2010 competition. According to the plot of the game you are pursuing a mysterious participant of a TV show trying to reveal his identity. You manage to get into the studio 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 conundrum and a set of instructions for it.

«Decompose each of the diagrams below into 1x1, 1x2 or 1x3 strips in such a way that no grid contains strips with the same black and white pattern, even after rotation.»

The puzzle consists of 25 square grids arranged in 5 rows and 5 columns. Each of these grids 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 1x3 strips (WWW, WWB, WBW, WBB, BWB and BBB), 3 different 1x2 strips (WW, WB and BB) and 2 different 1x1 strips (W and B). In total, these strips contain 26 cells. Thus, to decompose each grid we will have to use all the 1x3 strips, all the 1x2 strips and only one of the 1x1 strips. Since the location of a 1x1 strip follows from the location of the remaining 9 strips, it can be ignored when decomposing. Therefore, the problem can be reformulated as follows: we need to place 6 unique 1x3 strips and 3 unique 1x2 strips on each grid so, that the colors of the grid cells and the colors of the strip cells match. Let's try to solve this problem using Python.

Let's represent the strips using a tuple of rows in arbitrary order, where the symbols of each row will denote 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 grid as a tuple of strings, each of which will denote one row of the grid. 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 grids 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 for each grid into a simple outline consisting of vertical bars, underscores and spaces. In addition, to create output we will place several outlines on one horizontal level, so that the result will match the arrangement of the grids in the task. Let us denote the parameter that will indicate the number of outlines at one horizontal level for output and set it equal to five.

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

The program will begin 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."""
    num_rows = len(grids[0])
    num_cols = len(grids[0][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 a 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 tuple of grids, a tuple of strips and also a parameter for output. To decompose each grid the program will place the strips on it one by one according to their order in the tuple; therefore, before starting the search it makes sense to sort the strips 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 grid as a dictionary, in which the keys are tuples of two integers denoting the column number and row number of the cells and the values are single-character strings denoting the colors of the corresponding cells ('w' or 'b'). For each grid in the tuple the function forms such a representation and then runs a depth-first search with it. The found solution is then converted into an outline, which will be added to the overall tuple. After this process is complete, the function arranges the outlines into horizontal 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 len(strips) == len(placing):
        # all strips are placed
        return placing
    # current strip of search
    current_strip = strips[len(placing)]
    # 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, strips,
                                               next_occupied_cells, next_placing)
            if final_placing:
                return final_placing
    return False

First, this function compares the number of strips and the number of strips already placed. If they are equal, then the problem is solved and it remains to return the resulting placing. Otherwise, the function determines the strip to be placed and then generates its possible positions on the grid using the get_strip_positions function. Each of these positions will be represented in two different ways by a tuple of two elements. The first representation is used for search: it is a dictionary where the keys are tuples of two integers denoting the locations of the strip cells on the grid, 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 tuple of 3 elements: the first element denotes the lower-left cell of the strip for the given position as a tuple of two integers; the second element represents the strip orientation as a string ('horizontal' or 'vertical'); the third element represents the strip length as an integer. The function uses the first representation to check, that the colors of the strip cells match the colors of the grid cells at the given position and to make sure, that the corresponding grid cells are not occupied by other strips. If the position is possible, then the function extend the tuple of occupied grid cells, adds the second strip representation to the solution and continues the search.

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."""
    # 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 - len(strip) + 1):
            for pattern in patterns:
                position = {}
                for i in range(len(strip)):
                    position[(col + i, row)] = pattern[i]
                yield (position, ((col,row),'horizontal',len(strip)))
    # generate vertical placings of the strip 
    for col in range(num_cols):
        for row in range(num_rows - len(strip) + 1):
            for pattern in patterns:
                position = {}
                for i in range(len(strip)):
                    position[(col, row + i)] = pattern[i]
                yield (position, ((col,row),'vertical',len(strip)))

In the beginning it "turns" the strip 180 degrees and checks, whether the result matches the original one. If it does not, then both patterns should be considered. First, the function forms all possible horizontal positions of the strip, considering the rows of the grid in turn, then vertical ones, considering the columns of the gird in turn.

Once a solution is found, the solve_grids function passes it to the get_placing_outline function to create the grid outline for output.

def get_placing_outline(placing, num_cols, num_rows):
    """Function that creates outline of a placing for output
       that consists of bars, underscores and spaces."""
    cells_without_left_border = ()
    cells_without_lower_border = ()
    for strip in placing:
        col, row = strip[0][0], strip[0][1]
        orientation = strip[1]
        strip_len = strip[2]
        if orientation == 'horizontal':
            for i in range(1, strip_len):
                cells_without_left_border += ((col + i, row),)
        elif orientation == 'vertical':
            for i in range(1, strip_len):
                cells_without_lower_border += ((col, row + i),)
    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 or cell in cells_without_left_border:
                level += ' '
            else:
                level += '|'
            if col < num_cols:
                if cell in cells_without_lower_border:
                    level += ' '
                else:
                    level += '_'
        outline.append(level)
    return outline

First, this function extracts from the solution all the cells in the grid, whose left side is not the boundary of any strip, and all the cells in the grid, whose bottom side is not the boundary of any strip. Then, using horizontal bars, underscores and spaces, the function creates a solution outline as a list of rows, each of which represents one level of the outline. To achieve that, it is necessary to consider one additional row to display the upper boundary of the grid and one additional column to display the right boundary of the grid.

The outline of each solution is added to the tuple, which is then passed to the get_output function that 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."""
    output = ''
    # determine starting index for every row
    for first_index in range(0, len(outlines), outlines_per_row):
        last_index = min(first_index + outlines_per_row, len(outlines))
        # add first outline to the row
        one_row = outlines[first_index]
        # add other outlines to the row
        for i in range(first_index + 1, last_index):
            current_outline = outlines[i]
            for level_index in range(len(current_outline)):
                one_row[level_index] += ' ' + current_outline[level_index]
        for level in one_row:
            output += level + '\n'
    return output

This function combines the outlines for each horizontal level of the output into a single list. Initially each output level is simply the first outline in that level. Subsequent outlines 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 grids given in the task and print the outlines 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 execution can be seen below.

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

The resulting solution outlines now need to be superimposed on the original images.

Pay attention to the single-cell strips for each solution. The letters in these cells taken together form the message: "ONE MORE GRID. USE BLACK STRIPS". Moreover, each strip of 1 cell occupies a unique position of a grid. Thus, from these cells we can create another 5x5 grid without gaps or overlaps.

S U R A B
I C K D O
M I S E G
N S R T E
O P E R L

Let's create a representation of this grid.

# final grid for the puzzle
final_grid = ('bwwww','bbwbb','bbbww','wbwbb','wwbbw')

Let's add commands to the program to decompose it and print the solution outline.

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 superimpose the outline 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 we need to pay attention to the strips consisting only of black cells. The letters inside these strips form the word DOMINO. This is the answer to the puzzle.

The full program code can be found here.

Comments

Post a Comment

Popular posts from this blog

Solution to the puzzle Sleuth.

Image
Sleuth  is one of the tasks of the Melbourne University  Puzzle Hunt  2005 competition, which was compiled by the founder of WikiLeaks, and the likely organizer of the Cicada 3301 community, Julian Assange. This is an interesting and original puzzle. At the same time, it is quite voluminous, and its peculiarity is a large amount of irrelevant information.  According to the plot of the game, you find yourself inside a mysterious dark castle, where you become a witness of a strange conversation. 7 people take part in the discussion, and they all speak different languages. One of them is the host; he speaks english. The other 6 people are his guests; they speak Chinese, Dutch, French, German, Italian and Japanese. Apparently, a terrible crime has occurred in the castle, and the host suspects one of the guests. Together they try to unravel this case… It's easy to see a reference to the board game Cluedo. This exciting game was invented in the middle of the twentie...
Read more

Cicada 3301 - solution.

Image
A few years ago a secret society appeared on the internet. Its activity takes place on the pages of the dark web, the messages of its members are guarded by modern programs for encryption, and it only takes into its ranks those who are able to pass the mysterious game, taking place on the network. One such game was held in 2012, 2013 and 2014. Each time, anyone with internet access could try their hand. The chain of riddles began from resources such as 4chan, Reddit and Twitter and stretched further, gradually taking applicants into the depths of the network. From one riddle to another they had to interpret the mysterious messages of the organizers; look for hidden messages in literary, artistic and musical works; solve ciphers, ancient and modern. Several times the applicants came across telephone numbers, and further instructions were given by a voice on the other end of the line. However, the most impressive were the sheets with clues, that appeared exactly at the appointed time o...
Read more

Solution to the puzzle Cat Walk.

Image
Cat Walk is one of the interesting puzzles of the Melbourne University Puzzle Hunt 2012 competition. This task was part of the second act of the game and was preceded by a short narrative that continued the plot. In accordance with it you receive the parcel from your strange companion: a small flash drive is wrapped inside what appears to be a torn page from a children’s puzzle book. You stare long and hard at the puzzle before asking your companion if you had the right answer. He looks back in amazement, quickly plugs the USB drive into his laptop and then happily reports: “This is wonderful! You’ve figured out the password - this is everything that we needed...” As it turned out, the flash drive contained extremely important information, and the solution to the “children's puzzle” was the password to obtain it… The puzzle itself was below. It was a rectangular maze with colored gates between its parts: gray, red, blue and green. At the bottom of the maze, near the two entrances...
Read more