Шахматы и рекурсивная функция

@alexshch · Регистрация: 28.10.2015

Author24 — интернет-сервис помощи студентам

Дано число N. Определите, сколькими способами можно расставить на доске N×N N ферзей, не бьющих друг друга.
Формат входных данных
Задано единственное число N. (N ≤ 10)
Формат выходных данных
Выведите ответ на задачу.
Подсказка
Напишите рекурсивную функцию, которая пытается поставить ферзя в очередной столбец. Если на эту клетку ставить ферзя нельзя (он бьет предыдущих), то такой вариант даже не стоит рассматривать. Когда вы успешно поставили ферзя в последний столбец - увеличивайте счетчик.

Sample Input:
8
Sample Output:
92

@NikBond · 21.11.2015, 00:02

Прошу прощения, что не свой код, но исходный код задачи можно найти на первой же странице гугла:

C++

#include <time.h>
#include <stdio.h>
#include <string.h>
 
#define SIZE 20
 
int size,
    sol_num,
    a[ SIZE ];
 
struct _board {
    unsigned int a[ SIZE ];
} board[ SIZE+1 ];
 
void dfs(register int ind)
{
    register int i, j;
 
    if (ind >= size)
    {
        ++sol_num;
        return;
    }
 
    for (a[ind] = 0; a[ind] < size; ++a[ind])
    {
        if (!(board[ind].a[ ind ] & (1<<a[ind])))
        {
            memcpy(board[ind+1].a, &board[ind].a , SIZE*sizeof(int));
 
            for (i = ind, j = a[ind]; i<size && j<size; ++i, ++j)
                board[ind+1].a[i] |= (1<<j);
 
            for (i = ind, j = a[ind]; i<size && j>=0; ++i, --j)
                board[ind+1].a[i] |= (1<<j);
 
            board[ind+1].a[ind] = 65535u;
 
            for (i = ind; i < size; ++i)
                board[ind+1].a[i] |= 1<<a[ind];
 
            dfs(ind+1);
        }
    }
}
 
int main()
{
    double start, end;
 
    int i;
    for (size = 1; size < 20; ++size)
    {
        start = clock();
 
        sol_num = 0;
        memset(a, 0, sizeof(int)*SIZE);
        for (i = 0; i < SIZE+1; ++i)
            memset(board[i].a, 0, sizeof(int)*SIZE);
 
        dfs(0);
        end = clock();
        printf("%20d%20d\ttime: %.2lf\n", size, sol_num, (end-start)/CLOCKS_PER_SEC);
    }
 
    return 0;
}

Если быть точным, это все же Си, а не С++, но предполагаю, что в данном контексте разница не велика.

Добавлено через 2 минуты
А впрочем, вот и для С++:

C++

// Backtracking method. "Поиск с возвратом" на примере
// задачи о восьми ферзях.
 
#include <iostream>
 
const int SIZE = 8; // Размер.
 
int board[SIZE][SIZE];
int results_count = 0; // Количество решений.
 
// Функция showBoard() - отображает доску.
void showBoard()
{
    for(int a = 0; a < SIZE; ++a)
    {
        for(int b = 0; b < SIZE; ++b)
        {
            std::cout << ((board[a][b]) ? "Q " : ". ");
        }
        std::cout << '\n';
    }
}
 
// Функция tryQueen() - проверяет нет ли уже установленных ферзей,
// по вертикали, диагоналям.
bool tryQueen(int a, int b)
{
    for(int i = 0; i < a; ++i)
    {
        if(board[i][b])
        {
            return false;
        }
    }
 
    for(int i = 1; i <= a && b-i >= 0; ++i)
    {
        if(board[a-i][b-i])
        {
            return false;
        }
    }
 
    for(int i = 1; i <= a && b+i < SIZE; i++)
    {
        if(board[a-i][b+i])
        {
            return false;
        }
    }
 
    return true;
}
 
// Функция setQueen() - пробует найти результаты решений.
void setQueen(int a) // a - номер очередной строки в которую нужно поставить очередного ферзя.
{
    if(a == SIZE)
    {
        showBoard();
        std::cout << "Result #" << ++results_count << "\n\n";
        return; // Опционально.
    }
 
    for(int i = 0; i < SIZE; ++i)
    {
        // Здесь проверяем, что если поставим в board[a][i] ферзя (единицу),
        // то он будет единственным в этой строке, столбце и диагоналях.
        if(tryQueen(a, i))
        {
            board[a][i] = 1;
            setQueen(a+1);
            board[a][i] = 0;
        }
    }
 
    return; // Опционально.
}
 
int main()
{
    setQueen(0);
 
    return 0;
}

@alexshch · 21.11.2015, 00:03 **[ТС]**

С++ включает в себя С, поэтому всё хорошо, но алгоритм слишком медленный

@Kuzia domovenok · 21.11.2015, 18:20

alexshch, конечно у него медленно! Такой говнокод ничего кроме блевоты не вызывает.
Годный алгоритм не должен использовать циклов для проверки взаимоположения ферзей. Но до гуманитария NikBond это, похоже, не доходит.

@_Ivana · 21.11.2015, 19:15

Есть и другие точки зрения на то, что такое говнокод, и кто гуманитарий и вызывает блевоту.

Сообщение от alexshch

алгоритм слишком медленный

Похоже, гуманитарий, писавший это, не смог сопоставить N ≤ 10 в своем условии с size < 20 в коде. Ну, каждый сам себе гуманитарий.

ЗЫ в лоб, до 10 считает влет, как и вышепредложенный код.

C++

int m[10]; int f(int n, int i);
 
bool tst(int i, int j, int k) {
    return k==i ? 1 : m[k]!=j && (i-k)!=(j-m[k]) && (i-k)!=(m[k]-j) && tst(i,j,k+1);}
 
int loop(int n, int i, int j) {
    if (j<n) {int r=0; if (tst(i,j,0)) {m[i]=j; r=f(n,i+1);} return r+loop(n,i,j+1);}
    else return 0;}
 
int f(int n, int i) {return i==n ? 1 : loop(n,i,0);}
 
int main() {int n; cin>>n; cout<<f(n,0); return 0;}

@NikBond · 21.11.2015, 21:18

Сообщение от Kuzia domovenok

Но до гуманитария NikBond это, похоже, не доходит.

Я бы попросил не выражаться. К тому же, ~~мопед не мой~~ код нагугленный, о чем я и говорил.

@Kuzia domovenok · 22.11.2015, 00:56

C++

#include <iostream>
#include <conio.h>
#include <string>
using namespace std;
 
class board
{
private:
    enum { size = 8 };
    int rows[size];
    bool column_chk[size];
    bool diag_A_chk[size * 2 - 1];
    bool diag_B_chk[size * 2 - 1];
    int solutions_cnt;
 
    bool put_queen(int x, int y)
    {
        //if (rows[y] != -1) return false;//проверка пустоты строчки
        if (column_chk[x]) return false;//проверка пустоты столбца
        if (diag_A_chk[x + y]) return false;//проверка пустоты диагонали А
        if (diag_B_chk[x - y + size-1]) return false;//проверка пустоты диагонали Б
        /*    нумерация диагоналей (со строчками и столбцами и ежу понятно)
        0     x+y=const-индекс северо-восточных диагоналей    14 max
        /     /
        .012345/7
        0...../..\
        1..../... \
        2...Q....  \14 max
        3....\...
        4.....\..
        5......\.
        6.......\
        7........\
        \       \x-y+7=const
        \
        0
 
        */
        rows[y] = x;
        column_chk[x] = diag_A_chk[x + y] = diag_B_chk[x - y + size - 1] = true;
        return true;
    }
    void remove_queen(int y)
    {
        int x = rows[y];
        column_chk[x] = diag_A_chk[x + y] = diag_B_chk[x - y + size - 1] = false;
        rows[y] = -1;
    }
    void print()
    {
        cout << "@";
        for (char c = 'A'; c < 'A' + size; c++)
                cout << c;
        for (int row = 0; row < size; row++)
        {
            cout << endl << row;
            for (int col = 0; col < rows[row]; col++) cout << ".";
            if (rows[row] != -1) cout << "Q";
            for (int col = rows[row]+1; col < size; col++) cout << ".";
        }
        cout << endl;
    }
public:
    board()
    {
        for (int i = 0; i < size; ++i)
        {
            rows[i] = -1;
            column_chk[i] = false;
            diag_A_chk[i] = diag_A_chk[size + i-1] = false;
            diag_B_chk[i] = diag_B_chk[size + i-1] = false;
        }
        solutions_cnt = 0;
    }
    void solve(int row = 0)
    {
        if (row == size)
        {
            solutions_cnt++;
            //print();
            return;
        }
        for (int col = 0; col < size; ++col)
        {
            if (put_queen(col, row)){
                solve(row + 1);
                remove_queen(row);
            }
        }
    }
    int get_solutions_cnt() const
    {
        return solutions_cnt;
    }
};
 
int main()
{
    board task;
    task.solve();
    std::cout << "result solutions: " << task.get_solutions_cnt() << std::endl;
    _getch();
    return 0;
}

Добавлено через 9 минут

C++

#include <iostream>
#include <fstream>
#include <conio.h>
#include <string>
using namespace std;
 
class board
{
private:
    enum { max_size = 8 };
    int size;
    int rows[max_size];
    bool column_chk[max_size];
    bool diag_A_chk[max_size * 2 - 1];
    bool diag_B_chk[max_size * 2 - 1];
    int solutions_cnt;
 
    bool put_queen(int x, int y)
    {
        //if (rows[y] != -1) return false;//проверка пустоты строчки
        if (column_chk[x]) return false;//проверка пустоты столбца
        if (diag_A_chk[x + y]) return false;//проверка пустоты диагонали А
        if (diag_B_chk[x - y + size-1]) return false;//проверка пустоты диагонали Б
        /*    нумерация диагоналей (со строчками и столбцами и ежу понятно)
        0     x+y=const-индекс северо-восточных диагоналей    14 max
        /     /
        .012345/7
        0...../..\
        1..../... \
        2...Q....  \14 max
        3....\...
        4.....\..
        5......\.
        6.......\
        7........\
        \       \x-y+7=const
        \
        0
 
        */
        rows[y] = x;
        column_chk[x] = diag_A_chk[x + y] = diag_B_chk[x - y + size - 1] = true;
        return true;
    }
    void remove_queen(int y)
    {
        int x = rows[y];
        column_chk[x] = diag_A_chk[x + y] = diag_B_chk[x - y + size - 1] = false;
        rows[y] = -1;
    }
    void print()
    {
        cout << "";
        for (char c = 'A'; c < 'A' + size; c++)
                cout << c;
        for (int row = 0; row < size; row++)
        {
            cout << endl << row;
            for (int col = 0; col < rows[row]; col++) cout << ".";
            if (rows[row] != -1) cout << "Q";
            for (int col = rows[row]+1; col < size; col++) cout << ".";
        }
        cout << endl;
    }
    void solve_rec(int row)
    {
        if (row == size)
        {
            solutions_cnt++;
            //print();
            return;
        }
        for (int col = 0; col < size; ++col)
        {
            if (put_queen(col, row)){
                solve_rec(row + 1);
                remove_queen(row);
            }
        }
    }
public:
    board(int sz) :size(sz)
    {
        if (size>0 && size <= max_size)
        {
            for (int i = 0; i < size; ++i)
            {
                rows[i] = -1;
                column_chk[i] = false;
                diag_A_chk[i] = diag_A_chk[size + i - 1] = false;
                diag_B_chk[i] = diag_B_chk[size + i - 1] = false;
            }
            solutions_cnt = 0;
        }
    }
    void solve(){
        if (size>0 && size <= max_size)
            solve_rec(0);
    }
    int get_solutions_cnt() const
    {
        if (size>0 && size <= max_size)
            return solutions_cnt;
        else 
            return -1;
    }
};
 
int main()
{
    ifstream in("input.txt");
    ofstream out("output.txt");
    int n;
    in >> n;
    board task(n);
    task.solve();
    out << task.get_solutions_cnt();
    //getchar();
    return 0;
}

@NikBond · 23.11.2015, 15:01

C

/** Задача о восьми ферзях.
  * Программа выводит в консоль, сколькими способами можно разместить 8 ферзей (queen) на шахматной доске размером 8х8.
  * В файл "Queen.txt" записываются все возможные варианты таких размещений.
  * Используется алгоритм "Поиск с возвратом".
*/
 
#include <stdio.h>
#define SIZE 8
 
int countOfSolution = 0; //количество возможных решений
 
FILE * pF = fopen("Queen.txt", "w");
 
void printBoard(int board[SIZE][SIZE]);
void backtracking(int board[SIZE][SIZE], int );
int isCanPutQueen(int board[SIZE][SIZE], int, int );
 
 
int main(){
 
    /* Шахматная доска 8х8. 0 == клетка свободна, 1 == клетка под ударом*/
 
    int board[SIZE][SIZE] = {0}; //инициализируем доску нулями
 
    backtracking(board, 0);
 
    printf("Common amount of solutions is: %i", countOfSolution);
 
    return 0;
}
 
void printBoard(int board[SIZE][SIZE]){
 
    /* Печать доски в файл*/
 
    for(int i = 0; i < SIZE; i++ ){
        for(int j = 0; j < SIZE; j++){
            fprintf(pF, "%i ", board[i][j]);
        }
        fprintf(pF, "\n");
    }
    fprintf(pF, "\n");
}
 
void backtracking(int board[SIZE][SIZE], int row){
 
    /* Алгоритм Backtracking (поиск с возвратом). */
 
    if ( row == SIZE){
        /* Если успешно заполнен последний рядок доски, засчитываем решение и печатаем его в файл*/
        countOfSolution++;
        fprintf(pF, "Solution # %i\n", countOfSolution);
        printBoard(board);
    }
 
    for(int i = 0; i < SIZE; i++){
        if ( isCanPutQueen(board, row, i) != 0 ){
            board [row][i] = 1;
            backtracking(board, row + 1);
            board [row][i] = 0;
        }
    }
}
 
int isCanPutQueen(int board[SIZE][SIZE], int row, int col){
 
    /*Если поставить королеву в указанную клетку нельзя (она попадает под удар), функция возвращает 0. */
 
    for(int i = 0; i < row; i ++){                                  //проверка по вертикали
        if ( board [i][col] != 0){
            return 0;
        }
    }
 
 
    for(int i = 1; i <= row && col-i >= 0; i++){                    //проверка по основной диагонали
        if ( board[row - i][col - i] != 0){
            return 0;
        }
    }
 
    for(int i = 1; i <= row && col+i < SIZE; i++){                  //проверка по обратной диагонали
        if ( board[row - i][col + i] != 0){
            return 0;
        }
    }
 
    return 1;
}

@Kuzia domovenok · 24.11.2015, 20:32

Сообщение от NikBond

int isCanPutQueen(int board[SIZE][SIZE], int row, int col){ /*Если поставить королеву в указанную клетку нельзя (она попадает под удар), функция возвращает 0. */ for(int i = 0; i < row; i ++){ //проверка по вертикали if ( board [i][col] != 0){ return 0; } } for(int i = 1; i <= row && col-i >= 0; i++){ //проверка по основной диагонали if ( board[row - i][col - i] != 0){ return 0; } } for(int i = 1; i <= row && col+i < SIZE; i++){ //проверка по обратной диагонали if ( board[row - i][col + i] != 0){ return 0; } } return 1; }

зачем цикл?

Новые блоги и статьи
Что такое CQRS и как это реализовать на C# с MediatR InfoMaster 15.01.2025 Концепция CQRS и её роль в современной разработке В современном мире разработки программного обеспечения архитектурные паттерны играют ключевую роль в создании масштабируемых и поддерживаемых. . .	Как настроить CI/CD с Azure DevOps InfoMaster 15.01.2025 CI/ CD, или непрерывная интеграция и непрерывное развертывание, представляет собой современный подход к разработке программного обеспечения, который позволяет автоматизировать и оптимизировать процесс. . .	Как настроить CI/CD с помощью Jenkins InfoMaster 15.01.2025 Введение в CI/ CD и Jenkins В современной разработке программного обеспечения непрерывная интеграция (CI) и непрерывная доставка (CD) стали неотъемлемыми элементами процесса создания качественных. . .	Как написать микросервис на Go/Golang с Kafka и GitHub CI/CD InfoMaster 14.01.2025 Определение микросервиса, преимущества использования Go/ Golang Микросервис – это архитектурный подход к разработке программного обеспечения, при котором приложение состоит из небольших, независимо. . .	Как написать микросервис с нуля на C# с RabbitMQ, CQRS и CI/CD InfoMaster 14.01.2025 В современном мире разработки программного обеспечения микросервисная архитектура стала стандартом де-факто для создания масштабируемых и гибких приложений. Этот архитектурный подход предполагает. . .	Как создать интернет-магазин на PHP и JavaScript InfoMaster 14.01.2025 В современном мире электронная коммерция стала неотъемлемой частью бизнеса. Создание собственного интернет-магазина открывает широкие возможности для предпринимателей, позволяя достичь большей. . .
Как написать Тетрис на Ассемблере InfoMaster 14.01.2025 Тетрис – одна из самых узнаваемых и популярных компьютерных игр, созданная в 1984 году советским программистом Алексеем Пажитновым. За прошедшие десятилетия она завоевала симпатии миллионы людей по. . .	Как создать игру "Танчики" на Unity3d и C# InfoMaster 14.01.2025 Разработка игр – это увлекательный процесс, сочетающий в себе творчество и технические навыки. В этой статье мы рассмотрим создание классической игры "Танчики" с использованием Unity3D и языка. . .	Организую платный онлайн микро-курс по доработке Android-клиента Telegram _Ivana 14.01.2025 Официальная версия и распространенные форки не полностью устраивают? Сделай свою кастомную версию клиента! 4 занятия по 2 часа (2 недели пн, ср 19:00-21:00 по Москве). Первое вводное занятие. . .	Как создать приложение для фитнеса для iOS/iPhone на Kotlin InfoMaster 14.01.2025 Создание собственного фитнес-приложения — это не только захватывающий, но и полезный процесс, ведь оно может стать вашим верным помощником на пути к здоровому и активному образу жизни. В современных. . .	Как создать приложение магазина для iOS/iPhone на Swift InfoMaster 14.01.2025 Введение в разработку iOS-приложений Разработка приложений для iPhone и других устройств на базе iOS открывает огромные возможности для создания инновационных мобильных решений. В данной статье мы. . .	Это работает. Скорость асинхронной логики велика. Вопрос видимо останется в стабильности. Плата - огонь! Hrethgir 13.01.2025 По прошлому проекту в Logisim Evolution https:/ / www. cyberforum. ru/ blogs/ 223907/ blog8781. html прилагаю файл архива проекта в Gowin Eda. Восьмибитный счётчик из сумматора+ генератор сигнала. . .

@alexshch 1 / 1 / 0 Регистрация: 28.10.2015 Сообщений: 24
		1
	Шахматы и рекурсивная функция 20.11.2015, 23:50. Показов 14447. Ответов 8 Метки нет (Все метки) Дано число N. Определите, сколькими способами можно расставить на доске N×N N ферзей, не бьющих друг друга. Формат входных данных Задано единственное число N. (N ≤ 10) Формат выходных данных Выведите ответ на задачу. Подсказка Напишите рекурсивную функцию, которая пытается поставить ферзя в очередной столбец. Если на эту клетку ставить ферзя нельзя (он бьет предыдущих), то такой вариант даже не стоит рассматривать. Когда вы успешно поставили ферзя в последний столбец - увеличивайте счетчик. Sample Input: 8 Sample Output: 92 0

@alexshch 1 / 1 / 0 Регистрация: 28.10.2015 Сообщений: 24
	21.11.2015, 00:03 [ТС]	3
	С++ включает в себя С, поэтому всё хорошо, но алгоритм слишком медленный 0

@Kuzia domovenok 4264 / 3323 / 925 Регистрация: 25.03.2012 Сообщений: 12,520 Записей в блоге: 1
	21.11.2015, 18:20	4
	alexshch, конечно у него медленно! Такой говнокод ничего кроме блевоты не вызывает. Годный алгоритм не должен использовать циклов для проверки взаимоположения ферзей. Но до гуманитария NikBond это, похоже, не доходит. 0

@NikBond 2 / 2 / 2 Регистрация: 21.07.2015 Сообщений: 36
	21.11.2015, 21:18	6
	Сообщение от Kuzia domovenok Но до гуманитария NikBond это, похоже, не доходит. Я бы попросил не выражаться. К тому же, ~~мопед не мой~~ код нагугленный, о чем я и говорил. 0

@Kuzia domovenok 4264 / 3323 / 925 Регистрация: 25.03.2012 Сообщений: 12,520 Записей в блоге: 1
	24.11.2015, 20:32	9
	Сообщение от NikBond int isCanPutQueen(int board[SIZE][SIZE], int row, int col){ /Если поставить королеву в указанную клетку нельзя (она попадает под удар), функция возвращает 0. / for(int i = 0; i < row; i ++){ //проверка по вертикали if ( board [i][col] != 0){ return 0; } } for(int i = 1; i <= row && col-i >= 0; i++){ //проверка по основной диагонали if ( board[row - i][col - i] != 0){ return 0; } } for(int i = 1; i <= row && col+i < SIZE; i++){ //проверка по обратной диагонали if ( board[row - i][col + i] != 0){ return 0; } } return 1; } зачем цикл? 0