Гарантированная проходимость в Mahjong Solitaire: алгоритм обратной раздачи

Вы когда-нибудь играли в Mahjong Solitaire и через 20 минут понимали, что не можете сделать ни одного хода? Это не ваша ошибка — случайная раздача часто приводит к нерешаемым комбинациям. В этой статье мы разберем алгоритм, который гарантирует, что каждая партия будет проходимой.

Проблема прямой раздачи

Прямая раздача (просто перемешать 144 плитки и разместить их на поле) кажется очевидной, но она часто порождает нерешаемые расклады. Четыре последние плитки могут оказаться погребёнными друг под другом, а две одинаковые — запертыми в позициях, которые никогда не станут свободными одновременно. Вы узнаете об этом не в начале, а спустя 20 минут игры, когда ничего не совпадает и нет пути назад.

Обратная раздача: решение

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

1. На пустом макете симулируем легальный порядок удаления. Многократно выбираем любые две свободные позиции и удаляем их, пока макет не опустеет. Позиции пока не имеют лиц, поэтому «свободность» здесь чисто геометрическая.
2. Накладываем пары лиц на этот порядок: пара, попавшая на две позиции, удалённые на шаге k, будет удалена на шаге k.

Повторение этого порядка очищает доску. Таким образом, полное решение существует ещё до того, как игрок начнёт играть.

Функция проверки свободы плитки

Плитка считается свободной, если сверху ничего нет и хотя бы одна длинная сторона (левая или правая) открыта.

def is_free(i, gone_set):
    # Получаем координаты плитки
    z, hx, hy = tiles[i]
    # Проверяем, есть ли плитка на соседних позициях
    def there(z, hx, hy):
        j = index.get(f"{z}|{hx}|{hy}")
        if j is None:
            return False
        return j not in gone_set
    # Проверка, что сверху ничего нет
    for dx in range(-1, 2):
        for dy in range(-1, 2):
            if there(z + 1, hx + dx, hy + dy):
                return False
    # Проверка открытости хотя бы одной длинной стороны
    left_open = not (there(z, hx - 2, hy - 1) or there(z, hx - 2, hy) or there(z, hx - 2, hy + 1))
    right_open = not (there(z, hx + 2, hy - 1) or there(z, hx + 2, hy) or there(z, hx + 2, hy + 1))
    return left_open or right_open

Координаты заданы в полуплиточных единицах, поэтому смещения равны ±1 и ±2: плитка покрывает две полуединицы по каждой оси, а полуединицы позволяют верхней плитке черепахи располагаться по центру блока 2×2 снизу.

Генерация порядка удаления

def removal_order(idxs):
    for attempt in range(60):
        gone = set([i for i in range(len(tiles)) if i not in idxs])
        order = []
        stuck = False
        while len(gone) < len(tiles):
            free = [i for i in idxs if i not in gone and is_free(i, gone)]
            if len(free) < 2:
                stuck = True
                break
            a = random.choice(free)
            b = a
            while b == a:
                b = random.choice(free)
            order.append((a, b))
            gone.add(a)
            gone.add(b)
        if not stuck:
            return order
    return None  # fallback

Цикл повторных попыток нужен, потому что жадный случайный выбор может завести в тупик — останутся плитки, но ни одной свободной пары. Можно было бы реализовать backtracking, но повторный запуск на классической черепахе почти всегда успешен, а код остаётся читаемым. Шестидесяти попыток более чем достаточно.

Накладывание лиц

def paste(order, pool):
    pairs = random.sample(pool, len(order))
    for k, (a, b) in enumerate(order):
        tiles[a].face = pairs[k][0]
        tiles[b].face = pairs[k][1]

Гарантия проходимости и её восприятие

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

idxs = [i for i, tl in enumerate(tiles) if not tl.gone]
order = removal_order(idxs)
if order:
    paste(order, pool_from_tiles(live_tiles()))

Таким образом, игрок никогда не оказывается в безвыходной ситуации. Вместо экрана «Game Over» появляется сообщение и кнопка «Перемешать».

Практический вывод

Если вы разрабатываете игру Mahjong Solitaire или любую другую игру, где случайная раздача может привести к нерешаемым состояниям, используйте обратную раздачу. Это просто реализовать, и это значительно улучшает пользовательский опыт. Попробуйте написать свой генератор на Python уже сегодня!