Рубрики

C Программа для N Queen Задача | Откат-3

N Queen — это проблема размещения N шахматных ферзей на N × N шахматной доске, чтобы две королевы не атаковали друг друга. Например, следующее является решением проблемы 4 Queen.

Ожидаемый результат — это двоичная матрица, которая имеет 1 для блоков, в которые помещены ферзи. Например, ниже приведена выходная матрица для решения с 4 ферзями.

              { 0,  1,  0,  0}
              { 0,  0,  0,  1}
              { 1,  0,  0,  0}
              { 0,  0,  1,  0}

/ * C / C ++ программа для решения проблемы N Queen с помощью

   возвращение назад * /

#define N 4
#include <stdbool.h>
#include <stdio.h>

  
/ * Утилита для печати решения * /

void printSolution(int board[N][N])

{

    for (int i = 0; i < N; i++) {

        for (int j = 0; j < N; j++)

            printf(" %d ", board[i][j]);

        printf("\n");

    }

}

  
/ * Утилита для проверки, может ли ферзь

   быть помещенным на борту [ряд] [столб]. Обратите внимание, что это

   функция вызывается, когда королевы "col"

   уже размещены в столбцах от 0 до цв -1.

   Поэтому нам нужно проверить только левую сторону для

   атакующие королевы * /

bool isSafe(int board[N][N], int row, int col)

{

    int i, j;

  

    / * Проверьте этот ряд на левой стороне * /

    for (i = 0; i < col; i++)

        if (board[row][i])

            return false;

  

    / * Проверить верхнюю диагональ с левой стороны * /

    for (i = row, j = col; i >= 0 && j >= 0; i--, j--)

        if (board[i][j])

            return false;

  

    / * Проверить нижнюю диагональ с левой стороны * /

    for (i = row, j = col; j >= 0 && i < N; i++, j--)

        if (board[i][j])

            return false;

  

    return true;

}

  
/ * Рекурсивная функция полезности для решения N

   Королева проблема * /

bool solveNQUtil(int board[N][N], int col)

{

    / * базовый случай: если все королевы помещены

      затем верните true * /

    if (col >= N)

        return true;

  

    / * Рассмотрим этот столбец и попробуйте разместить

       эта королева во всех рядах по одному * /

    for (int i = 0; i < N; i++) {

        / * Проверьте, можно ли поместить королеву на

          доска [я] [цв] * /

        if (isSafe(board, i, col)) {

            / * Поместите эту королеву в доску [i] [col] * /

            board[i][col] = 1;

  

            / * повторить размещение остальных королев * /

            if (solveNQUtil(board, col + 1))

                return true;

  

            / * При размещении ферзя на доске [i] [col]

               не приводит к решению, то

               удалить королеву с доски [i] [col] * /

            board[i][col] = 0; // ОБРАТНАЯ СВЯЗЬ

        }

    }

  

    / * Если королева не может быть помещена ни в одну строку в

        этот столбец col затем вернуть false * /

    return false;

}

  
/ * Эта функция решает проблему N Queen, используя

   Откат. В основном он использует функцию executeNQUtil () для

   решать проблему. Возвращает ложь, если королевы

   не может быть помещен, в противном случае вернуть true и

   печатает размещение королев в виде 1с.

   Обратите внимание, что может быть более одного

   решения, эта функция печатает один из

   Возможные решения. * /

bool solveNQ()

{

    int board[N][N] = { { 0, 0, 0, 0 },

                        { 0, 0, 0, 0 },

                        { 0, 0, 0, 0 },

                        { 0, 0, 0, 0 } };

  

    if (solveNQUtil(board, 0) == false) {

        printf("Solution does not exist");

        return false;

    }

  

    printSolution(board);

    return true;

}

  
// программа драйвера для проверки вышеуказанной функции

int main()

{

    solveNQ();

    return 0;

}

Выход:

0  0  1  0 
1  0  0  0 
0  0  0  1 
0  1  0  0

Пожалуйста, обратитесь к полной статье о проблеме N Queen | Backtracking-3 для более подробной информации!

Рекомендуемые посты:

C Программа для N Queen Задача | Откат-3

0.00 (0%) 0 votes