БлогNot. Javascript: путь коня по доске NxN

Javascript: путь коня по доске NxN

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

Показанный ниже скрипт использует не совсем обычный подход к определению клеток, на которые может сходить конь - скрипт находит их координаты из уравнения "клеточной окружности" x2+y2=5, где x и y могут принимать целые значения от -2 до 2 включительно, кроме нуля (см. nMovesCalculate в коде).

Размеры доски выбирайте сами из списка, от 5 до 26 включительно. После выбора нажмите "Очистить", чтоб создать новую доску. Потом щёлкните по клетке, с которой конь начинает свой путь, и нажмите "Найти". Скрипт покажет ход коня визуально на доске и в текстовом виде под доской.

Если Javascript включён, но что-то не работает, проверьте, не блокируется ли скрипт каким-либо расширением браузера, например, AdBlock.

Почему такие размеры досок?

  • Для неквадартных досок менять программу лень, поменяйте сами пару строчек в коде, если нужно;
  • Верхний размер = 26 - просто потому, что кончились латинские буквы. Если придумать, как обозначать поля дальше (см. firstLetterCode в коде), можно без потерь времени получить решения для досок больших размеров;
  • Нижний размер = 5, потому что:
    • если одна сторона доски равна 3, то другая должна быть либо 4, либо не меньше 7;
    • если обе стороны больше 3, то обход коня возможен на всех досках, кроме 4x4.

Количество маршрутов коня для доски 8x8 равно значению 19 591 828 170 979 904, так что все показывать или выводить нецелесообразно :)

Для досок 5x5 и 7x7 алгоритм гарантированно найдёт полный путь, пожалуй, лишь с углового или центрального поля доски (хотя может и с других), на остальных досках должен искать с любого стартового поля. Уточнение - для некоторых стартовых полей возможны проблемы с досками нечётного размера... :)

Нужен JQuery, подключается извне с официального сервера (см. код). Точней, не очень бы он тут нужен, но для разнообразия.

Правильной закраской левого нижнего угла доски ("всегда чёрный") в этом скрипте не заморачивался, если что, это легко поправить.

Полный исходник скрипта:

<meta http-equiv="Content-Type" content="text/html; charset=windows-1251">
<div align="center" id="knightdraw"></div>
<link rel="stylesheet" type="text/css"
 href="http://code.jquery.com/ui/1.10.3/themes/smoothness/jquery-ui.css">
<script src="http://ajax.googleapis.com/ajax/libs/jquery/1.9.1/jquery.js"></script>
<script src="http://code.jquery.com/ui/1.10.3/jquery-ui.js"></script>
<style type="text/css">
 .btnLight {
  background-color: white;
  width:  32px;
  height: 32px;
 }
 .btnDark {
  background-color: lightgray;
  width:  32px;
  height: 32px;
 }
</style>

<script type="text/javascript">
 var LOG = 0; //вести ли лог в консоли (Ctrl+Shift+J в Chrome)
 var SQ_ID = "sID_"; //начало id клеток доски
 var movesCount = 0; //счётчик ходов
 var LOW_N=5;
 var HIGH_N=26; //минимальный и максимальный размеры доски

 var nWidth = 8; //размеры доски по умолчанию
 var nHeight = nWidth; 

 var firstLetterCode = 97; //первый столбец помечается кодом 'a'
 var xStart, yStart; //стартовая позиция фигуры
 var xNext, yNext; //следующая позиция фигуры
 var arrayX = [-2, -1, 1, 2]; //возможные смещения для хода коня
 var cRadius = 5; //квадрат радиуса клеточной окружности, в которую попадают ходы коня

 var s =  
  '<form name="knight_data" method="post">'+"\n"+
  '<table border="0" cellSpacing="2" cellPadding="0" align="center">'+"\n"+
  ' <caption>Путь коня с обходом всех полей доски</caption>'+"\n"+
  ' <tr><td align="center">'+"\n"+
  '  <table id="tableMain" cellSpacing="0" cellPadding="0"></table>'+"\n"+
  ' </td></tr><tr><td align="center">'+"\n"+
  '  <textarea id="statusArea" style="width:300px;height:150px;" disabled rows="6" cols="10"></textarea>'+"\n"+
  ' </td></tr><tr><td align="center">'+"\n"+
  '  <select name="N_select">';
 for (var n=LOW_N; n<=HIGH_N; n++) 
  s += '<option value="'+n+'"'+(n==nWidth?' selected':'')+'>'+n+"\n";
 s += 
  '  </select>'+"\n"+
  ' <input type="button" value="Очистить" onclick="init();"/>'+"\n"+
  ' <input type="button" value="Найти" onclick="getSolution();"/>'+"\n"+
  ' </td></tr>'+"\n"+
  '</table></form>';
 document.getElementById('knightdraw').innerHTML = s;

 function KnightCalc () {} //конструктор объекта конины
 KnightCalc.prototype.isWayLengthMoreThen1 = false;

 KnightCalc.prototype.isVisited = function (x, y) { 
  //проверка, посещалась ли клетка (true - нет, false - да)
  if (!(x>0 && x<=nWidth)) return false;
  if (!(y>=0 && y<nHeight)) return false;
  return isVisitedFromObject ($('#' + GetButtonIDString(x, y)));
 }
	
 KnightCalc.prototype.nMovesCalculate = function (x, y) { //количество ходабельных клеток для (x,y)
  var nSq = 0;
  var y0, x0, dY;
  for (var k = 0; k < arrayX.length; k++) {
   x0 = x + arrayX[k];
   dY = Math.sqrt(cRadius - Math.pow(arrayX[k], 2)); //+ или -
   for (var m = 1; m < 3; m++) {
    y0 = y + Math.pow(-1, m) * dY;
    if (this.isVisited(x0, y0)) nSq++;
   }
  }
  return nSq;
 }
		
 KnightCalc.prototype.Calculate = function (x, y) { //собственно вычисление
  var nMovesAvailable = 8; //количество доступных ходов
  var nMovesCurrent = 0;
  var nMovesCount = 0; //счётчик текущих ходов
  var movesArray = new Array (nMovesAvailable); //массив с ходами
  var objButton; //кнопка, куда писать ход
  var y0, x0, dY;
  for (var k = 0; k < arrayX.length; k++) {
   x0 = x + arrayX[k];
   dY = Math.sqrt(cRadius - Math.pow(arrayX[k], 2)); //+ или -
   for (var m = 1; m < 3; m++) {
    y0 = y + Math.pow(-1, m) * dY;                
    if (!this.isVisited (x0, y0)) continue; //вне доски или посещена - пропустить
    nMovesCount++;
    movesArray[nMovesCount] = null;
    nMovesCurrent = this.nMovesCalculate (x0, y0);
    if (LOG) 
     console.log ("Возможный ход [" + nMovesCount.toString() + "] = " +  
      buttonToChessCoord(x0, y0) + ". Вариантов следующего: " + nMovesCurrent.toString());
    if (nMovesCurrent <= nMovesAvailable) {
     nMovesAvailable = nMovesCurrent;
     movesArray[nMovesCount] = { xNew:x0, yNew:y0, nMovesFromNew:nMovesCurrent };
    }
   }	
  }
  var nOfGoodSteps = 0; 
  for (var s = 0; s < movesArray.length; s++) { //чистка массива ходов
   if (movesArray[s] != null) {
    if (movesArray[s].nMovesFromNew != nMovesAvailable) movesArray[s] = null;
    else nOfGoodSteps++;                
   }
  }
  var movesArrayCopy = new Array(nOfGoodSteps);
  var i = 0;
  for (var k=0; k<movesArray.length; k++) { //скопировать непустые элементы массива ходов
   if (movesArray[k] != null) movesArrayCopy[i++] = movesArray[k];
  }
  this.isWayLengthMoreThen1 = (movesArrayCopy.length > 1);
  return movesArrayCopy;
 }
	    
 function GetButtonIDString (x, y) { //сформировать id кнопки
  return (SQ_ID + y.toString() + "_" + x.toString());
 }

 function createBoard () { //сформировать доску
  var N0 = parseInt(document.knight_data.N_select.value);
  if (!isNaN(N0) && N0>=LOW_N && N0<=HIGH_N) {
   nWidth=N0; nHeight = nWidth; 
  }
  var tableMain = $('#tableMain');
  tableMain.empty();
  var bColorFlag = true;
  var currentRow = null;
  var currentCell = null;
  var strInnerHTML;
  for (var i = 0; i <= nHeight; i++) {
   currentRow = $("<tr>");
   for (var j = 0; j <= nWidth; j++) {
    currentCell = $('<td align="center">');
    if (i==nHeight && j == 0) {	
     currentRow.append(currentCell);
     continue;
    }
    if (i==nHeight) { //буквы столбцов
     currentCell.text(String.fromCharCode(firstLetterCode - 1 + j));
     currentRow.append(currentCell);
     continue;
    }
    if (j==0) { //цифры строк
     currentCell.html((nHeight - i).toString()+'&nbsp;');
     currentRow.append(currentCell);
     continue;
    }
    //кнопки клеток доски
    currentCell.html("<button class='"+(!bColorFlag?'btnDark':'btnLight')+
     "' id='" + GetButtonIDString(j, i) + "' onclick='OnButtonClick(this);return false;'></button>");  
    bColorFlag = !bColorFlag;
    currentRow.append(currentCell);
   }
   bColorFlag = (i%2 != 0); 
   tableMain.append(currentRow);
  }
 } 
    
 function OnButtonClick (obj) { //обработка клика по доске
  movesCount++;
  $(obj).text(movesCount.toString());
  var status = $("#statusArea");
  status.text(movesCount.toString() + ". " + idToChessCoord(obj));
  switchSquares (true);	
 }
	
 function switchSquares (mode) { 
  //закрыть (mode==true) или открыть клетки после первого клика
  for (i = 0; i < nHeight; i++)	{
   for (j = 1; j <= nWidth; j++) {
    if (mode) $('#' + GetButtonIDString(j, i)).attr ('disabled', '');
    else $('#' + GetButtonIDString(j, i)).removeAttr ('disabled');					
   }	
  }
 }
	
 function getStartCoord () { //найти стартовую позицию конины
  for (i = 0; i < nHeight; i++)	{
   for (j = 1; j <= nWidth; j++) {
    if ($('#' + GetButtonIDString(j, i)).text () == '1') {
     xStart = j; yStart = i; return;
    }
   }	
  }
 }
	
 function idToChessCoord (obj) { //id кнопки в нотацию поля доски
  var strID = $(obj).attr("id");
  var array = strID.split("_");
  return (String.fromCharCode(firstLetterCode-1+parseInt(array[2])) + "" + 
   (nHeight-parseInt(array[1])).toString());
 }
	
 function buttonToChessCoord (x, y) { //xy-координаты в нотацию поля доски
  return (idToChessCoord ($('#' + GetButtonIDString(x, y))));
 }
	
 function init() { //инициализировать данные (кнопка "Очистить")
  createBoard();
  for (i = 0; i < nHeight; i++) {
   for (j = 1; j <= nWidth; j++) {
    $('#' + GetButtonIDString(j, i)).text ('');
   }	
  }
  switchSquares (false);
  var status = $("#statusArea");
  status.text('');
  movesCount = 0;
 }
	
 function isVisitedFromObject(obj) { //посещалась ли клетка в obj (true-нет, false-да)
  var strSquareText = obj.text ();
  var bResult = (!(strSquareText != undefined && strSquareText != ''));
  return bResult;
 }
	
 function markAsVisited (obj, n) { 
  //пометить клетку n как посещённую и проверить, есть ли решение
  if (movesCount == (nHeight * nWidth))	{
   alert("Найдено полное решение");
   return true;
  }
  var bIncompleteFlag = false;
  if (n != undefined && n == 0 && movesCount == (nHeight * nWidth) - 1)	{
   if (!isVisitedFromObject (obj)) bIncompleteFlag = true;
  }
  else {
   if (n != undefined && n == 0 && movesCount > 1) bIncompleteFlag = true;
  }
  movesCount++;
  obj.text(movesCount.toString());
  updateMovesHistory (obj);
  if (bIncompleteFlag) {
   alert("Найдено неполное решение! Покрыто клеток: " + movesCount.toString());
   return true;
  }
  return false;	
 }
	
 function updateMovesHistory (obj) { //обновить запись пути в текстовом поле
  var status = $("#statusArea");
  if (movesCount == 1) status.text(movesCount.toString() + ". " + idToChessCoord(obj));
  else status.text(status.text() + " " + movesCount.toString() + ". " + idToChessCoord(obj));
 }
		    
 function movesFromOneSquare (x, y) { //Ходы из текущей клетки
  if (LOG) console.log ("Текущая позиция фигуры: " +  buttonToChessCoord (x, y));
  var nMovesAvailable = 8;
  var objKnightCalc = new KnightCalc();
  var movesArray = objKnightCalc.Calculate (x, y);
  if (movesArray.length > 0 && movesArray[0].nMovesFromNew == 0) {
   xNext = movesArray[0].xNew;
   yNext = movesArray[0].yNew;
   if (LOG) console.log ("Выполнено");
   return nMovesAvailable;
  }
  var nMovesCurrentLevel2 = 0;
  var nMovesAvailableLevel2 = 8;
  var nIndex2 = 0;
  if (movesArray.length > 1) {
   if (LOG) console.log ("Переход на уровень 2");
   var movesArray2;
   for (var p = 0; p < movesArray.length; p++) {
    if (movesArray[p] == null) continue;
    objButton = $('#' + GetButtonIDString(movesArray[p].xNew, movesArray[p].yNew));	
    objButton.text("v"); //временная пометка клетки
    movesArray2 = objKnightCalc.Calculate (movesArray[p].xNew, movesArray[p].yNew); 
    nMovesCurrentLevel2 = movesArray2[0].nMovesFromNew;
    if (nMovesCurrentLevel2 < nMovesAvailableLevel2) {
     nMovesAvailableLevel2 = nMovesCurrentLevel2;
     nIndex2 = p;
    }
    objButton.text(""); //убрать пометку
    movesArray2 = null;
   }
  }
  else if (movesArray.length == 1) {
   nMovesAvailable = nIndex2 = movesArray[0].nMovesFromNew;
   xNext = movesArray[0].xNew;
   yNext = movesArray[0].yNew;
   if (LOG) console.log ("Выбран следующий ход " +  buttonToChessCoord(xNext, yNext) + 
     ". Вариантов следующего: " + nMovesAvailable);
   return nMovesAvailable;
  }
  else return 0; 
  xNext = movesArray[nIndex2].xNew;
  yNext = movesArray[nIndex2].yNew;
  if (LOG) console.log ("Выбран следующий ход  " +  buttonToChessCoord(xNext, yNext) + 
    ". Вариантов следующего: " + nMovesAvailable);
  return nMovesAvailable;
 }

 function getSolution(x, y) { //основной метод получения решения
  if (movesCount == 0) {
   alert ("Щёлкните по доске для выбора начальной позиции коня и нажмите 'Найти' ещё раз.");
   return;
  }
  if (movesCount == 1) {
   getStartCoord ();
   x = xStart;
   y = yStart;
  }	
  var nMovesAvailable = movesFromOneSquare (x, y);
  var bResult = markAsVisited ($('#' + GetButtonIDString(xNext, yNext)), nMovesAvailable);
  if (bResult) return; //найдено
  getSolution(xNext, yNext); //или рекурсия для следующей клетки
  return;
 }

 init();
</script>
<noscript><div align="center">Извините, для работы приложения нужен включённый Javascript</div></noscript>

 Много решений задачи на всяких языках, только не на JS и не с выбором размера доски :)

 Задача Knight's tour в "Вики" (EN)

 Задача о ходе коня в "Вики" (RU)

А как запомнить маршрут коня по доске 8x8?

Для того чтобы обойти конём все шахматные клетки и ни разу не побывать дважды на одной и той же, к тому же сделать это "вслепую", начав или закончив на любой клетке по желанию "зрителя", можно благодаря мнемоническому стихотворению:

Алеет Осень Ценными Дарами,
Еще Один Животворящий День.
Хлеба Червонят Желтыми Шнурами,
Хрустальных Вод Философична Сень.

Два Вечера Цеплявшиеся Шишки
Артист Писал, Бездонна Синева.
Дорожный Шлак Целуют Червячишки,
Еще Покрыта Флоксами Трава.

Дымится Чай Эффектней Шоколада,
Фарфоры Чашек Достаются Трем,
Блондинке Девушка Дана Отрада
Форшмак Делить Холодным Острием.

Жена, Толкая Хилую Подругу,
Желает Сняться Этим Выходным,
Ценя Сама Арктическую Вьюгу,
Бросает Шар Арбуза Четверым.

Цикад Пяток, Едва Чревовещая,
Дарует Дрему Фикусам Окна.
Хотя Довольны Жаждавшие Чая,
Хозяин Шумно Жертвует Вина.

Фокстротами Шесть Девушек Пленились,
Эстрадных Танцев Фантастичней Па,
Едва Ступающий Цыпленок Вылез,
А Селезень Блуждающий Пропал.

Алеет Тело Бронзовой Осины,
Царит Теней Ажурная Длина.
Беззвучней, Чем Автомобиля Шины,
Болоту Ветер Дарит Семена.

Фонарь Восьмью Химерами Сияет,
Жук Прилетает, Хлопая, Туда.
Желанна Осень, Если Довершает
Ценнейший Отдых Бодрого Труда.

Первые буквы задают координаты ходов: Алеет Осень = А1; Ценными Дарами = С2; и т. д. В каждую строфу вставлена подсказка, помогающая не перепутать последовательность строф: ещё ОДИН, ДВА вечера, достаются ТРЁМ и т.д.

06.11.2014, 13:12 [18384 просмотра]


теги: javascript шахматы алгоритм jquery

К этой статье пока нет комментариев, Ваш будет первым