«Треки» - одна из интересных головоломок ежегодного квеста Puzzle Hunt Мельбурнского Университета.

Эта головоломка представляет собой два поля одинакового размера, разделенные на клетки горизонтальными и вертикальными линиями. Таким образом, каждое поле состоит из 6 рядов и 16 столбцов. Помимо этого, оба поля вертикально разделены посередине на две равные части.

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

Нижнее поле содержит большое число цифр от 1 до 9, которые довольно хаотично расставлены в некоторых его клетках.

Суть верхнего поля является достаточно очевидной: необходимо построить путь от клетки start до клетки finish, а цифры для столбцов и строк указывают на то, сколько раз требуемый путь должен проходить через данный столбец или данную строку.

Однако значение нижнего поля уже не столь тривиально. С помощью пути из верхнего поля из нижнего поля можно извлечь сообщение, которое также состоит из 6 строк и 16 столбцов, следующим образом. Если через какую-либо клетку нижнего поля, содержащую цифру, проходит путь из верхнего поля, то соответствующее место сообщения должна также занимать эта цифра. В противном случае это место следует оставить пустым. Ниже можно видеть полученное таким образом сообщение.

Данное сообщение необходимо интерпретировать как гитарные табы и сыграть его на этом музыкальном инструменте.

В результате можно услышать начало знаменитого трека Stairway to Heaven группы Led Zeppelin. Таким образом, ответом на задание является STAIRWAY TO HEAVEN.

Попробуем решить этапы этой головоломки (за исключением игры на гитаре) с помощью Python.

Начнем с поиска пути для верхнего поля. Входными данными для этой задачи являются: число столбцов в левой половине поля; 3 кортежа, которые представляют собой ограничения для столбцов, строк в левой части поля и строк в правой части поля соответственно; кортеж из 2 элементов, обозначающий клетку start, и кортеж из 2 элементов, обозначающий клетку finish.

# number of cols in the left part of the grid
cols_in_left_rows = 8

#constraints for cols of the grid
cols_constr =(3,3,2,1,4,3,2,3,6,3,4,3,5,2,2,3)

#constraints for rows in the left part of the grid
left_rows_constr = (1,1,4,5,6,4)

#constraints for rows in the right part of the grid
right_rows_constr = (5,2,2,7,6,6)

# start cell
start = (0,0)

# finish cell
finish = (15,5)

Сразу определим две вспомогательные функции, которые потребуются нам в дальнейшем.

def satisfied(constr):
    for value in constr:
        if value != 0:
            return False
    return True

В функцию satisfied мы будем передавать кортеж ограничений для столбцов или строк, чтобы определить, являются ли они решенными. Если все значения кортежа равны нулю, то функция вернет True. В противном случае функция вернет False.

def update_constr(constr, index):
    updated_value = constr[index] - 1
    updated_constr = constr[:index] + (updated_value,) + constr[index+1:]
    return updated_constr

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

Все входные данные мы передаем в функцию search.

def search(start, finish, cols_in_left_rows, cols_constr, left_rows_constr, right_rows_constr):
    # compute number of cols and rows in the grid
    num_cols, num_rows = len(cols_constr), len(left_rows_constr)
    start_col, start_row = start[0], start[1]
    # set active and inactive rows constraints for the start cell
    if start_col < cols_in_left_rows:
        active_rows_constr = left_rows_constr
        inactive_rows_constr = right_rows_constr
    else:
        active_rows_constr = right_rows_constr
        inactive_rows_constr = left_rows_constr
    # update constraints for the start cell
    updated_cols_constr = update_constr(cols_constr, start_col)
    updated_active_rows_constr = update_constr(active_rows_constr, start_row)
    path = depth_first_search(start, finish, num_cols, num_rows, cols_in_left_rows,
                              updated_cols_constr, updated_active_rows_constr, inactive_rows_constr, ())
    return path

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

def depth_first_search(current_cell, finish, num_cols, num_rows, cols_in_left_rows, 
                       cols_constr, active_rows_constr, inactive_rows_constr, current_path):
    current_path += (current_cell,)
    # if current cell is a finish cell and constraints satisfied, than path is found;
    # it is sufficient to check only constraints for cols, because if they are satisfied, than constraints for rows are also satisfied
    if current_cell == finish and satisfied(cols_constr):
        return current_path
    else:
        # find adjacent cells for the current cell with corresponding constraints
        adjacent_cells_with_constr = find_adjacent_cells_with_constr(current_cell, finish, num_cols, num_rows, cols_in_left_rows,
                                                                     cols_constr, active_rows_constr, inactive_rows_constr)
        for (adjacent_cell, next_cols_constr, next_active_rows_constr, next_inactive_rows_constr) in adjacent_cells_with_constr:
            # we assume, that path is acyclic
            if adjacent_cell not in current_path:
                path = depth_first_search(adjacent_cell, finish, num_cols, num_rows, cols_in_left_rows,
                                          next_cols_constr, next_active_rows_constr, next_inactive_rows_constr, current_path)
                if path != False:
                    return path
    return False

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

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

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

В противном случае функция вернет False.

Далее рассмотрим функцию find_adjacent_cells_with_constr.

def find_adjacent_cells_with_constr(cell, finish, num_cols, num_rows, cols_in_left_rows,
                                    cols_constr, active_rows_constr, inactive_rows_constr):
    cell_col, cell_row = cell[0], cell[1]
    adjacent_cells_with_constr = ()
    for direction in ('horizontal','vertical'):
        for move in (+1,-1):
            active_rows_constr_for_move = active_rows_constr
            inactive_rows_constr_for_move = inactive_rows_constr
            if direction == 'horizontal':
                next_col = cell_col + move
                #next col is inside grid
                if next_col >= 0 and next_col < num_cols:
                    next_row = cell_row
                else:
                    continue
                # we move from the left part of the grid to the right, or from right to the left;
                # so we should swap active and inactive constraints for rows
                if (cell_col == cols_in_left_rows - 1 and move == +1) or (cell_col == cols_in_left_rows and move == -1):
                    active_rows_constr_for_move, inactive_rows_constr_for_move = inactive_rows_constr_for_move, active_rows_constr_for_move                    
            elif direction == 'vertical':
                next_row = cell_row + move
                # next row is inside grid
                if next_row >=0 and next_row < num_rows:
                    next_col = cell_col
                else:
                    continue
            # extract values of constraints for the next col and next row
            next_col_value = cols_constr[next_col]
            next_row_value = active_rows_constr_for_move[next_row]
            # check that constraints
            if next_col_value > 0 and next_row_value > 0:

                # if value of constraints for the next col will be zero after update,
                # and there is some col on the direction, opposite to the finish cell from the next col, with non-zero value of constraints,
                # than this path can't led to solution and should be abandoned
                if next_col_value == 1:
                    finish_col = finish[0]
                    if (next_col <= finish_col and not satisfied(cols_constr[:next_col]) 
                        or 
                       (next_col >= finish_col and not satisfied(cols_constr[next_col+1:]))):
                        continue

                # if value of active constraints for the next row will be zero after update,
                # and value of inactive constraints for that row is also equal to zero,
                # and there is some row on the direction, opposite to the finish cell from the next row, with non-zero value of active or inactive constraints,
                # than this path can't led to solution and should be abandoned
                if next_row_value == 1 and inactive_rows_constr_for_move[next_row] == 0:
                    finish_row = finish[1]
                    if ((next_row <= finish_row and
                        (not satisfied(active_rows_constr_for_move[:next_row]) or not satisfied(inactive_rows_constr_for_move[:next_row])))
                        or
                        (next_row >= finish_row and
                        (not satisfied(active_rows_constr_for_move[next_row+1:]) or not satisfied(inactive_rows_constr_for_move[next_row+1:])))):
                        continue
                    
                adjacent_cell = (next_col, next_row)
                updated_cols_constr = update_constr(cols_constr,next_col)
                updated_active_rows_constr_for_move = update_constr(active_rows_constr_for_move, next_row)
                adjacent_cells_with_constr += ((adjacent_cell, updated_cols_constr, updated_active_rows_constr_for_move, inactive_rows_constr_for_move),)
    return adjacent_cells_with_constr

Эта функция рассматривает 2 направления движения (горизонтальное и вертикальное) и 2 варианта перемещения (+1 и -1). Для горизонтального передвижения функция проверят, является ли соответствующий столбец частью поля. Для вертикального передвижения функция проверят, является ли соответствующая строка частью поля. Для горизонтального передвижения функция дополнительно проверят, не перемещаемся ли мы из одной части поля в другую. Если это так, то необходимо поменять местами активные и неактивные ограничения для строк. После этого необходимо проверить, позволяют ли ограничения для смежной клетки переместиться в нее (ограничения для ее строки и столбца должны быть больше нуля).

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

Рассмотрим сначала столбцы. Допустим, после перемещения в некоторую смежную клетку, значение ограничений для ее столбца станет равным нулю. Обозначим индекс столбца этой смежной клетки как N, а индекс столбца финишной клетки - как F. Если N <= F и существует столбец с индексом K, где K < N, ограничения для которого не являются решенными, то данный путь не может вести к решению задачи. Аналогично, если N >= F и существует столбец с индексом K, где K > N, ограничения для которого не являются решенными, то данный путь не может вести к решению задачи.

Для строк имеем похожую ситуацию. Допустим, после перемещения в некоторую смежную клетку, значение активных ограничений для ее строки станет равным нулю. Помимо этого, предположим, что значение неактивных ограничений для данной строки также равно нулю. Обозначим индекс строки этой смежной клетки как N, а индекс строки финишной клетки - как F. Если N <= F и существует строка с индексом K, где K < N, активные или неактивные ограничения для которой не являются решенными, то данный путь не может вести к решению задачи. Аналогично, если N >= F и существует строка с индексом K, где K > N, активные или неактивные ограничения для которой не являются решенными, то данный путь не может вести к решению задачи.

Мы не будем допускать все эти бесперспективные смежные клетки до дальнейшего поиска.

После этого остается обновить ограничения для столбцов и активные ограничения для строк для каждой перспективной смежной клетки.

Теперь можно запустить поиск следующей командой:

path = search(start, finish, cols_in_left_rows, cols_constr, left_rows_constr, right_rows_constr)

В результате мы получим следующий путь:

((0, 0), (0, 1), (0, 2), (1, 2), (1, 3), (1, 4), (2, 4), (2, 5), (3, 5), (4, 5), (4, 4), (4, 3), (4, 2), (5, 2), (5, 3), (5, 4), (6, 4), (6, 3), (7, 3), (7, 4), (7, 5), (8, 5), (8, 4), (9, 4), (9, 3), (8, 3), (8, 2), (8, 1), (8, 0), (9, 0), (10, 0), (11, 0), (12, 0), (12, 1), (12, 2), (12, 3), (11, 3), (10, 3), (10, 4), (10, 5), (11, 5), (12, 5), (13, 5), (13, 4), (14, 4), (14, 3), (15, 3), (15, 4), (15, 5))

Теперь необходимо с помощью этого пути извлечь сообщение из нижнего поля.

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

bottom_grid = ((None,None,8,6,None,8,None,None,None,None,None,None,None,2,None,9),
               (None,1,None,3,None,None,None,1,None,7,None,9,None,None,4,None),
               (7,None,4,None,6,None,9,None,5,4,None,3,4,None,1,None),
               (2,5,3,3,None,None,5,None,None,None,5,None,None,8,2,None),
               (None,None,5,None,None,5,None,None,None,5,None,None,6,3,None,None),
               (None,4,None,5,7,None,2,7,8,9,None,8,2,None,None,2))

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

def extract_message(grid, path):
    num_rows = len(grid)
    num_cols = len(grid[0])
    message = ''
    # decremental loop for the number of rows
    for row in range(num_rows-1,-1,-1):
        for col in range(num_cols):
            cell_value = grid[row][col]
            if (col,row) in path and isinstance(cell_value, int):
                message += str(cell_value)
            else:
                message += '-'
        # add newline character after each row
        message += '\n'
    return message

Сначала эта функция определяет количество строк и столбцов поля. Для извлечения сообщения она по очереди рассматривает строки поля в обратном порядке. Если какая-либо клетка данной строки является частью пути и содержит цифру, то к сообщению добавляется эта цифра. В противном случае, к сообщению добавляется символ '-'. После рассмотрения каждой строки поля функция добавляет к сообщению символ новой строки ('\n').

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

if __name__ == '__main__':
    # find path in the upper grid and extract and print corresponding message from the bottom grid of the puzzle
    path = search(start, finish, cols_in_left_rows, cols_constr, left_rows_constr, right_rows_constr)
    message = extract_message(bottom_grid, path)
    print(message)

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