БлогNot. Задача о расстановке ладей: ещё проще, чем с ферзями :)

Задача о расстановке ладей: ещё проще, чем с ферзями :)

Код задачи об N ферзях можно использовать и с ладьями, просто исключив из оригинального решения всё, связанное с обработкой диагоналей доски. Вот для слонов или, особенно, коней, переделок потребовалось бы больше... С другой стороны, про тех же коней и решать нечего, например, на доске 8x8 можно расставить максимум 32 коня, не угрожающих друг другу, при этом расстановок всего 2 – по белым и по чёрным полям :)

Легко заметить, что для доски размером NxN клеток существует N! решений задачи о ладьях, так что форма вывода немного изменена - теперь можно ввести в текстовое номер позиции решения и перейти к ней кнопкой "Показать". Для ускорения работы приложения значением OUTPUT = 0 отключён вывод строк с решениями в многострочное поле вывода. Допустимые размеры доски - от 2 до 10 клеток включительно (хотя код сработает и для одной клетки :), в случае доски 10x10 мы получим 10! или 3628800 решений примерно за 3-4 секунды. Для размерности доски, равной 11, время обработки становится слишком большим для яваскрипта и вызовет останов выполнения в некоторых браузерах.

Вот приложение в работе и его исходный код:

Извините, для работы приложения нужен включённый Javascript

Выберите из списка размер доски N, нажмите "Выполнить", а потом "Показать". Если Javascript и картинки включены, но что-то не работает, проверьте, не блокируется ли скрипт каким-либо расширением браузера, например, AdBlock

<meta http-equiv="Content-Type" content="text/html; charset=windows-1251">
<script type="text/javascript">
var ISHERE = -1; //метка "фигура тут"
var OUTPUT = 0; //флаг "показать все решения"
var LOW_N=2;
var HIGH_N=10; //минимальный и максимальный размеры доски
var N=8; //размер доски по умолчанию
var Current = 0; //номер варианта решения для показа
var q; //будущие решения

function Rook(N) { //Реализация проблемы об N ладьях
 this.N = N;
 this.columns = new Array(this.N); //столбцы
 this.solutions  = new Array (); //решения

 this.run = function() { //метод для запуска поиска
  this.calculate (0);
 }

 this.calculate = function (row) { //метод для поиска всех возможных решений
  for (var column=0; column < this.N; ++column) {
   if (this.columns[column] >= 0) continue; //текущий столбец бьётся, продолжить
   this.columns[column] = row; 
   if (row == this.N - 1) this.solutions.push(this.columns.slice()); //найдена последняя строка - есть решение
   else this.calculate(row + 1); //иначе рекурсия
   this.columns[column] = ISHERE;
  }
 }
}

function getline (solution) { //сформировать строку с решением
 var line = "";
 for (var j=0; j<solution.length; ++j) line += "(" + (j+1) + "," + (solution[j]+1) + ")";
 return line;       
}

function putline (text) { //добавить строку в лог
 document.log_div.log_area.value += text + "\n";
}

function main (N) { //решить задачу и показать отчёт
 q = new Rook(N);
 putline("Размер доски: " + q.N + "x" + q.N);
 var start = new Date().getTime();
 q.run();
 putline("Время вычисления: " + (new Date().getTime() - start) + "мс");
 putline("Количество решений: " + q.solutions.length);
 document.log_div.show_button.disabled=false;
 document.log_div.num_solution.disabled=false;
 Current = 0;
 if (OUTPUT) {
  for (var i=0; i<q.solutions.length; ++i) {
   var solution = getline(q.solutions[i]);
   putline(solution);
  }
 }
}

function putboard (N) { //метод для рисования шахматной доски на Javascript
 var s='<table align="center" cellpadding="0" cellspacing="0" border="1">'+"\n";
 var color='white'; if (N%2) color='black';
 for (var i=1; i<=N; i++) {
  s+='<tr>'+"\n";
  for (var j=1; j<=N; j++) {
   s+='<td align="center" valign="middle" width="32" height="32" nowrap style="background:'+
      color+'; color: red; font-weight: bold;"><span id="board_'+i+'_'+j+'">&nbsp;</span></td>';
   color = (color=='white'?'black':'white');
  }
  s+='</tr>'+"\n";
  color = (N%2==0?(i%2?'black':'white'):(i%2?'white':'black'));
 }
 s+='</table>';
 document.getElementById('board_div').innerHTML=s;
 
}

function click1() { //главная функция
 var N0 = parseInt(document.log_div.N_select.value);
 if (!isNaN(N0) && N0>=LOW_N && N0<=HIGH_N) N=N0;
 document.log_div.log_area.value = "";
 document.log_div.num_solution.value = "1";
 putboard(N);
 main(N);
}

function show1() { //показать решения на доске
 if (document.log_div.show_button.disabled==false) {
  var c0 = parseInt(document.log_div.num_solution.value);
  if (!isNaN(c0) && c0>0 && c0<=q.solutions.length) {
   Current=c0-1;
  }
  else {
   document.log_div.num_solution.value=''+(Current+1);  
   alert ('Неверный номер решения, нужен от 1 до '+q.solutions.length);
   return;
  }
  var solution = getline(q.solutions[Current]);
  var reg = new RegExp("([0-9]+,[0-9]+)","g"); 
  var fields = solution.match(reg);
  for (var i=1; i<=N; i++) for (var j=1; j<=N; j++) document.getElementById('board_'+i+'_'+j).innerHTML='&nbsp;';
  for (var i=0; i<fields.length; i++) {
   var xy = fields[i].split(',');
   document.getElementById('board_'+xy[0]+'_'+xy[1]).innerHTML='<img src="wr.gif" alt="">';   
  }
  if (Current<q.solutions.length-1) Current++; else Current=0;
  document.log_div.num_solution.value=''+(Current+1);
 }
}

//вывести форму приложения
document.writeln (
 '<div align="center" id="board_div" style="color: red"></div>'+"\n"+
 '<div align="center">'+"\n"+
 '<form name="log_div">'+"\n"+
 ' <textarea name="log_area" rows="4" cols="50" readonly></textarea>'+"\n"+
 ' <br>N='+"\n"+
 ' <select name="N_select">'
);
for (var n=LOW_N; n<=HIGH_N; n++) 
 document.writeln ('<option value="'+n+'"'+(n==N?' selected':'')+'>'+n);
document.writeln ('</select>');
document.writeln (
 '<input type="button" onclick="click1();" value="Выполнить"/>'+"\n"+
 'Решение номер <input type="text" name="num_solution" size="8" maxlength="7" value="1" disabled/>'+"\n"+
 '<input name="show_button" type="button" onclick="show1();" value="Показать" disabled/></form></div>'
);
</script>
<noscript><div align="center">Извините, для работы приложения нужен включённый Javascript</div></noscript>

Картинка с ладьёй (файл wr.gif):

wr.gif (29x29)
wr.gif (29x29)

Красивый "танец ладей", похожий на "прямое" вычисление определителя матрицы 4x4:

Танец 4 ладей
Танец 4 ладей

Наверное, можно провести аналогию задачи о размещении N ладей на доске размерностью NxN и с латинскими квадратами.

28.10.2014, 20:53 [13517 просмотров]


теги: javascript картинка числа шахматы

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