Рубрики

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

# Python программа для решения N Queen
# Проблема с использованием возврата

  

global N

N = 4

  

def printSolution(board):

    for i in range(N):

        for j in range(N):

            print board[i][j],

        print

  

  
# Полезная функция, чтобы проверить, может ли королева
# быть размещенным на доске [row] [col]. Обратите внимание, что это
Функция # вызывается, когда королевы "col"
# уже размещены в столбцах от 0 до цв -1.
# Так что нам нужно проверить только левую сторону для
# атакующие королевы

def isSafe(board, row, col):

  

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

    for i in range(col):

        if board[row][i] == 1:

            return False

  

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

    for i, j in zip(range(row, -1, -1), range(col, -1, -1)):

        if board[i][j] == 1:

            return False

  

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

    for i, j in zip(range(row, N, 1), range(col, -1, -1)):

        if board[i][j] == 1:

            return False

  

    return True

  

def solveNQUtil(board, col):

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

    # затем верните true

    if col >= N:

        return True

  

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

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

    for i in range(N):

  

        if isSafe(board, i, col):

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

            board[i][col] = 1

  

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

            if solveNQUtil(board, col + 1) == True:

                return True

  

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

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

            # королева с доски [я] [кол]

            board[i][col] = 0

  

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

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

    return False

  
# Эта функция решает проблему N Queen, используя
Отступление. В основном он использует функцию executeNQUtil () для
# решать проблему. Возвращает ложь, если королевы
# не может быть размещен, иначе верните true и
# размещение королев в виде 1с.
# обратите внимание, что может быть более одного
# решения, эта функция печатает один из
# выполнимые решения.

def solveNQ():

    board = [ [0, 0, 0, 0],

              [0, 0, 0, 0],

              [0, 0, 0, 0],

              [0, 0, 0, 0]

             ]

  

    if solveNQUtil(board, 0) == False:

        print "Solution does not exist"

        return False

  

    printSolution(board)

    return True

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

  
# Этот код предоставлен Divyanshu Mehta

Выход:

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

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

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

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

0.00 (0%) 0 votes