生成3x3个相同难度的谜题？

Question

我想生成几个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]

但反转的次数并不是必要的最小移动次数。我如何修改代码，使其也返回最小的必要移动？还有，有没有办法用相同的最小动作自动生成谜题

Answer 1

您有3种通用方法：

1-如果要创建的谜题数量有限，您可以生成一个谜题，然后解决它，以获得准确的最小移动次数-然后使用该数量按难度级别对谜题进行分类

2-从一个已解决的位置，你可以通过随机滑动瓷砖来搅乱一个谜题，这将给你一个难度估计；某些移动可能会取消以前的移动，因此移动的数量将被限制

2-之二）更复杂的扰码器将防止重复状态，并提供更精确的路径长度，如（1）所示-当一些难题实际上很容易时，当在随机路径中存在更有效的快捷方式时，仍然会有一些难题被归类为硬（长路径）

3-正如其他答案中提到的，你可以找到估计所需移动次数的指标，但这可能不容易得到一个好的估计

Answer 2

一个谜题的“难度”可以通过不同的指标来估计（例如反转的数量、初始配置、大小等）。有些是有意义的，有些不是。这取决于你尝试不同的方法，并决定它们是否是好的“难度”估计器。但请记住，有时，你所谓的“困难”是主观的

找到这些指标，并尝试用它们来评估你的难题

Answer 3

在solvable（）中引入一个困难字典以及一个is_solvable布尔值，并定义generate_tiles（）以使用itertools.permutations（）生成可解决的游戏配置，以及选择默认级别设置为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)}]