AEKJOON #9663 N-Queen (backtracking, DFS) - python

6081 ワード
DFS Backtracking baekjoon python テキストリンク

N-Queen


ソース:白駿#9663
タイムアウトメモリ制限10秒128 MB

質問する


N-Queen問題の大きさはN× これは,N個のチェス盤上のN個の皇后が互いに攻撃し合うことができない問題である.
Nが与えられた場合,解放後の方法の数を計算するプログラムを作成してください.

入力


1行目はNです.(1 ≤ N < 15)

しゅつりょく


1行目でN個の皇后が互いに攻撃できない場合は、数字を出力します.

I/O例


入力例1


8

サンプル出力1


92

に答える

  • 関連概念:Algorithm-class-Backtracking2

    • の意見を打診

  • N−Queen問題は遡及型の最も代表的な問題である.
    • 同じ列、同じ行、対角線上に置かないように、N個のQueenを置かなければなりません.重要なのは、
  • bounding関数(ここではplace 함수)をどのように記述するかです.
  • でfor文を0からk-1に移動し、次のエントリを確認します.
    同じ列
  • にありますか.(board[j] == i)
  • 対角線にありますか.(abs(board[j]-i) == abs(j-k))
  • 対角線の場合、勾配は1 or-1であり、上記のように計算される.
  • 本関数backtrackにおいて、for文を0からn−1に遷移しplace関数を通過すると、kが終点に到達したか否かを判別して到着するとcountが1増加し、そうでなければkに1を加えた値が再帰的に戻される.

    • python code

    # 백준 9663번 N-Queen 
from sys import stdin
input = stdin.readline
n = int(input())
board = [-1]*n

count = 0
def backtrack(board, k, n):
    global count
        
    for i in range(n):
        if place(board, k, i):
            board[k] = i
            if k == n-1:
                count += 1
                # print('chess :', end=" ")
                # for j in range(n):
                #     print(board[j], end=" ")
                # print()
                return
            else:
                backtrack(board, k+1, n)
            

def place(board, k, i):
    for j in range(k):
        if (board[j] == i) or (abs(board[j]-i) == abs(j-k)):
            return False
    return True


backtrack(board, 0, n)
print(count)
    あなたのJipsterスタープリントにCLIを加えてください
    [HackerRank] Designer PDF Viewer