Я работал над анализом памяти и профиля времени в Knight's Tour в Python с помощью слепого поиска в глубину и написал простую программу для генерации решений, или, как мне показалось,
Моя задача состоит в том, чтобы выбрать 5 начальных отправных точек на шахматной доске и найти решение для каждой из них (с максимальным шагом в 1 мил, чтобы отказаться от попытки найти решение), где одна начальная точка всегда равна 0,0
Моя проблема в том, что требуется 100 000 шагов ДОЛГО, и мне нужно ускорить его. Однако я не уверен, как, и не вижу, в чем может быть проблема и основной фактор замедления.
Кроме того, я превышаю даже расширенный предел рекурсии. Можно ли еще увеличить его? .. То, как я закодировал метод, я думаю, что все должно быть в порядке, поскольку я передаю минимальные данные.
from random import *
from itertools import product # Easy random unique tuple generation
from pprint import pprint # To allow pretty printing for better analysis
import numpy as np # Will allow for arrays, where arithmetic is MUCH faster than in lists
import sys
import time
# TODO tests
class Euler:
def __init__(self, size_board: int, max_steps: int = None, random_seed: int = None):
self.max_steps = max_steps
if self.max_steps is None:
self.max_steps = 10e6
if random_seed is not None:
seed(random_seed) # Used for testing purposes to get same output every time.
self.size = size_board
self.max_depth = self.size ** 2
self.start_positions = sample(list(product(range(1, self.size), repeat=2)), k=4) # Generate random 2D positions
self.start_positions.insert(0, (0, 0)) # Add fixed [0, 0] position to compare 6x6 and 5x5 easily
print("Starting positions: ")
pprint(self.start_positions)
self.solutions = [] # Looking for first 5 solutions for each starting position
self.moves = [(1, 2), # Allowed jumps
(1, -2),
(2, 1),
(2, -1),
(-1, 2),
(-1, -2),
(-2, 1),
(-2, -1)]
for pos in self.start_positions:
self.steps_left = self.max_steps
self.board = np.array([[-1 for i in range(self.size)] for i in range(self.size)]) # Generate the chessboard
self.board[pos[0]][pos[1]] = 1 # Set first position as 1
self.blind_dfs(pos, 1)
for solution in self.solutions:
print("Solutions for starting position ", self.start_positions[0])
pprint(solution)
print()
self.start_positions.pop(0)
# Externally uses steps_left. The chessboard array is passed by reference, not copies. This is a procedure.
def blind_dfs(self, start, depth):
# If we're on a position labeled as the last possible position, we've found a solution
if depth == self.max_depth:
self.solutions.append(self.board.copy())
print("Found solution")
return -1 # Terminate recursion chain
for move in self.moves:
"""
We have to place this condition here, because this cycle could happen while there were steps
left, and if we put this outside, it would have no way of knowing to stop
the cycle even when out of steps, on older recursion depths
"""
if self.steps_left < 1:
self.solutions.append("Ran out of steps")
print("Solution not found")
return -1
step = tuple(np.add(start, move)) # Add the movement to the current position
# Check if we go outside the chessboard. If a number from the pair in the tuple is negative or > size, skip
if sum(1 for number in step if number < 0) == 0 and all(i < self.size for i in step):
if self.board[step] == -1:
self.board[step] = depth + 1 # Set the correct step order on the next position
self.steps_left -= 1
"""if self.steps_left % 100000 == 0: # Simple tracking
print(self.steps_left)"""
if self.blind_dfs(step, depth + 1) == -1:
return -1 # Annihilate recursion chain
self.board[step] = -1 # Going to try a new direction, so undo the step
else:
continue
sys.setrecursionlimit(2000) # Default is 1000. It is safe to modify it here, the stackframes are not big.
while (size := input("Enter size of board NxN: ")) != "":
try:
size = int(size)
except ValueError:
print("Please enter an integer.")
continue
steps = input("Enter max amount of steps (leave empty for 10e6 steps): ")
if steps == "":
steps = None
else:
try:
steps = int(steps)
except ValueError:
print("Please enter an integer.")
continue
Euler(size, steps, 4)