Расстановка слонов на шахматной доске

Как я справедливо замечал,

для слонов или, особенно, коней, переделок потребовалось бы больше

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

Используется только один цвет, так что это не последовательность A002465 и не решение соответствующей задачи с Вольфрама.

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

Также не уверен, что приложение можно счесть законченным, оно гораздо примитивней и избыточней по коду, чем про упомянутых выше ладей или про N ферзей.

Ниже показан скрипт в работе и его полный код (файл .html без тегов стандартных тегов начала и конца документа).

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

Внешняя картинка со слоном должна быть сохранена под именем wb.gif, её нужно сохранить в папку с файлом .html:

wb.gif

<div id="bishopContent"></div>
<script type="text/javascript">
var N=8; //размер доски по умолчанию
var OCCUPIED = 1;
var FREE = 0;
var ISHERE = 2;

function Bishop (N) { //Реализация проблемы о слонах
 this.N = N;
 this.N2 = this.N*this.N;
 this.NZ = Math.ceil (this.N2/2);
 this.z = new Array (this.N);
 for (var i=0; i<this.N; i++) {
  this.z[i] = new Array (this.N);
  for (var j = 0; j < this.N; j++) this.z[i][j] = FREE;
 }
 this.solutions = new Array ();
 
 this.clear = function () {
  for (var i=0; i<this.N; i++)
  for (var j = 0; j < this.N; j++) this.z[i][j] = FREE;
 }

 this.allOccupied = function () {
  var cnt = 0;
  for (var i = 0; i < this.N; i++) 
  for (var j = 0; j < this.N; j++) {
   if (this.z[i][j] != FREE) cnt++;
  }
  return cnt==this.NZ;
 }

 this.getFieldNotation = function (i,j) {
  return "(" + (i+1) + "," + (j+1) + ")";
 }

 this.getList = function () {
  var fieldsSet = new Array ();
  for (var i = 0; i < this.N; i++) 
  for (var j = 0; j < this.N; j++) 
   if (this.z[i][j] === ISHERE) fieldsSet.push(this.getFieldNotation(i,j));
  return fieldsSet;
 }

 this.set1 = function (row, col, state) {
  var r=row,c=col; //1
  while (1) {
   r--; c--;
   if (r<0 || c<0) break;
   if (this.z[r][c] === ISHERE) return false;
   this.z[r][c] = state;
  }
  var r=row,c=col; //2
  while (1) {
   r++; c++;
   if (r>this.N-1 || c>this.N-1) break;
   if (this.z[r][c] === ISHERE) return false;
   this.z[r][c] = state;
  }
  var r=row,c=col; //3
  while (1) {
   r--; c++;
   if (r<0 || c>this.N-1) break;
   if (this.z[r][c] === ISHERE) return false;
   this.z[r][c] = state;
  }
  var r=row,c=col; //4
  while (1) {
   r++; c--;
   if (r>this.N-1 || c<0) break;
   if (this.z[r][c] === ISHERE) return false;   
   this.z[r][c] = state;
  }
  return true;
 }

 this.next = function (i) {
  if (this.N % 2 == 1) return i+2;
  else {
   var col = i % this.N;
   var row = Math.floor (i / this.N);
   if (col+2 >= this.N) {
    if (row % 2 == 1) return i+1;
    else return i+3;
   }
   else return i+2;
  }
 }

 this.place = function (start) {
   if (this.allOccupied()) {
    this.solutions.push(this.getList()); 
    return true;
   }
   for (j = start; j < this.N2; j=this.next(j)) {
    var col = j % this.N;
    var row = Math.floor (j / this.N);
    if (this.z[row][col] === OCCUPIED) continue;
    this.z[row][col] = ISHERE; //add bishop at (col, row)
    if (this.set1(row,col,OCCUPIED)===false) { // save occupancy matrix
     this.set1(row,col,FREE); continue;
    }                                         
    // add threat by (col, row) to matrix
    if (this.place(this.next(j))===true) return true;
    this.set1(row,col,FREE); // revert matrix to saved matrix
    this.z[row][col] = FREE; //remove bishop from (col, row)
   }
  return false;
 }

 this.run = function() { //метод для запуска поиска
  for (var k = 0; k < this.N2; k=this.next(k)) {
   this.clear();
   this.place (k);
  }
 }

 this.debug = function(i) {
  var s='info='+i+"\n";
  for (var i = 0; i < this.N; i++) {
   for (var j = 0; j < this.N; j++) {
    s += this.z[i][j] + (j < this.N-1?' ':"\n");
   }
  }
  alert (s);
 }
}

var q;
var OUTPUT = 1; //флаг "показать все решения"
var LOW_N=1;
var HIGH_N=26; //минимальный и максимальный размеры доски
var Current = 0; //номер варианта решения для показа

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

function main (N) { //решить задачу и показать отчёт
 q = new Bishop(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;
 Current = 0;
 document.log_div.show_button.value="Показать ("+(Current+1)+")";
 if (OUTPUT) {
  for (var i=0; i<q.solutions.length; ++i) putline(q.solutions[i]);
 }
}

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 = "";
 putboard(N);
 main(N);
}

function show1() { //показать решения на доске
 if (document.log_div.show_button.disabled==false) {
  var solution = ''+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="wb.gif" alt="">';  
  }
  if (Current<q.solutions.length-1) Current++; else Current=0;
  document.log_div.show_button.value="Показать ("+(Current+1)+")";
 }
}

//вывести форму приложения
var s =
 '<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="10" cols="80" readonly></textarea>'+"\n"+
 ' <br>N='+"\n"+
 ' <select name="N_select">';
for (var n=LOW_N; n<=HIGH_N; n++) 
 s += '<option value="'+n+'"'+(n==N?' selected':'')+'>'+n;
s += '</select>';
s +=
 '<input type="button" onclick="click1();" value="Выполнить"/>'+"\n"+
 '<input name="show_button" type="button" onclick="show1();" value="Показать" disabled/></form></div>';
document.getElementById('bishopContent').innerHTML = s;
</script>
<noscript><div align="center">Извините, для работы приложения нужен включённый Javascript</div></noscript>

23.12.2017, 20:48 [2868 просмотров]