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

===== N-Queens =====
  * N*N 체스판에 N개의 퀸을 배치하는 유명한 문제. ([[wp>Eight queens puzzle]])
  * 배치할수 있는 방법의 갯수를 세는 문제는 백트래킹 연습문제로 흔히 등장한다.
    * 가지치기를 잘 할 수 있는 요령들도 많이 연구되어있다.
    * 하지만, 가지치기를 잘하더라도, N의 범위가 조금만 커져도 시간이 너무오래 걸린다. [[ps:problems:boj:9663]]에서는 N의 범위를 14이하로 제한하고 있고, 내가 python3으로 구현했을때에는 아무리 열심히 해도 15초 가량이 걸렸다. 
    * Exact Cover 문제로도 변환 가능하기 때문에, Knuth algorithm X 를 사용하는 것도 가능하긴 할것이다. 하지만 구현은 안해봤다.
  * 배치하는 방법 중에서 아무거나 한가지를 묻는 문제도 있다.
    * 이 경우는 솔루션을 백트래킹으로 찾지 않아도 된다, 계단형으로 배치하는 방법은 공식을 이용해서 바로 구할수 있기 때문이다. 방법은 [[https://en.wikipedia.org/wiki/Eight_queens_puzzle#Existence_of_solutions|여기]] 참고.
    * 여기에 해당하는 문제는 [[ps:problems:boj:3344]]와 [[ps:problems:boj:21133]]가 있다.

===== Rook 배치 =====
  * (작성중..)
  * 그냥 평범한 NxN보드에 N개의 룩을 배치하는 것은 간단히 N!이다.   
  * 그래서 보통 물어보는 것은, 몇몇 칸에 장애물이 놓여져 있는 보드에 룩을 배치하는 것이다. 이분매칭 문제로 변환해서 풀수 있다 
 
===== Hertzsprung's problem =====
  * [[https://oeis.org/A002464]]
  * N*N 체스판에 N개의 킹을, 각 열과 행에 한개씩만 들어가도록 배치하는 문제.
  * 백준에서는 [[ps:problems:boj:16878]] 문제가 여기에 해당된다. 이때는 킹과 룩의 움직임을 합쳐놓은 '궁전'이라는 기물을 정의하고, 궁전 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]] 참고)
  * 하지만 이 방식으로는 여러개의 n에 대해서 계산하기가 매우 힘들다. 대신, [[https://oeis.org/A002464]]에 적혀있는 점화식을 이용하면, a[0..n]을 O(n)에 모두 구할수 있다.
    * If n = 0 or 1 then a(n) = 1; if n = 2 or 3 then a(n) = 0; otherwise a(n) = (n+1)*a(n-1) - (n-2)*a(n-2) - (n-5)*a(n-3) + (n-3)*a(n-4).
    * 이 식이 어떻게 나왔는지는 전혀 감이 없다. 아마 이 논문 - [[https://www.jstor.org/stable/2321990|The Probability that Neighbors Remain Neighbors After Random Rearrangements]]) 에 있는거 같은데 읽어보지는 않았다.