Я работаю над заданием, касающимся головоломки с восьмеркой ферзей в шахматах. Упражнение выглядит следующим образом:
Учитывая расположение 8 ферзей на шахматной доске, напишите программу на C, которая будет оценивать расположение и информировать пользователя, является ли это расположение решением головоломки.
Теперь, поскольку есть 92 возможных решения, нецелесообразно сравнивать пользовательский ввод со списком решений, поэтому я решаю проблему следующим образом:
Я рассматриваю массив 8x8. Представляя пустое поле с 0 и поле с ферзем с 1, все, что мне нужно проверить, чтобы решение было правильным, это:
Сумма каждой строки, столбца и возможной диагональной линии не должна превышать 1.
И вот моя проблема: я покрыл строки и столбцы, но я не могу найти способ добавить диагонали. В целях разъяснения:
Каждая диагональная линия представляет собой квадраты, которые необходимо суммировать каждый раз. Результат каждой строки будет храниться в массиве. Это происходит для обоих направлений.
Код пока:
#include <stdio.h>
int check(int array[8][8])
{
int i, j;
int rowsum[8] = {0, 0, 0, 0, 0, 0, 0, 0};
int colsum[8] = {0, 0, 0, 0, 0, 0, 0, 0};
for (i = 0; i <= 7; i++) //test if are 2 queens on the same row (i: row, j: column)
{
for (j = 0; j <= 7; j++)
{
rowsum[i] += array[i][j]; /*since they are represented by 0s and 1s,
if a row's sum is bigger than 1
there is more than 1 queen on that particular row
here the row doesn't change until all
columns are accessed (we get a row sum)*/
}
}
for (i = 0; i <= 7; i++) //same as before, but for columns
{
for (j = 0; j <= 7; j++)
{
colsum[i] += array[j][i]; //here the col. doesn't change until all rows are accessed (we get a col. sum)
}
}
}
int main(void)
{
int i = 1; //counter for the input
int row = 0;
int column = 0; //row and column numbers
int board[8][8] = {
{0, 0, 0, 0, 0, 0, 0, 0}, //here we initialize an empty board as an 8x8 array
{0, 0, 0, 0, 0, 0, 0, 0}, //from now on: a 0 is an empty square, a 1 is a queen
{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}
};
while (i <= 8) //we fill our board with queens
{
printf("Queen #%d row:", i);
scanf("%d", &row);
printf("Queen #%d column:", i);
scanf("%d", &column);
board[row - 1][column - 1] = 1;
i++;
}
check(board);
}
Любая помощь будет принята с благодарностью.
EDIT: Решено. Большое спасибо @Yunnosch за то, что указал мне правильное направление! К сведению об окончательном решении: вы можете найти его здесь с поясняющими комментариями: Решение
EDIT-2: Вы можете найти весь код здесь, также с комментариями.
@Yunnosch: Это может быть не элегантно или даже неэффективно, но работает хорошо. Быстрый вопрос: был ли этот метод тем, который вы имели в виду, или это нововведение? :П
check
имеет возвращаемый типint
, но она не возвращает никаких значений, и вы все равно не проверяете значение, так зачем ее вызывать? - person Chris Turner   schedule 18.12.2017