반응형 백트랙킹1 Eight queens problem 체스판에서 8개의 퀸을 서로 죽이지 않도록 배치하는 문제는 알고리즘에서 많이 다루어집니다. 여기서는 알고리즘의 문제도 있지만, 어떻게 프로그램을 작성해야지 더 효율적일지를 생각해볼까 합니다. 체스에서 퀸은 전후좌우 그리고 대각선까지 장애물이 있지 않는 한 원하는 칸 수만큼 이동할 수 있습니다. 체스판에서 8개의 퀸을 어떻게 배치하면 서로 잡을 수 없는 위치에 놓일까 하는 것입니다. 이 조건을 간단하게 정리하면 다음과 같습니다. 각 열에는 오직 하나의 퀸만 존재해야 한다. 각 행에는 오직 하나의 퀸만 존재해야 한다. 각각의 퀸의 대각선에 다른 퀸이 존재해서는 안 된다. 여기서 첫번째 조건과 두번째 조건은 손쉽게 프로그램으로 작성할 수 있습니다. 만약 8개의 룩(Rook)을 가지고 이 문제를 냈다면, 수학적.. 2011. 11. 14. 이전 1 다음 728x90
