8Queue

N-Queues Puzzle

对于N皇后问题来说，可以形式化为一个CSP问题：

• $X={X_{ij}}_{n\times n}$

• $D_{ij}={0,1}$

• $$
  C=\begin{cases}
  \forall i,j,k:(X_{ij},X_{ik})\in{(0,0),(0,1),(1,0)}\
  \forall i,j,k:(X_{ij},X_{kj})\in{(0,0),(0,1),(1,0)}\
  \forall i,j,k:(X_{ij},X_{i+k,j+k})\in{(0,0),(0,1),(1,0)}\
  \forall i,j,k:(X_{ij},X_{i+k,j-k})\in{(0,0),(0,1),(1,0)}\
  \sum_{i,j}X_{ij}=N
  \end{cases}
  $$

这个描述有些复杂了，我们给出一个等价描述：

• $X={Q_k}_{k=1}^n$;

• $D_k={1,2,\cdots,N}$;

• $$
  \forall i,j, non-threatening(Q_i,Q_j)\(Q_1,Q_2)\in{(1,3),(1,4),\ldots}
  $$