Создавать головоломки 3x3 с одинаковой сложностью?

Я хочу сгенерировать несколько головоломок 3x3 (https://datawookie.netlify.app/blog/2019/04/sliding-puzzle-solvable/) с той же сложностью, где сложность определяется как минимально необходимые ходы для достижения решения. Например, в головоломке [1,2,3,4,5,6,7,0,8] минимальный необходимый ход равен 1, потому что мы можем достичь решения, переместив 8 вверх.

На указанном выше сайте есть код Python для определения разрешимости, и я немного изменил его, чтобы он давал мне количество инверсий:

def solvable(tiles):
    count = 0
    for i in range(8):
        for j in range(i+1, 9):
            if tiles[j] and tiles[i] and tiles[i] > tiles[j]:
                count += 1
    return [count, count % 2 == 0]

Но количество переворотов - это не минимально необходимый минимум ходов. Как мне изменить код, чтобы он также возвращал минимально необходимые ходы? И есть ли способ автоматически генерировать головоломки с одинаковыми минимально необходимыми ходами?

Источник

3 ответа

Решение

Введение словаря трудностей, а также логического значения is_solvable в solvable () и определение generate_tiles() для создания решаемых игровых конфигураций с помощью itertools.permutations(), а также select_difficulty() с уровнем по умолчанию, установленным на easy:

from itertools import permutations
from pprint import pprint as pp


def solvable(tiles):
    count = 0
    for i in range(8):
        for j in range(i+1, 9):
            if tiles[j] and tiles[i] and tiles[i] > tiles[j]:
                count += 1

    is_solvable = count % 2 == 0

    if is_solvable:
        difficulties = {'0': 'trivial',
                        '2': 'easy',
                        '4': 'medium',
                        '6': 'hard'
                        }
        difficulty = difficulties.get(str(count), 'very hard')
        return [difficulty, count, is_solvable]

    return [count, is_solvable]


def generate_tiles(count=2):
    """Generate solvable tiles for the 3x3 puzzle."""
    tile_candidates = list(permutations(list(range(9))))
    good_tiles = []
    for tile_candidate in tile_candidates:
        if solvable(tile_candidate)[-1]:
            good_tiles.append(tile_candidate)
    return good_tiles


def choose_difficulty(tiles, level=2):
    """Choose difficulty for the 3x3 puzzle, default level is easy (2)."""
    labelled_tiles = []
    for tile in tiles:
        labelled_tiles.append({"tile": tile,
                               "label": solvable(tile)
                               })
    level_tiles = []
    for tile_dict in labelled_tiles:
        if tile_dict['label'][1] == level:
            level_tiles.append(tile_dict)
    return level_tiles


if __name__ == '__main__':
    # Generate all solvable and easy tiles
    tiles = generate_tiles()
    pp(choose_difficulty(tiles))

Возвращает все простые плитки:

...
 {'label': ['easy', 2, True], 'tile': (2, 3, 1, 4, 5, 6, 7, 8, 0)},
 {'label': ['easy', 2, True], 'tile': (3, 0, 1, 2, 4, 5, 6, 7, 8)},
 {'label': ['easy', 2, True], 'tile': (3, 1, 0, 2, 4, 5, 6, 7, 8)},
 {'label': ['easy', 2, True], 'tile': (3, 1, 2, 0, 4, 5, 6, 7, 8)},
 {'label': ['easy', 2, True], 'tile': (3, 1, 2, 4, 0, 5, 6, 7, 8)},
 {'label': ['easy', 2, True], 'tile': (3, 1, 2, 4, 5, 0, 6, 7, 8)},
 {'label': ['easy', 2, True], 'tile': (3, 1, 2, 4, 5, 6, 0, 7, 8)},
 {'label': ['easy', 2, True], 'tile': (3, 1, 2, 4, 5, 6, 7, 0, 8)},
 {'label': ['easy', 2, True], 'tile': (3, 1, 2, 4, 5, 6, 7, 8, 0)}]
Источник

"Сложность" головоломки можно оценить с помощью различных показателей (например, количество инверсий, начальная конфигурация, размер и т. Д.). Некоторые значимы, некоторые нет. Вам решать, попробовать разные варианты и решить, подходят ли они для оценки "сложности". Но имейте в виду, что иногда то, что вы называете "трудностью", является субъективным.

Найдите эти показатели и попытайтесь с их помощью решать свои головоломки.

Источник

У вас есть 3 общих подхода:

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

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

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

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

Источник
Другие вопросы по тегам