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

«Разложите каждую из диаграмм ниже на полоски размером 1×1, 1×2 или 1×3 таким образом, чтобы ни одна сетка не содержала полосок с одинаковым черно‑белым паттерном, включая повороты».

Головоломка представляет собой 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."""
    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

Ее входными данными являются: кортеж полей, кортеж полосок, а также параметр для вывода. Для разложения каждого поля программа будет по очереди располагать на нем полоски в соответствии с их порядком в кортеже; поэтому перед началом поиска имеет смысл отсортировать полоски в соответствии с их длинной в убывающем порядке. В результате этого поиск будет рассматривать меньше потенциальных вариантов на пути к решению, что значительно упростит задачу. Для поиска будет удобно представить каждое поле в виде словаря, в котором ключами будут кортежи из двух чисел, обозначающие номер столбца и номер строки клетки, а значениями — строки из одного символа, обозначающие цвет данной клетки ('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 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

Сначала эта функция проверяет, не является ли кортеж полосок пустым. Если это так, то все полоски уже размещены, и остается вернуть получившееся расположение. В противном случае функция пытается разместить на поле первую полоску из кортежа, а затем, при удачном исходе, передает кортеж из оставшихся полосок в следующий вызов. Возможные позиции полоски генерируются с помощью функции 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."""
    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))

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

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

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 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."""
    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

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

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

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.

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

# 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. Оно и является ответом на задание.

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