9663 : N-Queen

• gold 4

시간제한	메모리제한	정답비율
10초	128MB	46.6%

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

1<=n<15

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수 출력

python

import sys, os

problem_num = "9663"

path = os.getcwd() + f"\\txt\\{problem_num}" + ".txt"
sys.stdin = open(path, "r")
input = sys.stdin.readline

n = int(input())

8

def solveNQueens(n):
    def can_place(row, col):
        for i in range(row):
            if (
                board[i] == col
                or board[i] - i == col - row
                or board[i] + i == col + row
            ):
                return False
        return True

    def place_queen(row, n):
        if row == n:
            result.append(board[:])
            return
        for col in range(n):
            if can_place(row, col):
                board[row] = col
                place_queen(row + 1, n)
                board[row] = 0

    result = []
    board = [0] * n
    place_queen(0, n)
    return result

len(solveNQueens(5))

10

Python - class

class Board:
    def __init__(self, size):
        self.size = size
        self.columns = []

    def place_in_next_row(self, column):
        self.columns.append(column)

    def remove_in_current_row(self):
        return self.columns.pop()

    def is_this_column_safe_in_next_row(self, column):
        row = len(self.columns)
        for i in range(row):
            if (
                (self.columns[i] == column)
                or (self.columns[i] - i == column - row)
                or (self.columns[i] + i == column + row)
            ):
                return False
        return True

    def display(self):
        for row in range(self.size):
            for column in range(self.size):
                if column == self.columns[row]:
                    print("Q", end=" ")
                else:
                    print(".", end=" ")
            print()


class NQueens:
    def __init__(self, size):
        self.size = size
        self.solutions = 0
        self.solve()

    def solve(self):
        self.board = Board(self.size)
        self.place_queen(0)
        print("Found", self.solutions, "solutions")

    def place_queen(self, target_row):
        if target_row == self.size:
            self.solutions += 1
            # self.board.display()
            return
        for column in range(self.size):
            if self.board.is_this_column_safe_in_next_row(column):
                self.board.place_in_next_row(column)
                self.place_queen(target_row + 1)
                self.board.remove_in_current_row()

NQueens(8)

Found 92 solutions

<<<<<<< HEAD

<__main__.NQueens at 0x19c176ee930>
=======
<__main__.NQueens at 0x297fa78cfd0>
>>>>>>> c424194691c9cf2ab72e6a646a5c7648c066f8cc