Новые задачки на шахматной доске
сейчас в списке: 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 ферзях с помощью одного вспомогательного массива, размерность которого не превышает N + 1.
#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 [3543 просмотра]