Задача о расстановке ладей: ещё проще, чем с ферзями :)
Код задачи об N ферзях можно использовать и с ладьями, просто исключив из оригинального решения всё, связанное с обработкой диагоналей доски. Вот для слонов или, особенно, коней, переделок потребовалось бы больше... С другой стороны, про тех же коней и решать нечего, например, на доске 8x8 можно расставить максимум 32 коня, не угрожающих друг другу, при этом расстановок всего 2 – по белым и по чёрным полям :)
Легко заметить, что для доски размером NxN клеток существует N! решений задачи о ладьях, так что форма вывода немного изменена - теперь можно ввести в текстовое номер позиции решения и перейти к ней кнопкой "Показать". Для ускорения работы приложения значением OUTPUT = 0 отключён вывод строк с решениями в многострочное поле вывода. Допустимые размеры доски - от 2 до 10 клеток включительно (хотя код сработает и для одной клетки :), в случае доски 10x10 мы получим 10! или 3628800 решений примерно за 3-4 секунды. Для размерности доски, равной 11, время обработки становится слишком большим для яваскрипта и вызовет останов выполнения в некоторых браузерах.
Вот приложение в работе и его исходный код:
Выберите из списка размер доски 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+'"> </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=' ';
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)
Красивый "танец ладей", похожий на "прямое" вычисление определителя матрицы 4x4:
Танец 4 ладей
Наверное, можно провести аналогию задачи о размещении N ладей на доске размерностью NxN и с латинскими квадратами.
28.10.2014, 20:53 [13695 просмотров]