игра "15" автоматическое решение

[vcj]

Всем привет.
У меня есть одна проблема. Называется она Пятнашки. А именно автоматическое решение этих пятнашек. Кто натыкался на подобные задачи? поделитесь советом или литературой.

Заранее благодарю vcj;

[Kikasso]

Я когда-то долго мучился, а потом тупо стал записывать все ходы и по секретной комбинации клавиш их проигрывать в обратном порядке с маленькой паузой. Что касается "запутывания" - если просто "рассыпать" квадратики, есть вероятность что обратно не соберется. Я не помню, как определить решаема ли головоломка в данном конкретом случае, что-то там было связано с четностью. Так что и разбирал я просто - рендомно двигал квадратики.
Да, маленький совет - квадратиков 15, а пустое место 1, проще двигать пустое место. Успехов.

[vcj]

да... тут то же самое как и везде.

[Dima_DPE]

vcj бросай пить водку по русски и начни читать еврея Перельмана :)
Книга называется Живая математика на math.ru можно найти. Это что касается решаема или нет, а вот автоматическое решение пятнашек это задача для рекурсии (перебор с возвратом), но это еще надо просчитать глубину рекурсии (во флеше она ограничена 256, конечно если ты не пишешь на AS3)

[Kopilkus]

если делать обход в ширину, то глубина там будет 12 или 16, если мне не изменяет память. но точно не больше 256. а при рэндумном начальном расположении собиратся ровно в половине случаев. суть в том что нельзя поменять местами две рядом стоящие фишки, не нврушив притом расположение всех остальных

[Dima_DPE]

изменяет тебе память
http://forum.vingrad.ru/forum/topic-124956/hl/%25D0%25BF%25D1%258F%25D1%2582%25D0%25BD%25D0%25B0%25D1%2588%25D0%25BA%25D0%25B8/index.html
http://forum.vingrad.ru/forum/topic-106143/unread-1/hl/%25D0%25BF%25D1%258F%25D1%2582%25D0%25BD%25D0%25B0%25D1%2588%25D0%25BA%25D0%25B8/index.html

[vcj]

изменяет тебе память
http://forum.vingrad.ru/forum/topic-124956/hl/%25D0%25BF%25D1%258F%25D1%2582%25D0%25BD%25D0%25B0%25D1%2588%25D0%25BA%25D0%25B8/index.html
http://forum.vingrad.ru/forum/topic-106143/unread-1/hl/%25D0%25BF%25D1%258F%25D1%2582%25D0%25BD%25D0%25B0%25D1%2588%25D0%25BA%25D0%25B8/index.html

Спасибо. Я только начал там регистрироватся.

[vcj]

помогите разобратся почему не работает.

///VARS
var infinity = 10000;
var oppositeMove:Array = new Array();
var dx:Array = Array(0, -1, 0, 1);
var dy:Array = Array(1, 0, -1, 0);
trace(dx);
var moveDescription:Array = new Array();
var i:Number;
var j:Number;
var value1:Number;
var transpos:Number
var count:Number;
var manhattan:Number;
var newx:Number;
var newx:Number;
var x0:Number;
var y0:Number;
//---------------------

initGoalArrays();
function avto()
{
if (isSolvable()) //если доска нерешаема
trace("Неразрешима!!!");
else if (estimate()==0) //если это уже цель
trace("Это уже цель");
else
if (idaStar()) //делаем IDA* поиск
trace("!!!rabotaem!!!"+ resultString); //выводим результат
else trace("IDA* failed.");
}

function swap(y1, x1, y2, x2)
{ //trace("Start swap");
Value1 = A[y1][x1]; Value2 = A[y2][x2];
A[y1][x1] = Value2; A[y2][x2] = Value1;
trace("swap "+Value1+" <--> "+Value2);
}

function isSolvable()
{
trace("Start isSolvable");
var a=new Array();
for(i=1;i<16;i++)
{
a[i]=new Array();
}

for (i=1; i<=4; i++)
if (i%2==0)
for (j=1; j<=4; j++)
{
value1 = A[i][j];
if (value1>0) a[count++] = value1;
}
else for (j=4; j>=1; j--) {
value1 = A[i][j];
if (value1>0) a[count++] = value1;
}
for (i=0; i<count-1; i++)
for (j=i+1; j<count; j++)
if (a[i]>a[j]) transpos++;
trace("END isSolvable");
return (transpos%2 == 1);
}
//--------------------------------------------------------------------
function initGoalArrays() {
goalX = new Array();
goalY = new Array();
for (i=1; i<=15; i++) {
goalX[i] = i % 4;
goalY[i] = i / 4;
// trace(i+" | "+goalX[i]+" @ "+goalY[i]);
}
goalX[1] = 3; goalY[1] = 3;
}

function estimate() //эвристическая оценочная функция "Манхеттеновское расстояние"
{
//trace("Start estimate");
manhattan =0;
for (i=1; i<=4; i++)
for (j=1; j<=4; j++)
{

value1 = A[i][j];
if (value1>0) manhattan += Math.abs(i-goalX[value1]) + Math.abs(j-goalY[value1]);
// trace("A="+A[j][i]+" goalX[]= "+goalX[value1]+" goalY[]= "+goalY[value1]+" manhattan= "+manhattan);
}
trace("END estimate manhattan= "+manhattan);
return manhattan;
}
//--------------------------------------------------------------------
//DFS с обрезанием f=g+h < deepness
function recSearch(g,previousMove,x0,y0)
{

h = estimate(); // h = минимум ходов к цели
if (h == 0) return true; //если это цель - ура!
//если то, что мы прошли (g) + то, что нам как минимум осталось (h)
//больше допустимой глубины - выход.
f = g + h;


if (f > deepness)
{ //находим минимум стоимости среди "обрезаных" узлов
if (minPrevIteration > f) minPrevIteration = f;
return false;
}
// делаем всевозможные ходы
for (i=1; i<=4; i++)
if (oppositeMove[i] != previousMove) {
find0();

newx = x0 + dx[i];
newy = y0 + dy[i]; //новые координаты пустой клетки
if ((newy<=4) and (newy>=1) and (newx<=4) and (newx>=1)) {
swap(y0, x0, newy, newx); //двигаем пустую клетку на новое место
res = recSearch(g+1, i, newx, newy); //рекурсивный поиск с новой позиции

swap(y0, x0, newy, newx); //возвращаем пустую клетку назад
if (res) { //если было найдено решение
resultString+=moveDescription[i]; //записываем этот ход

return true; //и выходим

}
}
}
return false; //цели не нашли
}

//итерация глубины и IDA*
function idaStar() {

res = false;
deepness = estimate(); //начинаем с h для начального состояния
do {
minPrevIteration = infinity; //инициализация для поиска минимума
find0();
res = recSearch(0, -1, x0, y0);
deepness = minPrevIteration;
} while ((!res) and (deepness<=100)); //следующее значение «обрезающей» глубины
//////////////////////////////////

return res;
}

[Ляксей]

Это что касается решаема или нет, а вот автоматическое решение пятнашек это задача для рекурсии (перебор с возвратом), но это еще надо просчитать глубину рекурсии (во флеше она ограничена 256, конечно если ты не пишешь на AS3)
Ограничения рекурсии ( по скорости и по вложенности) имеют место если решать задучу с помощью рекурсивно решаемой функции.
А можно развернуть рекурсию и решать её динамически.
А именно, вместо вызова следующей итерации добавлять параметры этой ф-и в массив. Потом пробегать по массиву и вычислять эту ф-ю только уже не рекурсивно, а просто вызывать.
Пишется чуть сложнее поскольку надо заморочиться с массивом, но нет вышеупомянутых проблем с рекурсией.
Это получается типа как поиск вширину, а не в глубину.
Решение задачи с пятнашками, немного похожа на решение игры Sokoban.

помогите разобратся почему не работает.

Опишите детальнее, что не работает. Ошибки компилирования? Переполнение? Ещё что-то?
Воспользуйтесь трейсами и режимом Debug

[vcj]

ошибок нет. просто замыкается. т.е. гдето цыклится. перемещает 1 фишку туда сюда. пока не закончится глубина.

[Kikasso]

Вторая неделя пошла. Говорил - ходы записывай )))

[vcj]

не в ходах дело. есть в мире спаведливость. осталось её найти )))

[Ляксей]

Чтобы не было зацикливания в ситуациях когда просто одна фишка двигается туда сюда, и, что ещё хуже, фишка двигается по кругу за несколько ходов, можно применить такую идею.
Принять аксиому, что при переборе ситуация на поле ( "фотография" поля) не должна повторяться. То есть нет смысла двигать , двигать фишки и потом получить ТОЧНО такую же ситуацию на полу. Для этого можно организовать массив снимков и перед следующим ходо проверять, не является ли он одним из снимков в списке.
Да, програмирования много - но эта схема работает. Можно потом ещё развлечься оптимизацией поиска в стопке снимков с привлечением хеширования этого массива :)
Я такую схему делал, правда на C++ , очень высокотехничный алгоритм получился, для настоящих ценителей процесса программирования :)

[vcj]

а можеш дать мне этот алгоритм?

[Michaos]

вот работающий вариант

// IDA* algorithm
var dx:Array = new Array(0, -1, 0, 1); //смещения пустой клетки
var dy:Array = new Array(1, 0, -1, 0);
var moveDescription:Array = new Array("D", "L", "U", "R"); // Возможные ходы
var oppositeMove:Array = new Array(2, 3, 0, 1); // Противоположные ходы (2, 3, 0, 1)
var infinity = 10000;
var x0:Number; // координаты пустой клетки
var y0:Number; // координаты пустой клетки
var goalX:Array = new Array(); //goalX[i] - координата x i-й пятнашки, ...
var goalY:Array = new Array();
var board = new Array(); // доска
for (var i:Number = 0; i < 4; i++) {
board[i] = new Array();
}
var boardGoal = new Array(); // доска целевого состояния
for (var i:Number = 0; i < 4; i++) {
boardGoal[i] = new Array();
}
var deepness:Number; // глубина
var resultString:Array = new Array(); //результат
var minPrevIteration:Number; //минимум стоимости среди нерассмотренных узлов
//--------------------------------
//инициализирует целевое состояние
function initGoalArrays():Void {
for (var i:Number = 0; i <= 15; i++) {
goalX[i+1] = Math.floor(i / 4);
goalY[i+1] = i % 4;
}
goalX[0] = 3;
goalY[0] = 3;
}
//меняет местами две пятнашки
function swap(y1, x1, y2, x2):Void {
var value1:Number = board[y1][x1];
var value2:Number = board[y2][x2];
board[y1][x1] = value2;
board[y2][x2] = value1;
}
//определяет "решаемость" пятнашек
function isSolvable():Boolean {
var count:Number = 0;
var transpos:Number = 0;
var value:Number = 0;
var a = new Array();

for (var i:Number = 0; i < 4; i++) {
if (i % 2 == 0) {
for (var j:Number = 0; j < 4; j++) {
value = board[i][j];
if (value > 0) {
a[count] = value;
count++;
}
}
}
else {
for (var j:Number = 3; j >= 0; j--) {
value = board[i][j];
if (value > 0) {
a[count] = value;
count++;
}
}
}
}
for (var i:Number = 0; i < count - 1; i++) {
for (var j:Number = i + 1; j < count; j++) {
if (a[i] > a[j]) {
transpos++;
}
}
}
if (transpos % 2 == 1) {
return true;
}
}
//эвристическая оценочная функция Манхеттеновское расстояние
function estimate():Number {
var manhattan:Number = 0;
var value:Number;
for (var i:Number = 0; i < 4; i++)
for (var j:Number = 0; j < 4; j++) {
value = board[i][j];
if ((value > 0) && (value != boardGoal[i][j])) {
manhattan += Math.abs(i - goalX[value]) + Math.abs(j - goalY[value]);
}
}
return manhattan;
}
//DFS с обрезанием f=g+h < deepness
var counter:Number;
function recSearch(g:Number, previousMove, x0:Number, y0:Number):Boolean {
var h:Number = estimate();
// h = минимум ходов к цели
if (h == 0) {
return true; // если это цель - ура!
}
// если то, что мы прошли (g) + то, что нам как минимум осталось (h)
// больше допустимой глубины - выход.
var f:Number = g + h;
if (f > deepness) {
//нaходим минимум стоимости среди "обрезаных" узлов
if (minPrevIteration > f) {
minPrevIteration = f;
}
return false;
}
// делаем всевозможные ходы
for (var i:Number = 0; i < 4; i++) {
if (oppositeMove[i] != previousMove) {
// новые координаты пустой клетки
var newx:Number = x0 + dx[i];
var newy:Number = y0 + dy[i];
if ((newy <= 3) && (newy >= 0) && (newx <= 3) && (newx >= 0)) {
swap(y0, x0, newy, newx); // двигаем пустую клетку на новое место
var res:Boolean = recSearch(g + 1, i, newx, newy); // рекурсивный поиск с новой позиции
swap(y0, x0, newy, newx); // возвращаем пустую клетку назад
if (res) { //если было найдено решение
resultString.push(moveDescription[i]); //записываем этот ход
return true; // и выходим
}
}
}
}
return false; //цели не нашли
}
// итерация глубины и IDA*
function idaStar():Boolean {
var res:Boolean = false;
deepness = estimate(); // начинаем с h для начального состояния
do {
minPrevIteration = infinity; // инициализация для поиска минимума
// поиск пустой клетки
for (var i:Number = 0; i <4; i++) {
for (var j:Number = 0; j <4; j++) {
if (board[i][j] == 0) {
x0 = j;
y0 = i;
}
}
}
res = recSearch(0, -1, x0, y0);
deepness = minPrevIteration;
} while ((!res) && (deepness <= 50)); // следующее значение «обрезающей» глубины
return res;
}
// ----------------------------
function main():Void {
initGoalArrays();
// Исходная доска
board[0] = [2, 3, 4, 8];
board[1] = [1, 10, 6, 7];
board[2] = [5, 11, 12, 0];
board[3] = [9, 13, 14, 15];
// Целевая доска
boardGoal[0] = [1, 2, 3, 4];
boardGoal[1] = [5, 6, 7, 8];
boardGoal[2] = [9, 10, 11, 12];
boardGoal[3] = [13, 14, 15, 0];

if (!isSolvable()) { // если задача нерешаема
trace("Задача неразрешима");
}
else if (estimate() == 0) { //если это уже цель
trace("Это уже цель");
}
else if (idaStar()) { //делаем IDA* поиск
trace("Путь:" + resultString); //выводим результат
}
else {
trace("IDA* failed");
}
}
main();

[terbooter]

А, пятнашки!
Где-то я видел или слышал что должна быть простая проверка,
на собираемость, точно не помню, но должно что то быть вроде суммы вертикалей и диагоналей...
Я делал как все -) Рандомно разбирал и записывал ходы.

В какой-то момент стало скучно, для поддержания интереса вместо циферек порезал картинку с девушкой -)))