Программа N-Queens в Python - PullRequest
Новая
       27

Программа N-Queens в Python

0 голосов
/ 07 апреля 2020

Проблема N Queen заключается в размещении N шахматных ферзей на N × N шахматной доске таким образом, чтобы две королевы не атаковали друг друга. Я решил эту программу ранее, но пытаюсь переделать свой код, чтобы отразить то, что я использовал для создания решения судоку. Кажется, я не могу найти логическую ошибку, но когда я запускаю код, ничего не печатается. Моя программа прилагается ниже, и если бы кто-нибудь мог найти мою ошибку, это было бы очень полезно! 

import numpy as np

def main():
    global n
    n = input("Enter N")
    n = int(n)
    global board
    board = np.zeros((n,n), dtype=int)
    solve_board()

def solve_board():

    for row in range(n):
        for col in range(n):
            if board[row][col] == 0: #no queen
                if (is_valid (board,row,col,n)):
                    board[row][col] = 1 #Assigning 1 for queen
                    solve_board()
                    board[row][col] = 0
            return False


    print('-'*n)
    for row in board:
        for col in row:
            if col == 1:
                print ("Q", end = " ")
            else:
                print (".", end = " ")


def is_valid(board,i,j,n):

    if 1 in board[i]: #Checking row
        return False

    for row in range(0,i): #Checking column
        if (board[row][j]==1):
            return False
    x,y = i,j

    while (x>=0 and y>=0): #left diagonal
         if (board[x][y]==1):
             return False
         x-=1
         y-=1

    x,y = i,j
    while (x>=0 and y<n): #right diagonal
         if (board[x][y]==1):
             return False
         x-=1
         y+=1
    return True

if __name__ == "__main__":
    main()

Вот как я решил этот код ранее, с изменением solve_board следующим образом. 

def solve_board(row):

    if(row == n):
        print('-'*n)
        for row in board:
            for col in row:
                if col == 1:
                    print ("Q", end = " ")
                else:
                    print (".", end = " ")
            print("")


    else:
        for col in range(n):
            if (is_valid (board,row,col,n)):
                board[row][col]=1
                solve_board(row+1)
                board[row][col] = 0
        return False

Вот откуда пришло вдохновение для моего текущего кода - решатель судоку, который я разработал, где использовал 2 вложенных цикла; один для строк и один для столбцов. Исходя из этого, я изменил свой solve_board (row) в моем исходном коде n-queens на текущую функцию без параметра. Этот код судоку работает отлично. 

def solve_board():

        global board
        for rowno in range(9):
            #print ("row",rowno)
            for colno in range(9):
                #print("col",colno)
                if board[rowno][colno] == 0:
                    for i in range(1,10):
                        #print(i)
                        if (is_valid(board,rowno,colno,i)):
                            board[rowno][colno]=i
                            solve_board()
                            board[rowno][colno]=0
                    return False

        print (np.matrix(board))

Я думаю, что проблема может быть ie в том факте, что в задаче N-Queens плата не заполняется, т. Е. Еще есть 0s, в то время как для судоку вся доска заполняется и, следовательно, когда '' if board [row] [col] == 0 '' ложно выходит из l oop и печатает. В проблеме N-Квинса, поскольку нули присутствуют всегда, это становится проблемой.

1 Ответ

0 голосов
/ 07 апреля 2020

Попробуйте это 

import numpy as np

def main():
    global n
    n = input("Enter N: ")
    n = int(n)
    global board
    board = np.zeros((n,n), dtype=int)
    solve_board()

def print_board():
    print('-'*n)
    for row in board:
        for col in row:
            if col == 1:
                print ("Q", end = " ")
            else:
                print (".", end = " ")
        print()


def is_valid(board,i,j,n):

    if 1 in board[i]: #Checking row
        return False

    for row in range(0, n): #Checking column
        if (board[row][j]==1):
            return False

    for k in range(0,n):
        for l in range(0,n):
            if (k+l==i+j) or (k-l==i-j):
                if board[k][l]==1:
                    return False
    return True

def solve_board():
    for row in range(n):
        for col in range(n):
            if board[row][col] == 0: #no queen
                if (is_valid (board,row,col,n)):
                    board[row][col] = 1 #Assigning 1 for queen
                    if np.count_nonzero(board) == n:
                      print_board()
                      return True
                    solve_board()
                    board[row][col] = 0
            else:
                  return False

if __name__ == "__main__":
    main()
...