๊ธ€ ์ž‘์„ฑ์ž: ํƒ์‹œ ์šด์ „์‚ฌ
๋ฐ˜์‘ํ˜•

๐Ÿ‘ธ N-Queens

๋ฌธ์ œ

N-Queen ๋ฌธ์ œ๋Š” ํฌ๊ธฐ๊ฐ€ N ร— N์ธ ์ฒด์ŠคํŒ ์œ„์— ํ€ธ N๊ฐœ๋ฅผ ์„œ๋กœ ๊ณต๊ฒฉํ•  ์ˆ˜ ์—†๊ฒŒ ๋†“๋Š” ๋ฌธ์ œ์ด๋‹ค.
N์ด ์ฃผ์–ด์กŒ์„ ๋•Œ, ํ€ธ์„ ๋†“๋Š” ๋ฐฉ๋ฒ•์˜ ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

์ž…๋ ฅ

์ฒซ์งธ ์ค„์— N์ด ์ฃผ์–ด์ง„๋‹ค. (1 โ‰ค N < 15)

์ถœ๋ ฅ

์ฒซ์งธ ์ค„์— ํ€ธ N๊ฐœ๋ฅผ ์„œ๋กœ ๊ณต๊ฒฉํ•  ์ˆ˜ ์—†๊ฒŒ ๋†“๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค.

๐Ÿ˜ƒ ๋‚˜์˜ ํ’€์ด

def nqueen(sol, n):
    global count

    if len(sol) == n:    # ์ •๋‹ต ๋ฐฐ์—ด(sol)์˜ ๊ธธ์ด๊ฐ€ n๊ณผ ๊ฐ™์•„์ง€๋ฉด, count ์ฆ๊ฐ€
        count += 1
        return 0
    candidate = list(range(n))    # 0๋ถ€ํ„ฐ n-1๊นŒ์ง€๋ฅผ ํ›„๋ณด ๋ฐฐ์—ด๋กœ ๋งŒ๋“ ๋‹ค.
    for i in range(len(sol)):
        if sol[i] in candidate:    # ๊ฐ™์€ ์—ด์— ์žˆ๋Š” ์ง€ ํ™•์ธ
            candidate.remove(sol[i])    # ๊ฐ™์€ ์—ด์— ์žˆ๋‹ค๋ฉด ํ›„๋ณด์—์„œ ์ œ์™ธ
        distance = len(sol) - i
        if sol[i] + distance in candidate:    # ๊ฐ™์€ ๋Œ€๊ฐ์„ฑ ์ƒ(+)์— ์žˆ๋Š” ์ง€ ํ™•์ธ
            candidate.remove(sol[i] + distance)    # ๊ฐ™์€ ๋Œ€๊ฐ์„  ์ƒ์— ์žˆ๋‹ค๋ฉด ํ›„๋ณด์—์„œ ์ œ์™ธ
        if sol[i] - distance in candidate:    # ๊ฐ™์€ ๋Œ€๊ฐ์„  ์ƒ(-)์— ์žˆ๋Š” ์ง€ ํ™•์ธ
            candidate.remove(sol[i] - distance)    # ๊ฐ™์€ ๋Œ€๊ฐ์„  ์ƒ์— ์žˆ๋‹ค๋ฉด ํ›„๋ณด์—์„œ ์ œ์™ธ
    if candidate != []:
        for i in candidate:
            sol.append(i)    # ํ›„๋ณด์˜ ์š”์†Œ๋ฅผ ์ •๋‹ต ๋ฐฐ์—ด์˜ i+1๋กœ ์ถ”๊ฐ€
            nqueen(sol, n)    # ์žฌ๊ท€์ ์œผ๋กœ ๋‹ค์Œ ํ–‰๋„ ํ™•์ธ
    else:
        return 0

count = 0
num = int(input())

for i in range(num):    # ์ฒซ ํ–‰์˜ ๊ฒฝ์šฐ์˜ ์ˆ˜
    nqueen([i], num)

print(count)

N-Queens๋Š” ๋ฐฑํŠธ๋ž™ํ‚น ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์˜ˆ์‹œ๋กœ ์ž์ฃผ ์ด์šฉ๋˜๋Š” ๋ฌธ์ œ์ด๋‹ค. ๋ฐฑํŠธ๋ž™ํ‚น ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ๋…ธ๋“œ์˜ ์œ ๋ง์„ฑ ์ ๊ฒ€ ํ›„, ์œ ๋งํ•˜์ง€ ์•Š์œผ๋ฉด ๊ทธ ๋…ธ๋“œ์˜ ๋ถ€๋ชจ๋กœ ๋˜๋Œ์•„๊ฐ„ ํ›„ ๋‹ค๋ฅธ ์ž์‹ ๋…ธ๋“œ๋ฅผ ๊ฒ€์ƒ‰ํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค.

์šฐ์„ , ์ฒซ ํ–‰์˜ ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ์‚ฐ์ •ํ•˜๊ณ  nqueen ํ•จ์ˆ˜์— ๋„ฃ๋Š”๋‹ค. ๊ทธ๋ฆฌ๊ณ  ๊ฐ ํ–‰์˜ ํ›„๋ณด๊ตฐ์„ ๋งŒ๋“ค์–ด ์œ„์— ์„ค๋ช…ํ•œ ๋ฐฑํŠธ๋ž™ ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์œ ๋ง์„ฑ์ด ์žˆ๋Š” ์ž์‹๋…ธ๋“œ์™€ ์œ ๋ง์„ฑ์ด ์—†๋Š” ์ž์‹ ๋…ธ๋“œ๋ฅผ ๊ตฌ๋ถ„ํ•˜์—ฌ ํ•œ ํ–‰์”ฉ ์ถ”๊ฐ€ํ•˜๋ฉด์„œ, ์™„์„ฑ๋œ ์ •๋‹ต ๋ฐฐ์—ด์„ ๋งŒ๋“ค์–ด ๋‚˜๊ฐ„๋‹ค.

4X4 ํฌ๊ธฐ์˜ N-Queens ๋ฌธ์ œ

์ฐธ๊ณ ์ž๋ฃŒ

๋ฐ˜์‘ํ˜•