Другие языки программирования и технологии

Задачка сложная по Си. 8 королев. Вопрос внутри.

учу Си, вроди есть результаты. Решил взяться за сложную задачу, заметил что делая одну сложную учишся большему чем решая 20 простых.
Так вот написал я, но компилятор вредина ругается. Сначала выдал много ошибок, уменьшил их до 3х - 4х и не знаю что с ними делать. Буду благодарен за помощь, все пошагово я закоментировал, чтоб вы долго не разберались что за чем идет. Задача интресная, мне кажется и Вам будет полезно.

ага так к сути задачи:

Вывести колличество возможных результатов расстоновки 8-ми шахматных королев так чтоб они не могли друг друга ударить. Задача должна решаться рекурсией.

пс: лучше если вы скопируете код и вставите его в свой редактор кода.

//#include
#include

void clear(int **board) //очищаем нашу доску
{
int i;
int j;

i = 0;
while (i < 7)
{
j = 0;
while (j < 7)
{
board[i][j] = 3;
j++;
}
i++;
}
}

void zero_diags(int **board, int x, int y) // ставим нули по диагоналям
{
int i;
int j;

i = x;
j = y;
while (i > 0 && j > 0)
{
--i;
--j;
}
while (i < 8 && j < 8)
{
board[i][j] = 0;
++i;
++j;
}
i = x;
j = y;
while (i < 8 && j > 0)
{
++i;
--j;
}
while (i > 0 && j < 8)
{
board[i][j] = 0;
i--;
j++;
}
board[x][y] = 1;
}

void zero_rl(int **board, int x, int y) //ставим нули на верх - вниз - вправо - влево
{
int i;

i = 0;
while(i < 8)
{
if (i == x)
{
i++;
continue;
}
board[i][y] = 0;
i++;
}
i = 0;
while (i < 8)
{
if (i == y)
{
i++;
continue;
}
board[x][i] = 0;
i++;
}
}

int ft_queen(int **board, int x, int y, int flag) // главная ф-ция решения задачи
{
if (x > 7) // переход на новую строку
{
x = 0;
y = y + 1;
}
if (y > 7) // конец счета, если все закончилось удачно возвращаем 1, стераем нашу шахматную доску для след захода. Конец рекурсии
{
clear(board);
return (1);
}
if (board[x][y] == 1) // если нашли королеву, ставим 0 по диагоналям и по прямым линиям
{
zero_rl(board, x, y);
zero_diags(board, x, y);
x++;
}
if (board[x][y] == 0)
x++;
if (board[x][y] != 0 && board[x][y] != 1) // если в клетке ничего нет ставим королеву
board[x][y] = 1;
if (flag == 0) // если это наш первый заход на доску, то раставив удар первой королевы, вот тут-то мы обнуляем координаты, и следующий заход будет с начала доски
{
x = 0;
y = 0;
}
ft_queen(board, x, y, flag = flag + 1); // заходим в рекурсию и как раз и увеличиваем наш флаг ТУТ РАГАЕТСЯ КОМПИЛЯТОР ЧТО ФЛАГ НИГДЕ НЕ ИСПОЛЬЗУЕТСЯ
}

int start_point (int **board, int x, int y, int counter)
{
int flag; // этот флаг передается в след. вызов функции. Он обнуляет координаты, чтоб программа начала работать с самого начала доски, после поставки первой королевы на доску

flag = 0;
if (y > 7)
return counter; //значит доска закончилась, возврат счетчика
if (x > 7) // переход начальной точки на следющую строку
{
y = y + 1;
x = 0;
}
board[x][y] = 1; // ТУТ ВЫДАЕТ ОШИБКУ СЕГМЕНТАЦИИ ((( по сути эта строчка ставит первую королеву
counter = counter + ft_queen(board, x, y, flag); // заходит в функцию с начальной точкой
start_point(board, x = x + 1, y, counter); // заходим в рекурсию увеличивая начальную точку ТУТ РАГАЕТСЯ КОМПИЛЯТОР ЧТО Х НИГДЕ НЕ ИСПОЛЬЗУЕТСЯ
}

void queens(void)
{
int x;
int y;
int board[7][7]; // шахматная доска
int result; // возврат комбинаций
int counter; // счет комбинаций

x = 0;
y = 0;
counter = 0;
result = start_point (board, x, y, counter); // ТУТ УЖЕ НАЧИНАЕТ РУГАТЬСЯ КОМПИЛЯТОР, НЕ ПОЙМУ ЧТО ОН ОТ МЕНЯ ХОЧЕТ
printf("%d", result); // вывод результата
}

int main(void)
{
queens();
return (0);
}
Для такой задачи не нужно использовать матрицу - достаточно массива 8 элементов (столбцы) - очевидно, что в одном столбце не может быть больше одного ферзя, таким образом достаточно хранить в элементе его позицию ( заодно очевидно, что решений не может быть более 8! а на самом деле их всего 92 :)

Если использовать "генератор перестановок" нам останется только проверить 40320 вариантов на диагонали например так https://ideone.com/QBf4sX

А "генератор перестановок" можно сделать рекурсивным, заодно и проверку на диагонали в него встроить :)
https://ideone.com/Fbj42N
Александр Ковалев
Александр Ковалев
78 419
Лучший ответ
напиши тексты ошибок как есть.. на английском
Антон Корпачёв
Антон Корпачёв
81 808
Польза от решения задачи будет, если вы над ней вначале подумаете. Думать надо на тему "как представить данные", то есть над структурой данных. "Иван Сигаев" уже дал верную подсказку. Можно хранить "расстановку" в виде 8 байт (даже семи, поскольку последний, восьмой, легко вычисляется). Заметить, что поворот и зеркальное отражение расстановки не меняют её. Продумать, как это реализовать Можно "для общего развития" поиграть с битами.
Всего (в лоб) потребуется перебрать не более 7! вариантов перестановок чисел {1,2,4,8,16,32,64,128,256}.
int board[7][7]; // шахматная доска
почему? доска ж 8х8

while (i < 7)
{
j = 0;
while (j < 7)
почему не (i < 8) и (j < 8) ?

x++;
}
if (board[x][y] == 0)
x++;
if (board[x][y] != 0 && board[x][y] != 1) // если в клетке ничего нет ставим королеву
board[x][y] = 1;
странный код: увеличили x, не проверив, что не вылетели за пределы доски, сунулись в board, увеличили x ещё раз, и, опять не проверив выход за границы массива, пытаемся что-то в него писать
Алексей Рыбак счет же начинается с 0. с 0 до 7 это 8мь
По моим расчётам СЕМЬ максимум
Алексей Рыбак 8 можно, на то задача и интересная, комп может посчитать как расставить 8. Можно усложнить задачу. не колличество вариантов, а выводить варианты на экран
Игорь Ручьев
Игорь Ручьев
2 042
инклуды сюда напиши
Алексей Рыбак тут один для printf #include