@alexu_007

Хочу написать программу, решающую пятнашки. В сети нашёл исходники аж 2 шт, оба работают неудовлетворительно, а именно - виснут при некоторых корректных исходных данных. Хочу сделать сам.

Имеется исходное поле, например
1 2 3 4
5 10 6 8
9 11 7 12
13 15 14 0

Данные хранятся в структуре вида:

Вначале можно сделать 2 хода: 12 и 14 (функцию, получающую возможные ходы написал) - т.е. из исходной структуры получим две, и для хранения нужно уже 2 списка вида: data0, data1 и data0, data2. Затем из data1 и data2 можно из каждого сделать по 2 хода:

data0, data1, data3
data0, data1, data4
data0, data2, data5
data0, data2, data6

и так далее, количество списков (и количество структур в них) будет быстро увеличиваться, но мне нужно первые 5-6-7 ходов. Вопрос - как объявлять новые структуры и как объявлять новые списки структур? Как заставить всё это работать?

Затем, когда списков будет много, для каждой позиции можно будет вычислить "рейтинг", ветки с плохим рейтингом удалить, а оставшиеся продолжить - т.е. должна быть возможность удаления целых веток списков.

0

@yarko

Попробуйте сделать QStack<data*>. На каждом шагу брать верхний елемент, проверять на тупик, создавать (если рейтинг хороший) 2-4 новых data в зависимости от положения, пихать их обратно в стек и делать следующий шаг.

0

Байт

alexu_007, Я бы использовал QHash. А в качестве ключа можно взять pole. Причем его величину можно сократить до 8 байт (16 четырехбитовых цифр)
И для 7 ходов нужно не так уж много памяти. Верхняя граница 4⁷ = 16000. Даже меньше, поскольку "обратные" ходы смысла не имеют, 3⁷ = 2187

0

@Wyn

alexu_007, На мой взгляд для подобной темы лучше применять обычное дерево.

0