Новые задачки на шахматной доске
сейчас в списке: 41 задача на шахматной доске Многих из этих задачек нет, кажется, и у Гика в бессмертной "Математике на шахматной доске", и, увы, уже не будет, в связи с тем, что Евгения Яковлевича тоже с нами нет с 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;
}
Задачу 24 с дополнительными ограничениями, состоящими в том, что задан список "стоп-клеток", куда ферзи не могут вставать, я решал вот тут, но что-то не уверен в правильности выводов и пока сюда не добавляю.
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, что и выводит изменённая программа.
29. Кратчайший путь коня.
Найти минимальное количество ходов коня, требуемое для достижения поля dest с поля src. Если решение не найдено, сообщить об этом. Доска предполагается квадратной и размерностью N × N.
Требуется также показать любой из возможных путей коня минимальной длины.
В отличие от задачи 8, определяем не только количество ходов, но и сами маршруты. Плюс задача служит хорошей иллюстрацией для применения метода BFS, он же поиск в ширину.
#include <iostream>
#include <iomanip>
#include <set>
#include <queue>
#include <climits>
int row[] = { 2, 2, -2, -2, 1, 1, -1, -1 }; //Смещения для
int col[] = { -1, 1, 1, -1, 2, -2, 2, -2 }; //возможных ходов коня по доске
bool isValid (int x, int y, int N) { //true, если (x, y) - валидные координаты
return (x >= 0 && x < N) && (y >= 0 && y < N);
}
struct Node { //Узел для алгоритма BFS https://en.wikipedia.org/wiki/Breadth-first_search
int x, y, dist; //координаты x,y поля, расстояния от цели
int x0, y0; //предыдущие координаты
Node(int x, int y, int dist = 0, int x0 = -1, int y0 = -1) :
x(x), y(y), dist(dist), x0(x0), y0(y0) {} //Конструктор узла
bool operator < (const Node& o) const {
//Компаратор, определяющий итоговое положение узлов во множестве посещённых полей
return dist < o.dist || dist == o.dist && (x < o.x || (x == o.x && y < o.y));
}
bool operator == (const Node & o) const { //Компаратор для будущего поиска полей
return x == o.x && y == o.y && dist == o.dist;
}
};
Node findShortestDistance(int N, Node src, Node dest, std::set <Node> &visited) {
//Вернуть минимальное количество ходов коня из src в dest,
//варианты путей записать в visited
std::queue <Node> q; //Очередь посещённых полей
q.push(src); //Посетили исходное поле
while (!q.empty()) {
Node node = q.front(); //Взяли следующее из очереди
q.pop();
int x = node.x;
int y = node.y;
int dist = node.dist;
if (x == dest.x && y == dest.y) { //Если цель достигнута
visited.insert(node);
return node;
}
if (!visited.count(node)) { //Пропустить, если node посещалось
visited.insert(node); //Пометили node как посещённое
for (int i = 0; i < 8; i++) { //ставим в очередь валидные ходы коня
int x1 = x + row[i];
int y1 = y + col[i];
if (isValid(x1, y1, N)) q.push({ x1, y1, dist + 1, x, y });
}
}
}
Node err = { src.x, src.y, INT_MAX, dest.x, dest.y };
return err; //Путь не найден
}
int main() {
int N = 8; //Доска N x N
Node src = { 0, 0 }; //Исходные координаты (с 0)
Node dest = { 7, 7 }; //Целевые координаты
std::set <Node> visited; //Посещённые поля
Node result = findShortestDistance(N, src, dest, visited);
if (result.dist == INT_MAX) std::cout << "Way not found";
else {
std::cout << "The minimum number of steps = " << result.dist << std::endl;
std::cout << "One of ways is " << std::endl;
int **board = new int* [N];
for (int i = 0; i < N; i++) board[i] = new int[N] { 0 };
while (result.dist >= 0) {
std::set<Node>::iterator it = visited.find(result);
if (it != visited.end()) {
board[result.x][result.y] = result.dist + 1;
result.dist--; result.x = (*it).x0; result.y = (*it).y0;
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
std::cout << std::setw(2) << board[i][j];
}
std::cout << std::endl;
}
}
return 0;
}
Вот результат прогона в актуальной сборке Visual Studio 2019, как-то много убилось времени сегодня (20.11.21) на задачу :)
The minimum number of steps = 6 One of ways is 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 6 0 0 0 0 0 5 0 0 0 7
30. Определить, есть ли ход ферзя с поля f1 на f2, координаты полей заданы в формате RC (цифры номера строки и столбца, нумерация с единицы).
Определить то же самое при добавлении списка с информацией о занятых полях.
Первая формула очевидна, при допустимых координатах полей ход ферзя с поля f1 на f2 возможен, если f1 / 10 == f2 / 10 или f1 % 10 == f2 % 10 или |r1 - r2| == |c1 - c2|, где r1, r2, c1, c2 - строка и столбец (горизонталь, вертикаль и две диагонали).
Во втором случае дополнительно проверяем, не входит ли какое-то поле пути, включая начальное и конечное, в список занятых полей.
Вот программка на консольном C++.
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cmath>
int oneStep(int f1, int f2) { //Есть ли ход ферзя с f1 на f2
//f1 и f2 - в формате RC (цифры номера строки и столбца)
int r1 = f1 / 10, r2 = f2 / 10, c1 = f1 % 10, c2 = f2 % 10;
if (r1 == r2) return 1;
if (c1 == c2) return 2;
if (abs(r1 - r2) == abs(c1 - c2)) return (abs(f1 - f2) % 9 == 0 ? 3 : 4);
return 0;
}
bool freeWay(int f1, int f2, std::vector <int>& busy) {
//Есть ли ход ферзя с f1 на f2 с учетом занятых полей из вектора busy
int len = busy.size();
int way = oneStep(f1, f2);
if (way == 0) return false;
int start = std::min(f1, f2), end = std::max(f1, f2);
int step = way == 1 ? 1 : way == 2 ? 10 : way == 3 ? 9 : 11;
for (int i = start; i <= end; i += step) {
std::vector <int>::iterator it = std::find(busy.begin(), busy.end(), i);
if (it != busy.end()) return false;
}
return true;
}
int main() {
std::vector <std::pair<int,int>> test; //поля с тестами путей
test.push_back(std::make_pair(11, 34));
test.push_back(std::make_pair(33, 15));
test.push_back(std::make_pair(21, 27));
test.push_back(std::make_pair(26, 66));
test.push_back(std::make_pair(88, 11));
std::vector <int> busy; //занятые поля
busy.push_back(16);
busy.push_back(24);
busy.push_back(55);
for (std::vector <std::pair<int, int>>::iterator it = test.begin(); it != test.end(); ++it) {
int f1 = it->first, f2 = it->second;
for (int r = 1; r < 9; r++) { //вывод доски
for (int c = 1; c < 9; c++) {
int f = (r * 10 + c);
std::cout << std::setw(3);
if (f == f1 || f == f2) std::cout << 'Q';
else {
std::vector <int>::iterator it = std::find(busy.begin(), busy.end(), f);
if (it != busy.end()) std::cout << '*';
else std::cout << f;
}
}
std::cout << std::endl;
}
std::cout << "oneStep: " << oneStep(f1, f2) << std::endl; //тест функции oneStep
std::cout << "freeWay: " << freeWay(f1, f2, busy) << std::endl; //тест функции freeWay
std::cout << "Press Enter to continue...";
std::cin.get();
}
return 0;
}
31. Расстановка двух фигур, не бьющих друг друга.
Практически всегда такие задачи решаются аналитически, и особо программировать их незачем.
31.1. Сколькими способами можно поставить чёрную и белую ладьи на шахматной доске так, чтобы они не били друг друга?
Белую ладью можно поставить на любое из 64 полей доски, причём с каждого из них она бьёт 15 полей (на самом деле 14, но добавим сюда поле, на котором стоит сама ладья, чтобы туда нельзя было поставить чёрную). Остаётся 49 полей, на которые можно поставить чёрную ладью. Таким образом, белую и чёрную ладью можно расставить 64*49 = 3136 способами.
Если две ладьи одного цвета, то они неразличимы между собой (первая ладья на a1 и вторая на b2 - это та же самая позиция, что первая на b2, а вторая на a1) и позиций (способов расстановки) будет ровно вдвое меньше, то есть, 1568.
Формулы для ладей легко обобщить на доску произвольной размерности.
31.2. Та же задача для двух королей разного цвета.
Белого короля можно поставить на любое из 64 полей. Количество полей, которые он бьёт, зависит от его расположения, всего есть три случая:
- белый король в одном из 4 углов бьёт 4 поля (как и в прошлый раз, включаем в расчёт поле, занимаемое фигурой, чтобы туда нельзя было поставить вторую фигуру) и остается 60 полей, на которые можно поставить чёрного короля;
- когда белый король стоит на краю доски, но не в углу (24 поля), он бьёт по 6 полей, включая своё собственное, и для чёрного короля остается 58 возможных полей;
- если же белый король находится не на краю доски (36 полей), он бьёт 9 полей, включая поле расположение, тогда для чёрного короля остается по 55 возможных полей.
Всего имеем 4*60 + 24*58 + 36*55 = 3612 способов расстановки двух королей разного цвета.
Если короли одного цвета, как и в 31.1 имеем вдвое меньше (1806) способов.
31.3. Та же задача для двух слонов разного цвета (всё равно, белопольных или чернопольных).
11111111 12222221 12333321 12344321 12344321 12333321 12222221 11111111
На полях 1 (28 полей) слон бьёт 8 полей, включая своё собственное, остаётся по 56 свободных.
На полях 2 (20 полей) слоны бьют по 10 полей, остаётся по 54.
На полях 3 (12 полей) слоны бьют по 12 полей, остаётся по 52.
На полях 4 (4 поля) слоны бьют по 14 полей, остаётся по 50.
Всего 28*56 + 20*54 + 12*52 + 4*50 = 3472 способа или 1736, если слоны оба белые или оба чёрные.
Если оба слона белопольные или оба чернопольные, в расчётах участвует на 64, а 32 клетки,
14*24 + 10*22 + 6*20 + 2*18 = 712 способов для слонов разных цветов и 356 для слонов одного цвета.
31.4. Аналогично получаем для двух ферзей разного цвета 28*42 + 20*40 + 12*38 + 4*36 = 2576 способов и вдвое меньше (1288), если ферзи одного цвета.
31.5. По тем же принципам получаем для двух коней разного цвета 4*61 + 8*60 + 20*59 + 16*57 + 16*55 = 3696 способов и вдвое меньше (1848), если кони одного цвета.
32. Чётное количество.
Шахматный король обошёл доску чётной размерности N*N, побывав на каждом поле по одному разу и вернувшись последним ходом в исходную клетку. Докажите, что он сделал чётное количество диагональных ходов.
Если ход не диагональный, то после него меняется цвет поля под королём, а для диагонального хода не меняется. Так как король обошёл все поля и вернулся обратно, цвет поля менялся с белого на чёрный столько же раз, сколько с чёрного на белый. Значит, количество не-диагональных ходов K чётно. Тогда количество диагональных ходов будет равно N*N-K и тоже окажется чётным.
Заметим, что ноль - тоже чётное число, и на квадратной доске чётного размера король мог вообще не делать диагональных ходов, например, для доски 2*2 он мог проделать путь
23 14
а для 4*4
45AB 369C 278D 1GFE
32.1. В углу шахматной доски размерностью n×n, n>1, стоит ладья. При каких n, чередуя горизонтальные и вертикальные ходы, она может за n2 ходов побывать на всех полях доски и вернуться на место? Учитываются только поля, на которых ладья останавливается.
При чётном n решение существует, при нечётном нет. Так как ладья должна сделать всего n2 ходов, она может побывать на каждом поле не более одного раза, а значит, поля должны делиться на пары и их общее количество n2 чётно, что возможно только при чётном n.
Вопросы о шахматной доске, в шутку и всерьёз
Вопрос 1. Почему шахматная доска имеет размерность именно 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;
}
Ну а с доской ещё больше, да притом заставленной разными фигурами, игра никогда не стала бы массовой. Это же не го со всеми одинаковыми камнями :)
Вопрос 2. Ничейны ли шахматы?
Точней, достаточно ли преимущества выступки для победы белых?
Реального ответа на этот вопрос нет, потому что перебрать все партии никакому компьютеру не по силам.
Есть моя лемма о том, как распределяются доли ничьих, побед белых и побед чёрных из всех шахматных партий.
33. Дана шахматная доска размерностью n×n, n≥2. Разрешается перекрашивать в другой цвет сразу все клетки какой-либо горизонтали или вертикали. Может ли при этом получиться доска, у которой ровно одна чёрная клетка?
Перекрашивая вторую, четвёртую и т.д. горизонтали (или вертикали) из доски вида
0101 1010 0101 1010
мы получим
0101 0101 0101 0101
после чего невозможно оставить в какой-либо строке или столбце только одну "единичку". Следовательно, искомой раскраски не существует.
34. В некоторых клетках шахматной доски размерностью n×n, n≥1 стоят фигуры. Известно, что на каждой горизонтали стоит хотя бы одна фигура, причём в разных горизонталях – разное количество фигур. Докажите, что всегда можно отметить n фигур так, чтобы в каждой вертикали и каждой горизонтали стояла ровно одна отмеченная фигура.
На горизонтали может стоять от одной до n фигур. Так как на разных горизонталях находится разное количество фигур, на некоторой горизонтали стоит ровно одна фигура, на некоторой другой – две фигуры и т.д. Пронумеруем горизонтали в соответствии с количеством стоящих на них фигур. Отметим на первой горизонтали её единственную фигуру. Поскольку на второй горизонтали две фигуры, одну из них можно отметить. На третьей горизонтали находится три фигуры, хотя бы одну из них можно отметить, и так далее.
Пример такой отметки:
* 1 * 1 * 3 1*34 1 2 * 45 1234 *6 1234 *67 1234567*
35. Сколько коней можно расставить на стандартной шахматной доске таким образом, чтобы каждый конь бил ровно двух других?
Если в квадрате 3×3 поставить коней на все клетки, кроме центральной, то каждый конь будет бить ровно двух других. Расположив такие группы по 8 коней на полях a1:c3, a6:c8, f1:h3, f6:h8, получим искомую расстановку из 32 коней.
36. Сколько всего чёрных и белых ладей можно расставить на шахматной доске размерностью n×n, n≥2 так, чтобы ладьи разного цвета не били друг друга?
Очевидно, всего n*n/2 ладей при чётном значении n
*Ч Б*
**ЧЧ **ЧЧ ББ** ББ**
и (n*n-1)/2 при нечётном.
**Б **Б ЧЧ*
***ББ ***ББ ***ББ ЧЧЧ** ЧЧЧ**
37. Откуда берётся число 23. На 1-й горизонтали стандартной шахматной доски стоят 8 чёрных ферзей, а на последней – 8 белых. За какое минимальное количество ходов белые и чёрные ферзи могут обменяться местами, если белые и чёрные ходят в обычном порядке по очереди?
Парам ферзей с вертикалей b,c,...,g требуется не менее 3 ходов на пару. Четырём угловым ферзям вместе понадобится не менее 5 ходов. Всего имеем 6*3+5 = 23 хода, попробуйте воспроизвести это.
38. Какое наименьшее количество ладей нужно поставить на стандартную шахматную доску 8×8, чтобы все белые клетки были под боем этих ладей?
Каждая ладья бьёт не больше двух клеток белой диагонали. Максимальное количество клеток белой диагонали равно 8, значит, нужно 4 ладьи. Поставим их на поля a1, c3, e5 и g7.
39. Докажите, что количество решений задачи об N ферзях всегда чётно.
Так как на одной горизонтали может стоять только один ферзь, для любой расстановки ферзей есть расстановка, симметричная ей относительно вертикальной оси, разбивающей доску пополам. Таким образом, общее количество расстановок всегда чётно.
40. На шахматной доске n×n (n = 4, 6, 8, ...) расставлено n не бьющих друг друга ферзей. Докажите, что в каждом угловом квадрате (n/2)×(n/2) находится хотя бы один ферзь.
Пусть в левом верхнем квадрате (n/2)×(n/2) ферзей нет. Тогда все (n/2) ферзей на (n/2) верхних горизонталях находятся в правом верхнем квадрате (n/2)×(n/2), а все (n/2) ферзей на (n/2) левых вертикалях – в левом нижнем квадрате. Но оба этих квадрата покрываются n-1 диагоналями, поэтому ферзей там не больше n-1. Противоречие.
41. Коды ходов. Для игры по каналу связи шахматный ход передаётся как 4-значное число, первые 2 цифры которого означают столбец и строку доски, с которых сделан очередной ход, а последние 2 цифры - аналогичные координаты целевого поля, например, 5121 - это длинная рокировка за белых (или ход ладьёй либо ферзём с поля e1 на c1), а 5254 - ход с e2 на e4. Так как обмен ходами ведётся последовательно с начальной позиции, информацию о фигуре и цвете можно не передавать.
12345678 8 * * * * 7 * * * * 6 * * * * 5 * * * * 4 * * * * 3 * * * * 2 * * * * 1 * * * * abcdefgh
Сколько существует различных кодов ходов при такой записи?
- 14*64 = 896, ладья (из задачи 31.1);
- 28*7+20*9+12*11+4*13 = 560, слон (из задачи 31.3);
- 4*2+8*3+20*4+16*6+16*8 = 336, конь (задача 17);
- 4 рокировки отдельных кодов не дадут;
- 16*4 = 64 превращения, если кодировать их отдельно.
Ходы ферзя, пешки и короля уже будут учтены, так как слон и ладья сделают все возможные ходы по вертикалям, горизонталям и диагоналям.
Всего имеем 1792 кода, или же 1792+64=1856, если учитывать превращения отдельными цифровыми кодами. Можно добавить два "спецкода", например, 0000 и 1212 для сдачи и предложения ничьей.
17.02.2019, 12:30 [7750 просмотров]