C++: 8 Puzzle

Лабораторная работа по курсу C++, ИТМО

Написать программу, которая решает головоломку 8 Puzzle (и её обобщения) с использованием алгоритма A*.

https://en.wikipedia.org/wiki/15_puzzle

https://en.wikipedia.org/wiki/A*_search_algorithm

Реализуйте класс Board

Вам необходимо реализовать неизменяемый класс доски, который будет удовлетворять следующим требованиям:

• Конструктор, принимающий массив в пространстве размерности 2, который заполнен целыми числами
• Статический метод create_random, принимающий размер доски и генерирующий некоторое состояние на доске
• Метод size, возвращающий размер доски
• Метод hamming, возвращающий количество блоков не на своих местах
• Метод manhattan, возвращающий сумму Manhattan расстояний между блоками и целью
• Метод is_goal, который отвечает на вопрос является ли эта доска целью
• Метод is_solvable, который отвечает на вопрос, решаема ли такая расстановка элементов
• Операторы == и != для board
• Метод to_string и операторы вывода для текстового представления строк
• Такой синтаксис должен работать: board b(3); std::cout << b[1][1] << std::endl;, выводит элемент в ячейке (1, 1)
• Класс должен поддерживать операции копирования
• Доступ на чтение к объектам Board должен быть потокобезопасным (без применения примитивов синхронизации)
• Обращение к статическим функциям Board должно быть потокобезопасным (без применения примитивов синхронизации)
• Одновременный доступ на запись к разным объектам Board должен быть безопасным (без применения примитивов синхронизации)

Реализуйте классы Solver и Solution

Solver должен предоставлять статический метод solve, принимающий начальную доску и возвращающий экземпляр класса Solution. Solution не должен быть доступен для пользовательского кода иначе, как через публичный интерфейс Solver. Solution должен предоставлять по крайней мере такой публичный интерфейс:

• Метод moves, который выводит количество перемещений, которые приводят к решению
• Итератор, который позволяет пройтись по последовательности board, приводящей к решению
• Методы begin и end
• Операции копирования
• Обращение к статическим функциям Solver должно быть потокобезопасным (без применения примитивов синхронизации)
• Публичный интерфейс Solution должен быть потокобезопасным (без применения примитивов синхронизации)

Если решения не существует, тогда begin() == end(). Т.е. в решении должно быть 0 досок которые приводят к решению. Если размер доски задан 0 или 1, то можно считать, что решение есть и возможно создать лишь доску-решение.

HINT: Для решения этой задачи не обязательно писать свой итератор.