Je souhaite générer plusieurs puzzles 3x3 (https: //datawookie.netlify .app / blog / 2019/04 / glissant-puzzle-résoluble /) avec la même difficulté où la difficulté est définie comme le minimum de mouvements nécessaires pour atteindre la solution. Par exemple, dans un puzzle [1,2,3,4,5,6,7,0,8], le mouvement minimum nécessaire est 1 car nous pouvons atteindre la solution en déplaçant 8 vers le haut.

Le site ci-dessus a un code python pour déterminer la solvabilité, et je l'ai modifié un peu pour qu'il me donne le nombre d'inversions:

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]

Mais le nombre d'inversions n'est pas le minimum de coups nécessaires. Comment pourrais-je modifier le code pour qu'il renvoie également les mouvements minimums nécessaires? Et, existe-t-il un moyen de générer automatiquement des puzzles avec les mêmes mouvements minimums nécessaires?

-2
Yuki Takahashi 2 juin 2020 à 13:14

3 réponses

Meilleure réponse

Introduction d'un dictionnaire de difficultés, ainsi que d'un booléen is_solvable dans solvable (), et définition de generate_tiles () pour produire des configurations de jeu résolubles en utilisant itertools.permutations (), ainsi que choose_difficulty () avec le niveau par défaut défini sur 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))

Renvoie toutes les tuiles faciles:

...
 {'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)}]
1
Gustav Rasmussen 2 juin 2020 à 11:21

Vous avez 3 approches générales:

1 - Si le nombre de puzzles à créer est limité, vous pouvez générer un puzzle, et le résoudre pour obtenir le nombre minimum exact de coups - vous l'utilisez ensuite pour classer les puzzles par niveau de difficulté.

2- A partir d'une position résolue, vous pouvez brouiller un puzzle en faisant glisser des tuiles au hasard - cela vous donnera une estimation de la difficulté; certains coups peuvent annuler les précédents, donc le nombre de coups sera plafonné.

2-bis) Un brouilleur plus sophistiqué empêchera les états répétés et vous donnera une longueur de chemin plus exacte que dans (1) - Vous aurez toujours des casse-tête classés comme difficiles (chemin long) quand ils sont en fait faciles, quand ils existent un raccourci plus efficace dans le chemin aléatoire.

3 - comme cela a été mentionné dans d'autres réponses, vous pouvez trouver des statistiques qui estiment le nombre de mouvements nécessaires, mais il peut ne pas être facile d'obtenir une bonne estimation.

1
Reblochon Masque 2 juin 2020 à 11:53

La "difficulté" d'un puzzle peut être estimée par différentes métriques (par exemple, nombre d'inversions, configuration initiale, taille, etc.). Certains sont significatifs, d'autres non. C'est à vous d'en essayer différents et de décider s'ils sont de bons estimateurs de «difficulté». Mais gardez à l'esprit que parfois, ce que vous appelez «difficulté» est subjectif.

Trouvez ces paramètres et essayez d'évaluer vos énigmes avec eux.

1
Adam Boinet 2 juin 2020 à 10:28