-
2차원 배열에서 동일한 행, 열, 대각선 상에 돌이 놓이면 안되게하는 알고리즘.
1
2
3
4
1
2
3
4
- 1행 1열 부터 놓아 보면서 진행한다.
1
2
3
4
1
1
2
x
x
2
3
x
x
x
x
4
-
2행 : 1행 1열에 놓으면 2행 1열과 2행 2열은 두지 못한다.(같은 열 / 대각)
-
3행 : 둘 수 있는 곳이 없다.(같은 열 / 대각) 2행에서의 선택을 번복한다.
1
2
3
4
1
1
2
x
x
x
2
3
x
3
4
x
x
x
-
2행 : 2행 4열로 선택 바꾼다.
-
3행 : 3행 2열이 적합하다.
-
4행 : 둘 수 있는 곳이 없다. 3행에서의 선택은 번복한다.
1
2
3
4
1
1
2
x
x
x
2
3
x
x
x
x
4
-
3행 : 3행에서의 선택을 번복하려 했는데 자리가 없다. 2행으로 올라가서 번복한다.
-
2행 : 2행에서도 번복할 자리가 없다. 1행으로 올라간다.
1
2
3
4
1
x
1
2
x
x
x
2
3
3
4
x
x
4
-
1행 : 1행 1열의 자리로는 돌을 다 놓을 수 없었다. 1행 2열로 번복.
-
2행 : 2행 4열에 자리가 있다.
-
3행 : 3행 1열에 자리가 있다.
-
4행 : 4행 3열에 놓으며 모든 자리에 돌을 놓았다.
-
상태공간트리를 그려보며 진행하는 방식과 같다. 상태공간트리의 특징은 모든 노드를 탐색할 필요가 없이 솔루션에 접근 가능하다.
-
상태공간트리를 깊이 우선 탐색으로 진행.
-최종 5x5 짜리 2차원 배열
