N Rook Problem

문제 설명

체스판의 크기와 룩(Rook) 의 개수인 n이 매개변수로 주어졌을 때 n $\times$ n 체스판에 다음 조건을 만족하면서 n 개의 룩을 배치하는 경우의 수를 반환하는 solution 함수를 작성하시오.

조건

• n 개의 룩은 체스판 위에서 서로 공격할 수 없습니다.
• 행 번호와 열 번호가 같은 곳에는 룩을 둘 수 없습니다.

참고 내용

• N-Rook 문제(N Rook problem)는 n $\times$ n 체스판이 있을 때 n 개의 룩을 체스판에서 서로 공격할 수 없도록 배치하는 문제입니다.
• 룩(Rook)은 체스판에서 상,하,좌,우 총 4방향으로 거리에 상관없이 모든 기물을 공격할 수 있습니다.
• 일반적으로 n $\times$ n 체스판에서 n 개의 룩을 체스판에서 서로 공격할 수 없도록 배치하는 경우의 수는 $n!$ 입니다.

제한 사항

• n은 2 이상 10 이하의 자연수입니다.

예시 테스트케이스 설명

1번 테스트케이스 설명

• 2 $\times$ 2 체스판에는 2개의 룩을 주어진 조건에 맞게 배치하는 경우는 아래의 경우가 유일합니다.
  

2번 테스트케이스 설명

• 3 $\times$ 3 체스판에는 3개의 룩을 주어진 조건에 맞게 배치하는 경우는 아래의 경우로 2가지가 있습니다.

3번 테스트케이스 설명

• 5 $\times$ 5 체스판에는 5개의 룩을 주어진 조건에 맞게 배치하는 경우는 총 44가지이며 그중 하나는 아래와 같습니다.