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

vcj · 21.08.2007, 13:43

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

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

Kikasso · 21.08.2007, 14:44

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

vcj · 21.08.2007, 15:08

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

Dima_DPE · 21.08.2007, 15:58

vcj бросай пить водку по русски и начни читать еврея Перельмана

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

Kopilkus · 21.08.2007, 16:03

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

Dima_DPE · 21.08.2007, 16:40

изменяет тебе память
http://forum.vingrad.ru/forum/topic-...5B8/index.html
http://forum.vingrad.ru/forum/topic-...5B8/index.html

vcj · 21.08.2007, 17:15

Цитата:

Сообщение от Dima_DPE

изменяет тебе память
http://forum.vingrad.ru/forum/topic-...5B8/index.html
http://forum.vingrad.ru/forum/topic-...5B8/index.html

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

vcj · 30.08.2007, 13:52

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

Код:

///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;
  }

Ляксей · 31.08.2007, 13:13

Цитата:

Сообщение от Dima_DPE

Это что касается решаема или нет, а вот автоматическое решение пятнашек это задача для рекурсии (перебор с возвратом), но это еще надо просчитать глубину рекурсии (во флеше она ограничена 256, конечно если ты не пишешь на AS3)

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

Цитата:

Сообщение от vcj

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

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

vcj · 03.09.2007, 11:23

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