Implementation of A* search algorithm to solve N-puzzles (пятнашки, 15-Puzzle, taquin)
Алгоритм А* - информированный алгоритм поиска, который находит маршрут наименьшей стоимости между начальной и конечной вершинами во взвешенном графе, в нашем случае алгоритм находит наилучший набор движений пустого блока, который приводит головоломку в конечный вид.
Основные правила
- головоломка состоит из квадратного поля N*N элементов;
- каждая ячейка содержит уникальное число от 1 до N^2 - 1 в рандомном порядке, одна из ячеек остается пустой;
- за один ход можно менять местами пустой блок с соседними ячейками;
- необходимо преобразовать поле в конечный вид "snail solution";
- A*
- heuristics
- dfs
- bfs
- greedy search