Решение головоломки Black and White.

Black and White - одна из интересных головоломок игры Puzzle Hunt Мельбурнского Университета 2010 года. По сюжету игры вы преследуете загадочного участника ТВ-шоу в надежде раскрыть его личность. Вам удается пробраться сначала на студию, а затем и в его гримерку. Там в его одежде вы находите клочок бумаги. Одну из его сторон занимает сообщение, другую - головоломка и набор инструкций к ней. 

«Разложите каждую из диаграмм ниже на полоски размером 1x1, 1x2 или 1x3 таким образом, чтобы ни одна сетка не содержала полосок с одинаковым черно-белым паттерном, включая повороты».

Головоломка представляет собой 25 квадратных полей, расположенных в 5 рядов и 5 столбцов. В свою очередь, каждое поле разделено на 25 клеток горизонтальными и вертикальными линиями. Клетки имеют белый или черный фон, и каждая из них содержит по одной букве. 

Сначала определим, какие полоски мы можем использовать для решения этой задачи. Существует 6 различных полосок размером 1х3 (WWW, WWB, WBW, WBB, BWB и BBB), 3 различных полоски размером 1х2 (WW, WB и BB) и 2 различных полоски размером 1х1 (W и B). В сумме все эти полоски содержат 26 клеток. Это означает, что для разложения каждого поля придется использовать все полоски размером 1х3, все полоски размером 1х2 и только одну из полосок размером 1х1. Так как расположение полоски из 1 клетки вытекает из расположения остальных 9 полосок, то ее можно не учитывать при разложении. Стало быть, задачу можно переформулировать следующим образом: необходимо расположить на каждом поле 6 уникальных полосок размером 1х3 и 3 уникальных полоски размером 1х2 таким образом, чтобы цвета клеток поля и цвета клеток полосок совпадали. Попробуем решить эту задачу с помощью Python.

Представим полоски с помощью кортежа из строк в произвольном порядке, где символы каждой строки будут обозначать цвета соответствующих клеток полоски ('w' или 'b').

# strips for the puzzle            
strips = ('ww','wb','bb','www','wwb','wbw','wbb','bwb','bbb')

Представим каждое поле как кортеж из строк, каждая из  которых будет обозначать одну строку поля. При этом символы строк будут представлять цвета соответствующих клеток.

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

Все поля также соберем вместе в один кортеж.

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

Для наглядности мы будем  конвертировать решение каждого поля в простенькую схему, состоящую из вертикальных черт, нижних подчеркиваний и пробелов. Помимо этого, при выводе мы будем располагать по несколько схем на одном горизонтальном уровне, чтобы результат соответствовал расположению полей в задании. Предусмотрим параметр, который будет обозначать число решений на одном уровне при выводе, и установим его равным пяти.

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

Работа программы будет начинаться с функции solve_grids. 

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

Ее входными данными являются: кортеж полей, кортеж полосок, а также параметр для вывода. Для разложения каждого поля программа будет по очереди располагать на нем полоски в соответствии с их порядком в кортеже; поэтому перед началом поиска имеет смысл отсортировать полоски в соответствии с их длинной в убывающем порядке. В результате этого поиск будет рассматривать меньше потенциальных вариантов на пути к решению, что значительно упростит задачу. Для поиска будет удобно представить каждое поле в виде словаря, в котором ключами будут кортежи из двух чисел, обозначающие номер столбца и номер строки клетки, а значениями - строки из одного символа, обозначающие цвет данной клетки ('w' или 'b'). Для каждого поля из кортежа функция формирует такое представление, а затем запускает с ним поиск в глубину. Найденное решение затем преобразуется в схему, которая будет добавляться в общий кортеж. После завершения этого процесса функция располагает схемы по уровням и возвращает результат.

Рассмотрим теперь функцию поиска в глубину. 

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

Сначала эта функция сравнивает количество полосок и количество уже размещенных полосок. Если они равны, то задача является решенной, и остается вернуть получившееся расположение. В противном случае функция определяет полоску, которую необходимо разместить, а затем генерирует ее возможные позиции на поле с помощью функции get_strip_positions. Каждая из этих позиций будет представлена двумя различными способами с помощью кортежа из двух элементов. Первое представление используется для поиска: это словарь, где ключами служат кортежи из  двух чисел, обозначающие расположение клеток полоски на поле, а значениями - строки из одного символа, обозначающие цвета клеток полоски ('w' или 'b'). Второе представление будет использоваться, чтобы сформировать ответ на задачу, так как оно более удобно для последующего вывода решения. Это представление является кортежем из 3 элементов: первый элемент обозначает левую нижнюю клетку полоски при данной позиции в виде кортежа из 2 чисел; второй элемент представляет ориентацию полоски в виде строки ('horizontal' или 'vertical'); третий элемент обозначает длину полоски в виде числа. Функция использует первое представление, чтобы проверить, что цвета клеток полоски совпадают с цветами клеток поля при данной позиции, а также удостовериться, что соответствующие клетки поля не заняты другими полосками. Если позиция возможна, то функция дополняет кортеж занятых клеток поля, добавляет второе представление полоски к решению и продолжает поиск.

Рассмотрим теперь функцию get_strip_positions. 

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

Первым делом она «разворачивает» полоску на 180 градусов и проверяет, совпадает ли результат с первоначальным вариантом. Если это не так, то дальше следует рассматривать оба варианта расположения. Сначала функция формирует все возможные горизонтальные позиции полоски, рассматривая по очереди строки поля, затем - вертикальные, рассматривая по очереди столбцы поля.

После того, как решение найдено, функция solve_grids передает его в функцию get_placing_outline, чтобы сформировать схему расположения полосок для вывода.

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

Сначала эта функция извлекает из решения все клетки поля, левая сторона которых не является границей какой-либо полоски, и все клетки поля, нижняя сторона которых не является границей какой-либо полоски. Затем функция с помощью горизонтальных черт, нижних подчеркиваний и пробелов создает схему решения в виде списка из строк, каждая из которых представляет собой один уровень схемы. При этом необходимо рассмотреть одну дополнительную строку, чтобы отобразить верхнюю границу поля, и один дополнительный столбец, чтобы отобразить правую границу поля.

Схема каждого решения добавляется в общий кортеж, который затем передается в функцию get_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

Эта функция объединяет схемы решений для каждого горизонтального уровня вывода в один список. Изначально каждый уровень вывода представляет собой просто первую схему в данном уровне. Последующие схемы добавляются к списку уровень за уровнем с добавлением пробелом. После того, как уровень вывода сформирован, он преобразуется в строку с добавлением символов новой строки.

Теперь остается добавить к программе команды для разложения полей, данных в задании, и вывода схем их решения. 

if __name__ == '__main__':
    # solve the given grids for the puzzle
    answer = solve_grids(grids, strips, outlines_per_row)
    print(answer)

Результат работы программы можно видеть ниже.

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

Полученные схемы решений теперь необходимо наложить на исходные изображения.

Внимание следует обратить на полоски из одной клетки для каждого решения. Буквы в этих клетках, взятые вместе, складываются в сообщение: "ONE MORE GRID. USE BLACK STRIPS" (ЕЩЕ ОДНО ПОЛЕ. ИСПОЛЬЗУЙТЕ ЧЕРНЫЕ ПОЛОСКИ). При этом каждая полоска из 1 клетки занимает уникальную позицию. Таким образом, из этих клеток можно без пробелов и наложений составить еще одно поле размером 5х5.

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

Создадим представление этого поля.

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

Добавим к  программе команды, чтобы разложить его и вывести схему решения.

if __name__ == '__main__':
    # solve the final grid for the puzzle
    answer = solve_grids((final_grid,), strips, outlines_per_row)
    print(answer)

Результат их выполнения можно видеть ниже.

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

Далее наложим схему на исходное изображение (левая граница у клетки с буквой T ошибочна, буквы B и L следует поменять местами).

В соответствии с подсказкой внимание необходимо обратить на полоски, состоящие только из черных клеток. Буквы внутри этих полосок складываются в слово DOMINO. Оно и является ответом на задание.

Код программы целиком можно найти здесь.

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