체스 기물 배치 문제 (N-Queen, Rook, Bishop, ...)

N*N 체스판에 N개의 퀸을 배치하는 유명한 문제. (Eight queens puzzle)

(작성중..)

그냥 평범한 NxN보드에 N개의 룩을 배치하는 것은 간단히 N!이다.

그래서 보통 물어보는 것은, 몇몇 칸에 장애물이 놓여져 있는 보드에 룩을 배치하는 것이다. 이분매칭 문제로 변환해서 풀수 있다

https://oeis.org/A002464

N*N 체스판에 N개의 킹을, 각 열과 행에 한개씩만 들어가도록 배치하는 문제.

백준에서는 궁전 문제가 여기에 해당된다. 이때는 킹과 룩의 움직임을 합쳐놓은 '궁전'이라는 기물을 정의하고, 궁전 N개를 배치하는 문제로 표현했다.

킹의 공격범위에 들어가지 않으려면, 인접한 열에 배치된 킹들은 인접한 행에 존재하면 안된다. 이것을 바꿔 말하면, 1~N까지의 숫자로 만들어지는 퍼뮤테이션 중에서 인접한 두 수의 차가 모두 2이상인 퍼뮤테이션의 갯수를 찾는 문제라고도 볼수있다.

이것을 기반으로 포함배제 정리를 잘 섞어서 식을 만들면 n!에서 한페어가 인접한 퍼뮤테이션을 빼고, 두 페어가 인접한 퍼뮤테이션을 더하고,.. 이런식으로 정리해서 $ n!+\sum_{k=1}^n {(-1)^k}(n-k)!\sum_{i=1}^k 2^{i} \binom{k-1}{i-1}\binom{n-k+1}{i} $ 처럼 정리가 가능하긴 하다. (직접 유도해보지는 않았다.. 설명은 https://www.quora.com/What-is-the-number-of-permutations-possible-for-5-elements-after-a-change-in-order-no-two-adjacent-elements-remain-next-to-each-other 참고)