БлогNot. Новые задачки на шахматной доске

помощь сортировка по рейтингу 🔍 поиск ≡ статистика 🏠 домой

Новые задачки на шахматной доске

сейчас в списке: 26 задач на шахматной доске Многих из этих задачек нет, кажется, и у Гика в бессмертной "Математике на шахматной доске", и, увы, уже не будет, в связи с тем, что Евгения Яковлевича тоже с нами нет с 2016-го года.

В статье приведены не только программки, но и просто формулы или наброски, из которых, впрочем, легко сделать программки.

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

1. На сколько различных полей может перейти шахматный слон за один ход?

Если исходную позицию слона обозначить (r,c) и нумеровать клетки шахматной доски слева направо (c) и сверху вниз (r) с единицы, то имеем:

Слева вверху: min (r, c) – 1 полей для хода

Справа вверху: min (r, 9 – c) – 1

Слева внизу: 8 – max (r, 9 – c)

Справа внизу: 8 – max (r, c)

(для доски 8 x 8). Сложите эти 4 значения, чтобы получить ответ. После несложного преобразования, для поля с координатами (r,c) на доске размерностью n x n можно получить вполне изящную формулу для количества ходов слона с этого поля: B(r,c) = 2*(n-1) - max(r,c) + min(r,c) - max(r,n-c+1) + min(r,n-c+1)

2. Может ли слон взять пешку?

При нумерации клеток как в задаче 1 и позиции слона (bX,bY), а пешки (pX,pY), имеем ответ "может", если

pX - bX == pY - bY или bX - pX == pY - bY

Иначе не может.

3. Сколько не атакующих друг друга слонов можно разместить на шахматной доске размерностью n x n ?

При n = 1 - одного, а при n, большем единицы - ровно 2 * (n – 1) слонов (например, расставьте n слонов на верхней горизонтали доски и (n-2) - на нижней).

Про слонов одного цвета, не угрожающих друг друг и бьющих все поля доски, решалось вот в этой заметке.

4. Сколько полей доски может достигнуть шахматный король ровно за m ходов?

Если король находится в позиции (r,c), мы можем найти координаты левой верхней (r1,c1) и правой нижней (r2,c2) клеток, в которые он мог бы попасть за m ходов: 

r1 = r - m; if (r1 < 1) r1 = 1; 
r2 = r + m; if (r2 > 8) r2 = 8; 
c1 = c - m; if (c1 < 1) c1 = 1; 
c2 = c + m; if (c2 > 8) c2 = 8;

Потом останется вычислить значение (r2-r1+1)*(c2-c1+1)

Можно отнять от этого значения единицу, если исходное поле не считается.

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

Если исходные координаты короля (r1,c1), а целевые (r2,c2), имеем ответ max (|c2-c1|,|r2-r1|), где |...| - модуль (абсолютное значение).

6. На сколько различных между собой полей может встать шахматный конь, сделав ровно m ходов?

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

задача об m ходах коня
задача об m ходах коня

В общем, при размере доски n x n (нумерация полей - с единицы) и начальной позиции коня (r, c) имеем

#include <iostream> 
#include <map> 
using namespace std;

map <pair<int, int>, int> mp;

int solve(int r, int c, int m, int n) {
 if (m == 0 && mp[make_pair(r, c)] == 0) {
  mp[make_pair(r, c)] = 1;
  return 1;
 }
 int res = 0;
 if (m > 0) {
  int dx[] = { -2, -1, 1, 2, -2, -1, 1, 2 }; //ходы
  int dy[] = { -1, -2, -2, -1, 1, 2, 2, 1 }; //коня
  for (int k = 0; k < 8; k++) {
   if ((dx[k] + r) > 0
    && (dx[k] + r) < n 
    && (dy[k] + c) > 0
    && (dy[k] + c) < n) {
    res += solve (dx[k] + r, dy[k] + c,  m - 1, n);
   }
  }
 }
 return res;
}

int main() {
 int r = 1, c = 1, m = 2, n = 8;
 cout << solve (r, c, m, n);
 cin.get();
 return 0;
}

(здесь и далее программы на C++ запускались в консоли Visual Studio 2015).

7. Сколько шахматных коней можно разместить на доске размерностью n x n так, чтобы они не угрожали друг другу?

Если расставлять коней "по шашечному принципу", а это, видимо, оптимальный способ, то имеем

при чётном n: n2/2

при нечётном n: (n-1)2/2 + n

Подумайте, как получить общую формулу для количества расстановок этого максимального количества коней, скажем, на доске 3x3 таких расстановок две:

задача о расстановке максимального количества коней
задача о расстановке максимального количества коней

на доске 8x8 расставить 32 не угрожающих друг другу можно, очевидно, двумя способами (по белым или по чёрным клеткам), а как насчёт доски 5x5 и максимально возможных на ней 13 коней?

P.S. Наверное, вот как. Несложные формулы для доски размерностью n x m видны из приложенной программки. 

#include <iostream>
#include <algorithm>
using namespace std;

int max_knight(int n, int m) {
 if (m == 1 || n == 1) return max(m, n); //доска 1 x m или n x 1
 else if (m == 2 || n == 2) { //доска шириной или высотой 2
  int c = 0;
  c = (max(m, n) / 4) * 4;
  if (max(m, n) % 4 == 1) c += 2;
  else if (max(m, n) % 4 > 1) c += 4;
  return c;
 }
 else return (((m * n) + 1) / 2); //общий случай
}


int main() {
 int n = 5, m = 5;
 cout << max_knight(n, m);
 cin.get();
 return 0;
}

8. Какое минимальное количество ходов должен сделать шахматный конь, чтобы достигнуть указанного поля доски?

При исходной позиции коня (r1,c1) и целевой позиции (r2,c2) решим задачу программно, во избежание километровых формул.

#include <iostream> 
#include <cstdlib> 
#include <algorithm> 
using namespace std;

int board[8][8] = { 0 };

int getsteps(int c1, int r1, int c2, int r2) {
 if (c1 == c2 && r1 == r2) return board[0][0]; //уже на цели
 else {
  if (board[abs(c1 - c2)][abs(r1 - r2)] != 0)
   return board[abs(c1 - c2)][abs(r1 - r2)];
  else {
   int x1, y1, x2, y2;
   if (c1 <= c2) {
    if (r1 <= r2) {
     x1 = c1 + 2; y1 = r1 + 1; x2 = c1 + 1; y2 = r1 + 2;
    }
    else {
     x1 = c1 + 2; y1 = r1 - 1; x2 = c1 + 1; y2 = r1 - 2;
    }
   }
   else {
    if (r1 <= r2) {
     x1 = c1 - 2; y1 = r1 + 1; x2 = c1 - 1; y2 = r1 + 2;
    }
    else {
     x1 = c1 - 2; y1 = r1 - 1; x2 = c1 - 1; y2 = r1 - 2;
    }
   }
   board[abs(c1 - c2)][abs(r1 - r2)] =
    min (getsteps(x1, y1, c2, r2),getsteps(x2, y2, c2, r2)) + 1;
   board[abs(r1 - r2)][abs(c1 - c2)] = board[abs(c1 - c2)][abs(r1 - r2)];
   return board[abs(c1 - c2)][abs(r1 - r2)];
  }
 }
}

int main() {
 int c1, r1, c2, r2, result;

 const int n = 8;

 c1 = 8; r1 = 8; c2 = 7; r2 = 7; //h1 - g2, 4 хода
  //координаты (столбец, строка), нумеруем с единицы

 //углы:
 if ((c1 == 1 && r1 == 1 && c2 == 2 && r2 == 2) ||
     (c1 == 2 && r1 == 2 && c2 == 1 && r2 == 1)) result = 4;
 else if ((c1 == 1 && r1 == n && c2 == 2 && r2 == n - 1) ||
          (c1 == 2 && r1 == n - 1 && c2 == 1 && r2 == n)) result = 4;
 else if ((c1 == n && r1 == 1 && c2 == n - 1 && r2 == 2) ||
          (c1 == n - 1 && r1 == 2 && c2 == n && r2 == 1)) result = 4;
 else if ((c1 == n && r1 == n && c2 == n - 1 && r2 == n - 1) ||
          (c1 == n - 1 && r1 == n - 1 && c2 == n && r2 == n)) result = 4;
 else {
  // board[a][b], где a, b - разница c1 & c2 , r1 & r2
                   board[0][1] = 3; board[0][2] = 2;
  board[1][0] = 3; board[1][1] = 2; board[1][2] = 1;
  board[2][0] = 2; board[2][1] = 1;
  result = getsteps(c1, r1, c2, r2);
 }

 cout << result;
 cin.get();
 return 0;
}

9. Найти количество полей, на которые может пойти ферзь на пустой доске размерностью n x n.

К решению задачи 1 о количестве полей для слона прибавьте 2 * (n - 1) - количество полей для ладьи.

10. Задача о пьяном коне. На шахматной доске размерностью n x n шахматный конь, находящийся в начальной позиции (r, c) делает ровно k шагов, каждый раз выбирая случайное из 8 возможных направлений хода. Какова вероятность того, что конь останется на шахматной доске после выполнения k ходов, при условии, что он не сможет вернуться на доску после того, как покинет её?

А ведь наверняка можно решить аналитически методами теории вероятностей :)

#include <iostream> 
using namespace std;

const int N = 8; //размерность доски

//направления хода для коня
int dx[] = { 1, 2, 2, 1, -1, -2, -2, -1 };
int dy[] = { 2, 1, -1, -2, -2, -1, 1, 2 };

bool onBoard(int x, int y) { //конь на доске?
 return (x >= 0 && x < N && y >= 0 && y < N);
}

double findSolution(int cx, int cy, int steps) {
 double D[N][N][N+1]; //вспомогательный массив

 //Для нуля ходов все вероятности равны 1:
 for (int i = 0; i < N; i++)
 for (int j = 0; j < N; j++) D[i][j][0] = 1;

 for (int s = 1; s <= steps; s++) { //для каждого хода
  for (int x = 0; x < N; x++) { //для каждой позиции после s ходов
   for (int y = 0; y < N; y++) {
    double prob = 0.0;
    for (int i = 0; i < 8; i++) { //для каждого достижимого поля
     int nx = x + dx[i];
     int ny = y + dy[i];
     if (onBoard(nx, ny)) prob += D[nx][ny][s-1] / 8.0;
    }
    D[x][y][s] = prob;
   }
  }
 }
 return D[cx][cy][steps];
}

int main() {
 int row = 4, col = 4, k = 8;
 cout << findSolution(col, row, k) << endl;
 cin.get();
 return 0;
}

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

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

 Ссылка не в тему: деревья и птицы, читайте Брябрина

11. Сколько не угрожающих друг другу королей можно разместить на шахматной доске размерностью n x n?

Для не-угрожающих друг другу королей при размерности доски n>0 имеем формулу ((n+1) div 2)2, где div - деление нацело с отбрасыванием остатка (3 div 2 == 1)

А вот количество способов расставить n не атакующих друг друга королей на доске размерностью n x n найдёте разве что здесь (последовательность приведена, начиная с размера доски 0x0).

12. Сколько королей одного цвета нужно, чтобы контролировать все поля шахматной доски размерностью n x n?

При n>0 имеем для размерностей n = 1, 2, 3 одного короля, для n = 4, 5, 6 - четырёх, для n = 7, 8, 9 - девятерых, и т.д., в общем виде ((n+2) div 3)2 где div - деление нацело с отбрасыванием остатка (3 div 2 == 1)

Формулу для не квадратной доски размерностью m x n можно записать, например, в виде ((m+2) div 3) * ((n+2) div 3)

А вот задачу о доминировании ферзей над всеми полями доски n x n и количестве способов расстановки доминирующих ферзей так легко не решить.

13. Сколько всего квадратов на шахматной доске размерностью n x n?

Подвох в том, что нужно учесть не только отдельные поля, но и квадраты размером 2x2, 3x3 и т.д. до nxn включительно.

Решение можно найти как сумму ряда или по аналитической формуле, вот оба варианта расчёта для n=8:

количество квадратов на шахматной доске
количество квадратов на шахматной доске

14. А сколько прямоугольников (включая квадраты) может содержаться на шахматной доске размерностью n x m?

В отличие от задачи 13, учитываем прямоугольники из 1x2, 2x3 и т.д. полей.

Формулы для квадратной и не-квадратной досок при n=8 и n=10, m=15 показаны ниже:

количество прямоугольников на шахматной доске
количество прямоугольников на шахматной доске

15. Какое максимальное количество разрезов по границам полей можно сделать на шахматной доске размерностью n x m так, чтобы она не распалась на две части?

Например, вот разрезы на доскаx 2x2 и 2x3:

разрезы шахматной доски по границам полей
разрезы шахматной доски по границам полей

Общая формула очень проста: (n-1)*(m-1) разрезов.

А ещё это количество стенок единичной длины, которые нужны, чтобы построить односвязный лабиринт.

16. Задача о минимальном количестве коней, нужных, чтобы атаковать все поля доски размерностью n x n, тоже интересна и не поддаётся аналитической формуле, можно посмотреть вот здесь количество коней для размерностей доски n=1,2,... и т.д. или вот тут с количествами различных между собой решений.

17. Для шахматной доски размерностью n x n (для простоты примем n>4) найти количество ходов коня в зависимости от его координат (r,c), координаты считаются как в задаче 1.

Сначала выведем таблицу ходов коня, полученную "экстенсивно", то есть, прямым вычислением для каждого поля. 

#include <iostream>
#include <iomanip>
using namespace std;

int main() {
 int dxy[8][2] = {
  {-2,-1},{-2 ,1 },{-1 ,2 },{1 ,2 },{2 ,1 },{2 ,-1 }, {1,-2}, {-1,-2}
 };
 for (int r =1; r<9; r++) {
  cout << endl;
  for (int c = 1; c<9; c++) {
   int steps=0;
   for (int d = 0; d < 8; d++) {
    int r1 = r + dxy[d][0];
    int c1 = c + dxy[d][1];
    if (r1<1 || r1>8 || c1<1 || c1>8) continue;
    steps++;
   }
   cout << setw(2) << steps;
  }
 }
 cin.get(); return 0;
}

Вывод этой программы: 

2 3 4 4 4 4 3 2
3 4 6 6 6 6 4 3
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
3 4 6 6 6 6 4 3
2 3 4 4 4 4 3 2

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

Эта функция применяет "штрафы" за близость коня к краям доски и делает небольшое количество сравнений, которое ещё можно сократить, займитесь этим самостоятельно. 

#include <iostream>
#include <iomanip>
using namespace std;
const int n = 8;

int knightMoves(int r, int c) { //корректно при n>4
 int m = 8;
 if (r < 3 || r > n - 2) m -= 2;
 if (c < 3 || c > n - 2) m -= 2;
 if (r == 1 || r == n ) m -= 2;
 if (c == 1 || c == n) m -= 2;
 if (m == 2) return 3;
 if (m == 0) return 2;
 return m;
}
int main() {
 for (int r = 1; r<n+1; r++) {
  cout << endl;
  for (int c = 1; c<n+1; c++) {
   int steps = knightMoves(r,c);
   cout << setw(2) << steps;
  }
 }
 cin.get(); return 0;
}

18. Есть ли простая общая формула для определения цвета поля на шахматной доске размерностью n x n, если считать, как и принято по правилам, что слева от игрока поле на нижней горизонтали должно быть чёрным?

При нумерации полей слева направо (j) и сверху вниз (i), начиная с нуля, имеем 

если (
      (i+j)%2==1 и n%2==0) или
      (i+j)%2==0 и n%2==1)
     ) то поле чёрное
иначе поле белое

("%" - взятие остатка от деления).

19. Как определить количество белых и чёрных полей для квадратной доски размерностью n x n ? А для прямоугольной?

Как и в предыдущей задаче считаем, что доска всегда "правильная", то есть первое поле первой горизонтали слева от игрока - чёрное.

Если доска квадратная, то всё очень просто: 

если n % 2 == 0
  то Б = Ч = n^2 / 2
иначе
     Б = (n^2 - 1) / 2
     Ч = (n^2 + 1) / 2

где "%" - взятие остатка от деления, "^" - возведение в степень.

Для прямоугольной доски из n x m полей, если хотя бы одна из размерностей чётная, то чётно и произведение n*m, имеем поровну белых и чёрных полей, по n*m/2. Если же и n, и m нечётны, получаем формулы Ч = (n*m+1)/2, Б = (n*m-1)/2.

20. Как связаны допустимые для хода коня поля доски и уравнение окружности?

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

21. Может ли ферзь, находящийся на поле (qR, qC), атаковать поле (oR, oC)?

Поля нумеряются слева направо и сверху вниз. Ответ "да", если выполняется условие

qR == oR или qC == oC или abs(qR - oR) == abs(qC - oC)

где |...| - модуль (абсолютное значение).

22. Расставить K коней на доске размерностью M x N так, чтобы они не угрожали друг другу.

В отличие от задач 6, 7 здесь мы хотим получить сами расстановки коней. Уместным будет рекурсивное решение.

#include <iostream>
using namespace std;

int m, n, k;
int cnt = 0;

void makeBoard (char** board) {
 for (int i = 0; i < m; i++) 
 for (int j = 0; j < n; j++) 
  board[i][j] = '_';
}

void displayBoard (char** board) {
 cout << endl << endl;
 for (int i = 0; i < m; i++) {
  for (int j = 0; j < n; j++) cout << " " << board[i][j] << " ";
  cout << endl;
 }
}

void attack (int i, int j, char a, char** board) { //атаковать с поля (i,j)
 if ((i + 2) < m && (j - 1) >= 0) board[i + 2][j - 1] = a;
 if ((i - 2) >= 0 && (j - 1) >= 0) board[i - 2][j - 1] = a;
 if ((i + 2) < m && (j + 1) < n) board[i + 2][j + 1] = a;
 if ((i - 2) >= 0 && (j + 1) < n) board[i - 2][j + 1] = a;
 if ((i + 1) < m && (j + 2) < n) board[i + 1][j + 2] = a;
 if ((i - 1) >= 0 && (j + 2) < n) board[i - 1][j + 2] = a;
 if ((i + 1) < m && (j - 2) >= 0) board[i + 1][j - 2] = a;
 if ((i - 1) >= 0 && (j - 2) >= 0) board[i - 1][j - 2] = a;
}

bool canPlace (int i, int j, char** board) { //если (i,j) пусто, поставить коня
 if (board[i][j] == '_') return true;
 else return false;
}

void place (int i, int j, char k, char a, char** board, char** new_board) {
 //поставить коня на (u,j)
 for (int y = 0; y < m; y++) 
 for (int z = 0; z < n; z++) 
  new_board[y][z] = board[y][z];
 new_board[i][j] = k;
 attack(i, j, a, new_board);
}

void solve (int k, int sti, int stj, char** board) { //основная функция
 if (k == 0) {
  displayBoard(board); cnt++;
 }
 else {
  for (int i = sti; i < m; i++) {
   for (int j = stj; j < n; j++) {
    if (canPlace(i, j, board)) {
     char** new_board = new char * [m];
     for (int x = 0; x < m; x++) new_board[x] = new char[n];
     place(i, j, 'K', 'A', board, new_board);
     solve(k - 1, i, j, new_board);
     for (int x = 0; x < m; x++) delete[] new_board[x];
     delete[] new_board;
    }
   }
   stj = 0;
  }
 }
}


int main() {
 m = 3, n = 3, k = 5;

 char **board = new char * [m];
 for (int i = 0; i < m; i++) board[i] = new char[n];
 makeBoard (board);

 solve(k, 0, 0, board);

 cout << endl << "Total solution(s): " << cnt;
 cin.get();
 return 0;
}
 K  A  K
 A  K  A
 K  A  K


 A  K  A
 K  K  K
 A  K  A

Total solution(s): 2

23. Проверить, правильная ли заданная целочисленной матрицей шахматная доска N x N.

Доска правильна, если любые 2 соседних по горизонтали или вертикали клетки окрашены в противоположные цвета.

#include <iostream>
using namespace std;

int main() {
 const int n = 3;
 int c[n][n] = { 
  { 1, 0, 1 },
  { 0, 1, 0 },
  { 1, 0, 1 }
 };
 
 //Проверка
 int X[] = { 0, -1, 0, 1 };
 int Y[] = { 1, 0, -1, 0 };
 bool isValid = true;
 for (int i = 0; i < n; i++) 
 for (int j = 0; j < n; j++) 
 for (int k = 0; k < 4; k++) {
  int newX = i + X[k];
  int newY = j + Y[k];
  if (newX < n && newY < n && newX >= 0 && 
      newY >= 0 && c[newX][newY] == c[i][j]) isValid = false;
 }
 
 cout << (isValid == true ? "Yes" : "No");
 cin.get();
 return 0;
}

24. Решить задачу об N ферзях со сложностью алгоритма O(N)

#include <iostream>
using namespace std;

#define MAX 10 
int arr[MAX+1], no;

bool canPlace(int k, int i) {
 for (int j = 1; j <= k - 1; j++) 
  if (arr[j] == i || (abs(arr[j] - i) == abs(j - k))) return false;
 return true;
}

void display(int n) {
 cout << "Solution number " << ++no << endl;
 for (int i = 1; i <= n; i++) {
  for (int j = 1; j <= n; j++) {
   if (arr[i] != j) cout << "\t_";
   else cout << "\tQ";
  }
  cout << endl;
 }
}

void nQueens(int k, int n) {
 for (int i = 1; i <= n; i++) {
  if (canPlace (k, i)) {
   arr[k] = i;
   if (k == n) display (n);
   else nQueens(k + 1, n);
  }
 }
}

int main() {
 int n = 5;
 nQueens(1, n);

 cin.get();
 return 0;
}

25. Подсчитать количество возможных ходов коня с поля (p, q) доски размерностью n x m.

В отличие от задачи 17, доска не обязана быть квадратной и задано поле расположения коня.

#include <iostream>
using namespace std;

const int n = 4, m = 4;

int findPossibleMoves(int mat[n][m], int p, int q) {
 int X[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
 int Y[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
 int cnt = 0;
 for (int i = 0; i < 8; i++) {
  int x = p + X[i];
  int y = q + Y[i];
  if (x >= 0 && y >= 0 && x < n && y < m && mat[x][y] == 0) cnt++;
 }

 // Return number of possible moves 
 return cnt;
}

int main() {
 int mat[n][m] = { 
  { 1, 0, 1, 0 },
  { 0, 1, 1, 1 },
  { 1, 1, 0, 1 },
  { 0, 1, 1, 1 } 
 };

 int p = 2, q = 2;

 cout << findPossibleMoves(mat, p, q);

 cin.get();
 return 0;
}

26. Сколько есть способов разместить на доске N x N ровно K слонов так, чтобы ни один из них не угрожал другому?

Решение, основанное на методах динамического программирования, может быть таким:

#include <iostream>
using namespace std;

int squares(int i) { //количество полей по диагонали i
 if ((i & 1) == 1) return i / 4 * 2 + 1;
 else return (i - 1) / 4 * 2 + 2;
}

long int bishop_placements(int n, int k, long int **dp) {
 if (k > 2 * n - 1) return 0;
 for (int i = 0; i < n * 2; i++) dp[i][0] = 1;
 dp[1][1] = 1;
 for (int i = 2; i < n * 2; i++) {
  for (int j = 1; j <= k; j++)
   dp[i][j] = dp[i - 2][j] + dp[i - 2][j - 1] * (squares(i) - j + 1);
 }
 long int res = 0;
 for (int i = 0; i <= k; i++) {
  res += dp[n * 2 - 1][i] * dp[n * 2 - 2][k - i];
 }
 return res;
}

int main() {
 int n = 4;
 int k = 3;
 long int **dp = new long int * [n * 2]; //таблица для расчета
 for (int i = 0; i < n * 2; i++) {
  dp[i] = new long int [k + 1];
  for (int j = 0; j < k + 1; j++) dp[i][j] = 0;
 }
 long int res = bishop_placements(n, k, dp);
 cout << res;
 cin.get();
 return(0);
}
Вопросы о шахматной доске, в шутку и всерьёз

Почему шахматная доска имеет размерность именно 8x8?

Если считать в целых числах и в пределах первого десятка, соотношения 8/5 и 5/3 наиболее близки к золотому сечению.

//Программка для иллюстрации этой мысли
#include <iostream> 
#include <vector>
#include <algorithm>
#include <cmath> 
using namespace std;

bool sortPairs (const pair<double, const pair<int, int>> &i,
                const pair<double, const pair<int, int>> &j) {
 return (i.first > j.first); 
 //по убыванию модуля разности между отношением a/b и константой золотого сечения
}

int main() {
 const double gold = (sqrt(5)+1.)/2.;
 double minabs = 11;
 int a0, b0;
 vector <pair<double, pair<int, int>>> v;
 for (int a = 10; a > 1; a--)
 for (int b = a ; b > 1; b--) {
  double d = abs((double)a / b - gold);
  v.push_back(make_pair(d, make_pair(a,b)));
 }
 sort(v.begin(), v.end(), sortPairs);
 for (int i = 0; i<v.size(); i++) {
  cout << v[i].first << " " << 
   v[i].second.first << " " << v[i].second.second << endl;
 }
 cin.get();
 return 0;
}

Ну а с доской ещё больше, да притом заставленной разными фигурами, игра никогда не стала бы массовой. Это же не го со всеми одинаковыми камнями :)

Ничейны ли шахматы?

Точней, достаточно ли преимущества выступки для победы белых?

Реального ответа на этот вопрос нет, потому что перебрать все партии никакому компьютеру не по силам.

Есть моя лемма о том, как распределяются доли ничьих, побед белых и побед чёрных из всех шахматных партий.

теги: числа математика c++ алгоритм шахматы список

17.02.2019, 12:30; рейтинг: 1374