I want to generate several 3x3 puzzles (https://datawookie.netlify.app/blog/2019/04/sliding-puzzle-solvable/) with the same difficulty where difficulty is defined as the minimum necessary moves to reach the solution. For example, in a puzzle [1,2,3,4,5,6,7,0,8], the minimum necessary move is 1 because we can reach the solution by moving 8 up.
The above site has a python code to determine solvability, and I modified it a little bit so that it gives me the number of 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]
But the number of inversions is not the minimum necessary moves. How could I modify the code so that it also returns the minimum necessary moves? And, is there any way to automatically generate puzzles with the same minimum necessary moves?
Introducing a difficulties dictionary, as well as an is_solvable boolean in solvable(), and defining generate_tiles() to produce solvable game configurations using itertools.permutations(), as well as choose_difficulty() with default level set to 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))
Returns all the easy 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)}]