Рубрики

Java-программа для задачи 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}

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

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

public class NQueenProblem {

    final int N = 4;

  

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

    void printSolution(int board[][])

    {

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

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

                System.out.print(" " + board[i][j]

                                 + " ");

            System.out.println();

        }

    }

  

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

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

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

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

       проверять только левую сторону на атакующие королевы * /

    boolean isSafe(int board[][], int row, int col)

    {

        int i, j;

  

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

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

            if (board[row][i] == 1)

                return false;

  

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

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

            if (board[i][j] == 1)

                return false;

  

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

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

            if (board[i][j] == 1)

                return false;

  

        return true;

    }

  

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

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

    boolean solveNQUtil(int board[][], 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) == true)

                    return true;

  

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

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

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

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

            }

        }

  

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

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

        return false;

    }

  

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

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

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

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

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

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

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

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

    boolean solveNQ()

    {

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

                          { 0, 0, 0, 0 },

                          { 0, 0, 0, 0 },

                          { 0, 0, 0, 0 } };

  

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

            System.out.print("Solution does not exist");

            return false;

        }

  

        printSolution(board);

        return true;

    }

  

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

    public static void main(String args[])

    {

        NQueenProblem Queen = new NQueenProblem();

        Queen.solveNQ();

    }

}
// Этот код предоставлен Abhishek Shankhadhar

Выход:

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

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

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

Java-программа для задачи N Queen | Откат-3

0.00 (0%) 0 votes