[python]白駿9663 N-Queen

https://www.acmicpc.net/problem/9663

**次の内容はYouTube「Baking Dog」のbacktraking講義を聞いて書いたものです.(youtube.com/watch?v=Enz2csssTCs&t=1237s)
この問題は遡及を利用して解決できる.
チェスでは、皇后が直線で前、後ろ、側、対角線を任意の方向に移動できるので、まず列(前後)、上対角線、下対角線方向に馬が存在するかどうかをチェックします.

check1 =[True]*n #열확인 
check2 =[True]*(n*2-1) #대각선확인 (x+y)
check3 =[True]*(n*2-1) #대각선확인 (y-x)

check 1:検査列

check 2:上向き対角線をチェック
たとえば、インデックス(2,2)、(1,1)、および(0,2)は対角線上に配置されます.
このとき(x,y),x+yともに同じものを確認できる.

check:下向き対角線検査
たとえば、インデックス(0,1)、(1,2)、および(2,3)は対角線上に配置されます.
このとき(x,y),y−xともに同じものを確認できる.

コード#コード#

import sys
input = sys.stdin.readline

n = int(input())
#퀸은 일직선으로 앞, 뒤, 옆, 대각선 어떤 방향이든 원하는 만큼 이동가능

check1 =[True]*n #열확인 
check2 =[True]*(n*2-1) #대각선확인 (x+y)
check3 =[True]*(n*2-1) #대각선확인 (x-y)
cnt=0

def func(num):
    global cnt
    
    if num ==n: #퀸을 모두 체스판에 놓았으면 cnt+=1
        cnt+=1
        return

    for i in range(n):
        if check1[i] and check2[i+num] and check3[num-i+n-1]: 
        #모두 조건을 만족하면(check3: num-i+n-1인 이유는 계산한 값이 음수가 되는 것을 방지하기 위해서이다.)
            check1[i]=False
            check2[i+num]=False
            check3[num-i+n-1]=False
            func(num+1)
            check1[i]=True
            check2[i+num]=True
            check3[num-i+n-1]=True
func(0)
print(cnt)