Первоначально я пытался создать базу данных непересекающихся (6-6-3) шаблонов для 15-головоломок, но я изо всех сил старался, чтобы сначала попытаться создать полную базу данных шаблонов для 8- головоломка, что означает, что я хочу сохранить все возможные варианты 8-головоломки в файл, чтобы создать heuristi c для использования при попытке решить головоломку с помощью алгоритма A *.
Целью 8-головоломки является [1, 2, 3, 4, 5, 6, 7, 8, 0], где 0 - пустая клетка. Для создания перестановок я использую поиск в ширину из состояния цели и сохраняю каждую перестановку в виде кортежа состояния головоломки и стоимости (количества ходов), чтобы достичь ее из состояния цели.
Мой код выглядит следующим образом:
import math
import json
from collections import deque
from copy import deepcopy
from timeit import default_timer
# Goal state of the puzzle
goal = [1, 2, 3, 4, 5, 6, 7, 8, 0]
# Calculates the possible moves of the blank tile.
def get_moves(puzzle):
# Lists potential moves in order: up, right, down, left.
potential_moves = [-3, 1, 3, -1]
# Checks which moves are possible.
possible_moves = []
for pm in potential_moves:
pos = puzzle.index(0)
pos += pm
if pos in range(8):
possible_moves += [pm]
return possible_moves
# Moves the blank tile in the puzzle.
def move(puzzle, direction):
# Creates a copy of the new_puzzle to change it.
new_puzzle = deepcopy(puzzle)
pos = puzzle.index(0)
# Swaps blank tile with tile in direction.
if direction == -3:
new_puzzle[pos], new_puzzle[pos-3] = new_puzzle[pos-3], new_puzzle[pos]
elif direction == 1:
new_puzzle[pos], new_puzzle[pos+1] = new_puzzle[pos+1], new_puzzle[pos]
elif direction == 3:
new_puzzle[pos], new_puzzle[pos+3] = new_puzzle[pos+3], new_puzzle[pos]
elif direction == -1:
new_puzzle[pos], new_puzzle[pos-1] = new_puzzle[pos-1], new_puzzle[pos]
return new_puzzle
# Transforms a puzzle to a string.
def puzzle_to_string(puzzle):
string = ""
for t in puzzle:
string += str(t)
return string
# Creates the database.
def create_database():
# Initializes a timer, starting state, queue and visited set.
begin = default_timer()
start = goal
queue = deque([[start, 0]])
visited = set()
visited.add((puzzle_to_string(start), 0))
print("Generating database...")
print("Collecting entries...")
# BFS taking into account a state and the cost to reach it from the starting state.
while queue:
states = queue.popleft()
state = states[0]
cost = states[1]
for m in get_moves(state):
next_state = move(state, m)
cost += 1
if not any(s for s in visited if s[0] == puzzle_to_string(next_state)):
queue.append([next_state, cost])
visited.add((puzzle_to_string(next_state), cost))
# Print a progress for every x entries in visited.
if len(visited) % 10000 == 0:
print("Entries collected: " + str(len(visited)))
# Exit loop when all permutations for the puzzle have been found.
if len(visited) >= math.factorial(9)/2:
break
print("Writing entries to database...")
# Writes entries to the text file, sorted by cost in ascending order .
with open("database.txt", "w") as f:
for entry in sorted(visited, key=lambda c: c[1]):
json.dump(entry, f)
f.write("\n")
end = default_timer()
minutes = math.floor((end-begin)/60)
seconds = math.floor((end-begin) % 60)
return "Generated database in " + str(minutes) + " minute(s) and " + str(seconds) + " second(s)."
print(create_database())
Теперь проблема в том, что заполнение записей (все еще) занимает невыносимо много времени, чего, вероятно, не должно быть, поскольку в 8-головоломке всего 9! / 2 = 181440 возможных перестановок, поэтому должна быть возможность довольно быстро создать полную базу данных.
Буду признателен за любой вклад в эту проблему и, если возможно, также некоторые советы в направлении создания баз данных непересекающихся шаблонов. для 15 головоломок.
Заранее спасибо!
Редактировать: Я обнаружил проблему, мне удалось испортить функцию перемещения при преобразовании из 15 головоломок, которые используют 4 строки вместо имея 1-мерную строку. Кроме того, я также испортил приращение стоимости состояний где-то вдоль линии.
Вот обновленный рабочий код, который генерирует полную базу данных для 8 задач за ~ 15 секунд на моей машине.
import json
import math
from collections import deque
from copy import deepcopy
from timeit import default_timer
# Goal state of the puzzle
goal = [1, 2, 3, 4, 5, 6, 7, 8, 0]
# Calculates the possible moves of the blank tile.
def get_moves(puzzle):
pos = puzzle.index(0)
if pos == 0:
possible_moves = [1, 3]
elif pos == 1:
possible_moves = [1, 3, -1]
elif pos == 2:
possible_moves = [3, -1]
elif pos == 3:
possible_moves = [-3, 1, 3]
elif pos == 4:
possible_moves = [-3, 1, 3, -1]
elif pos == 5:
possible_moves = [-3, 3, -1]
elif pos == 6:
possible_moves = [-3, 1]
elif pos == 7:
possible_moves = [-3, 1, -1]
else:
possible_moves = [-3, -1]
return possible_moves
# Moves the blank tile in the puzzle.
def move(puzzle, direction):
# Creates a copy of the new_puzzle to change it.
new_puzzle = deepcopy(puzzle)
pos = puzzle.index(0)
# Position blank tile will move to.
new_pos = pos + direction
# Swap tiles.
new_puzzle[pos], new_puzzle[new_pos] = new_puzzle[new_pos], new_puzzle[pos]
return new_puzzle
# Creates the database.
def create_database():
# Initializes a timer, starting state, queue and visited set.
begin = default_timer()
start = goal
queue = deque([[start, 0]])
entries = set()
visited = set()
print("Generating database...")
print("Collecting entries...")
# BFS taking into account a state and the cost (number of moves) to reach it from the starting state.
while queue:
state_cost = queue.popleft()
state = state_cost[0]
cost = state_cost[1]
for m in get_moves(state):
next_state = move(state, m)
# Increases cost if blank tile swapped with number tile.
pos = state.index(0)
if next_state[pos] > 0:
next_state_cost = [next_state, cost+1]
else:
next_state_cost = [next_state, cost]
if not "".join(str(t) for t in next_state) in visited:
queue.append(next_state_cost)
entries.add(("".join(str(t) for t in state), cost))
visited.add("".join(str(t) for t in state))
# Print a progress for every x entries in visited.
if len(entries) % 10000 == 0:
print("Entries collected: " + str(len(entries)))
# Exit loop when all permutations for the puzzle have been found.
if len(entries) >= 181440:
break
print("Writing entries to database...")
# Writes entries to the text file, sorted by cost in ascending order .
with open("database.txt", "w") as f:
for entry in sorted(entries, key=lambda c: c[1]):
json.dump(entry, f)
f.write("\n")
end = default_timer()
minutes = math.floor((end-begin)/60)
seconds = math.floor((end-begin) % 60)
return "Generated database in " + str(minutes) + " minute(s) and " + str(seconds) + " second(s)."
print(create_database())