8 Queens 체스
| 8 Queens 체스 |
체스에서, 퀸 8개를 서로가 서로를 공격하지 못하도록 배치할 수 있다. 퀸 하나의 위치가 주어질 때, 퀸 8개를 배치하는 모든 방법을 구하는 프로그램을 작성하여라.
8개의 퀸에 대해 8개의 배치 모두를 계산하려고 하지 않도록 한다. 그렇게 하면 88번 연산해야되고, 시스템 과부하를 불러올 수 있다. 더 효율적인 방법을 찾도록 하여라.
입력 형식
입력의 첫 번째 줄은 데이터셋의 개수를 나타낸다. 두 번째 줄은 빈 줄이다. 각각의 데이터셋은 빈 칸으로 구분된 두 수를 가진다. 이 두 수는 8개의 퀸 중 한 개의 퀸이 무조건 있어야 할 칸의 위치를 나타낸다. 입력 데이터를 검사할 필요는 없다.좌표계는 맨 왼쪽 위의 칸을 (1,1)로 하고, 줄은 아래쪽으로 증가하며 칸은 오른쪽으로 증가한다. 모든 좌표는 (줄,칸)으로 나타내어진다. 예를 들어 (4,6)은 4번째 줄 6번째 칸을 의미한다.
각 데이터셋은 빈 줄로 구분한다.
출력 형식
각각의 데이터셋에 대한 출력은 여러 줄로 이루어질 수 있다. 퀸을 배치할 수 있는 각각의 경우에 대해서 한 줄씩 출력한다.가능한 경우에 대해 순차적으로 1부터 N까지 번호를 붙인다. 각각의 경우는 8개의 숫자로 이루어진다.
1 5 8 6 3 7 2 4
이와 같은 출력은 (1,1)(5,2)(8,3)(6,4)(3,5)(7,6)(2,7)(4,8)의 위치에 퀸이 있음을 나타낸다. 즉, 각 칸에 대해서 퀸이 있는 줄 번호를 출력하는 것이다.
아래 행렬을 출력하는 것이 아닙니다!
경우 1 경우 2 경우 3 경우 4 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0
퀸은 한 칸에 한 개밖에 있을 수 없으므로, 각 경우에 대해 한 줄만 출력하도록 한다.
각 데이터셋 사이에는 빈 줄을 출력한다.
입력 예시
1 1 1
출력 예시
SOLN COLUMN # 1 2 3 4 5 6 7 8 1 1 5 8 6 3 7 2 4 2 1 6 8 3 7 4 2 5 3 1 7 4 6 8 2 5 3 4 1 7 5 8 2 4 6 3
원문 출처 : http://acm.uva.es/p/v7/750.html 
2008년 1월 19일 이후 작성된 모든 글에 대해서 퍼가는 것을 금지합니다.
퍼가고자 하시는 분은 링크를 달아 주시기 바랍니다.
퍼가고자 하시는 분은 링크를 달아 주시기 바랍니다.
댓글을 달아 주세요