生成具有相同难度的 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]

但是倒转的次数并不是最少的必要步数。我如何修改代码以使其也 returns 最少的必要移动？还有，有什么方法可以自动生成具有相同最少必要步数的谜题吗？

Answer 1

拼图的 "difficulty" 可以通过不同的指标（例如反转次数、初始配置、大小等）来估算。有些有意义，有些则没有。这取决于您尝试不同的方法并决定它们是否是好的 "difficulty" 估计器。但请记住，有时您所说的 "difficulty" 是主观的。

找到这些指标并尝试用它们评估你的谜题。

Answer 2

在 solvable() 中引入困难字典和 is_solvable 布尔值，并定义 generate_tiles() 以使用 itertools.permutations() 生成可求解的游戏配置，以及作为 choose_difficulty()，默认级别设置为简单：

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))

Returns 所有简单的方块：

...
 {'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)}]

Answer 3

您有 3 种通用方法：

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

2- 从已解决的位置开始，您可以 通过随机滑动方块来打乱拼图 - 这将为您估算难度；有些动作可能会取消之前的动作，所以动作的数量将有上限。

2-bis) 更复杂的扰频器将防止重复状态，并为您提供更准确的路径长度，如 (1) 中所示 - 您仍然会有一些难题被归类为困难（长路径），而实际上它们是很容易，当随机路径中存在更有效的捷径时。

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

生成具有相同难度的 3x3 拼图？

Generate 3x3 puzzles with the same difficulty?

python

python-3.x

algorithm

sliding-tile-puzzle