Пятнашки

Задача

Пятнашки - известная головоломка в которой 15 костяшек, находятся в коробке размером × . Мы будем рассматривать произвольный размер "игрового поля", поэтому цифры выше можно редактировать, затем нажав кнопку mix, попрбовать собрать головоломку. При этом нормальное (целевое) расположение костяшек то, которое было до нажатия кнопки. На самом деле, обычно, пустая клетка находится в правом нижнем углу. Однако, мы будем считать, что это костяшка с номером ноль, поэтому, естественно дырку рассположить в начале массива: 0, 1, 2, 3,...

Пятнашки являются отличным полигоном для тестирования различных алгоритмов поиска решений. Число возможных состояний (конфигураций поля) для головоломки с n костяшками (включая дырку) равно n!. Действительно, перечисляя костяшки слева направо и сверху вниз, игровое поле можно представить в виде последовательности n цифр 0,1,...,n-1. Различные расклады костяшек соответствуют различным перестановкам этих чисел, которых как раз n!. В частности для классического варианта 16!=20922789888000, поэтому простой перебор решение найти не позволит.

На самом деле все возможные состояния игры разбиваются на два равных непересекающихся множества. Если поменять местами любые две соседние костяшки ("вытащив" их из коробки), перейдём от одного множества в другое. После такой операции ни какими перестановками костяшек собрать головоломку не пролучится.

Класс Fifteen

Хотя мы рассматриваем головоломку игровым полем произвольного размера, будем по-прежнему её называть пятнашками. Создадим конструктор класса Fifteen:

function Fifteen(nx, ny)
{
   this.nX = nx? nx: 4;                           // число ячеек по горизонтали
   this.nY = ny? ny: 4;                           // число ячеек по вертикали
   this.desk = new Array(this.nX*this.nY);        // игровое поле
   this.hole = 0;                                 // положение дырки
   this.move = -1;                                // ход, который привёл к этому состоянию

   for(var i=0; i < this.desk.length; i++)        // начальный порядок
      this.desk[i] = i;
}

Fifteen.prototype.getNear = function (k)
{
   var go = [];                                   // возвращаемый массив
   var i = k % this.nX, j = (k-i)/this.nX;        // номер k по x и y

   if(j   > 0)       go.push(k-this.nX);          // вверх
   if(j+1 < this.nY) go.push(k+this.nX);          // вниз
   if(i > 0)         go.push(k-1);                // влево
   if(i+1 < this.nX) go.push(k+1);                // вправо

   return go;
}

Чтобы не проверять каждый раз границы поля, можно было бы создать ненаправленный граф в виде прямоугольной сетки (как нарисовано справа от кода). Имея его, легко получить массив соседних ячеек graph.nodes[k].go. Мы не будем так поступать, для экономии памяти (необходимо будет создавать много экземпляров головоломки).

Рисуем головоломку

Определим статическое свойство пятнашек в виде объекта в котором будут задаваться параметры графического отображения головоломки:

Fifteen.svg = {        // параметры графического отображения
   w: 50,              // ширина костяшки
   сDesk: "#069",      // цвет игрового поля (бэкграунд)
   cDice: "#FFA",      // цвет костяшки
}

В качестве инструмента рисования используем класс Draw, который единообразно рисует как на канвасе, так и создаёт картинки в svg-формате. Если экземпляр draw этого класса создан, можно написать функцию рисования на "нём":

Fifteen.prototype.show = function(draw)
{
   var svg = Fifteen.svg;                         // визуальные параметры
   draw.clear();                                  // очищаем (актуально для канваса)

   draw.widthLine(2);                             // толстые линии
   draw.colorFill(svg.сDesk);                     // цвет игрового поля
   var w = svg.w*this.nX, h = svg.w*this.nY;      // размеры игрового поля
   draw.box(2+w/2, 2+h/2, w+4, h+4, 5);           // рисуем игровое поле

   draw.colorFill(svg.cDice);                     // цвет костяшки
   draw.sizeText(Math.floor(0.60*svg.w));         // размер текста по размеру костяшки
   for(var j=0; j < this.nY; j++)                 // бежим по ячейкам поля
      for(var i=0; i < this.nX; i++){
         var x = 3+svg.w/2 + i*svg.w, y = 3+ svg.w/2 + j*svg.w;
         var k = i+j*this.nX;                     // номер в массиве desk
         if(this.desk[k]){                        // если это не дырка (равная 0)
            draw.box(x, y, svg.w, svg.w, 5);      // рисуем костяшку
            draw.text(this.desk[k], x,y);         // и номер на ней
         }
      }
}

Fifteen.prototype.getSVG = function()
{
   var draw = new Draw();                         // draw будет в svg-формате
   this.show(draw);                               // нарисовать на "нём"
   return draw.getSVG(Fifteen.svg.w*this.nX+6, Fifteen.svg.w*this.nY+6);
}

Fifteen.prototype.setCanvas = function(canvasID)
{
   var draw = new Draw(canvasID);                 // draw будет канвасом
   this.show(draw);                               // нарисовать на нём
}

<canvas id="canvas" width="200px" height="200px" ></canvas>

Ещё немного функций

Напишем функцию конвертации игрового поля в строку:

Fifteen.prototype.toString = function ()
{
   return this.desk.toString();
}

Fifteen.prototype.clone = function (f)
{
   this.hole = f.hole;
   this.move = f.move;

   if(this.desk.length !== f.desk.length){
      this.desk = new Array(f.desk.length);
      this.nX = f.nX;
      this.nY = f.nY;
   }
   for(var i = f.desk.length; i--; )
      this.desk[i] = f.desk[i];
}

Генерация ходов