Новые задачки на шахматной доске
сейчас в списке: 28 задач на шахматной доске Многих из этих задачек нет, кажется, и у Гика в бессмертной "Математике на шахматной доске", и, увы, уже не будет, в связи с тем, что Евгения Яковлевича тоже с нами нет с 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 ходах коня
В общем, при размере доски 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)
где abs(...)
- модуль (абсолютное значение).
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); }
27. Реализовать простейший генератор шахматной позиции в нотации FEN.
Проверить строку, выданную программой, можно так: нажать в консоли Ctrl+M, выделить строчку FEN, нажать Enter, вставить в поле соответствующего скрипта, например, здесь и нажать кнопку "Показать картинку". Нюансы не учитываем, например, прописываем в FEN ход белых, но не проверяем, не под шахом ли чёрный король.
#include <iostream> #include <string> #include <cstdlib> #include <cmath> #include <ctime> using namespace std; char grid[8][8] = { {'\0','\0','\0','\0','\0','\0','\0','\0'}, {'\0','\0','\0','\0','\0','\0','\0','\0'}, {'\0','\0','\0','\0','\0','\0','\0','\0'}, {'\0','\0','\0','\0','\0','\0','\0','\0'}, {'\0','\0','\0','\0','\0','\0','\0','\0'}, {'\0','\0','\0','\0','\0','\0','\0','\0'}, {'\0','\0','\0','\0','\0','\0','\0','\0'}, {'\0','\0','\0','\0','\0','\0','\0','\0'} }; void placeKings() { int r1, r2, c1, c2; for (;;) { r1 = rand() % 8; c1 = rand() % 8; r2 = rand() % 8; c2 = rand() % 8; if (r1 != r2 && abs(r1 - r2) > 1 && abs(c1 - c2) > 1) { grid[r1][c1] = 'K'; grid[r2][c2] = 'k'; return; } } } void placePieces (const char* pieces, bool isPawn) { int n, r, c; int numToPlace = rand() % strlen(pieces); for (n = 0; n < numToPlace; ++n) { do { r = rand() % 8; c = rand() % 8; } while (grid[r][c] != 0 || (isPawn && (r == 7 || r == 0))); grid[r][c] = pieces[n]; } } string toFen() { string fen(""); char ch; int r, c, countEmpty = 0; for (r = 0; r < 8; r++) { for (c = 0; c < 8; c++) { ch = grid[r][c]; if (ch == 0) countEmpty++; else { if (countEmpty > 0) { fen += (char)(countEmpty + '0'); countEmpty = 0; } fen += ch; } } if (countEmpty > 0) { fen += (char)(countEmpty + '0'); countEmpty = 0; } fen += '/'; } fen += " w - - 0 1"; return fen; } string createFen() { placeKings(); placePieces ("PPPPPPPP", true); placePieces ("pppppppp", true); placePieces ("RNBQBNR", false); placePieces ("rnbqbnr", false); return toFen(); } int main() { srand(time(NULL)); cout << createFen() << endl; cin.get(); return 0; }
28. Задача о пьяном короле.
Аналогично (задаче 10) можно решить задачу о "пьяном короле"
В программе задачи 10 изменится только описание массива допустимых ходов
//направления хода для коня int dx[] = { -1, 0, 1, -1, 1, -1, 0, 1 }; int dy[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
и, возможно, определение начальной позиции фигуры и количества сделанных ходов в первой строке функции main
.
Так, при позиции короля в левом верхнему углу доски и единственном ходе (int row = 0, col = 0, k = 1;
) только три хода из восьми не
приведут к падению с доски, а значит, вероятность остаться на доске составит 1 - 5/ 8 = 3 / 8 = 0,375
, что и выводит изменённая программа.
Вопросы о шахматной доске, в шутку и всерьёз
Почему шахматная доска имеет размерность именно 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; }
Ну а с доской ещё больше, да притом заставленной разными фигурами, игра никогда не стала бы массовой. Это же не го со всеми одинаковыми камнями :)
Ничейны ли шахматы?
Точней, достаточно ли преимущества выступки для победы белых?
Реального ответа на этот вопрос нет, потому что перебрать все партии никакому компьютеру не по силам.
Есть моя лемма о том, как распределяются доли ничьих, побед белых и побед чёрных из всех шахматных партий.
17.02.2019, 12:30; рейтинг: 2771