이 놈이 아마 첫번째 레포트 였던걸로 기억합니다. 그 당시 나름대로 신경써서 만든다고 만든건데, ㅋㅋㅋ~~ 미완성이군요. 이 문제는 오일러가 제안한 기사 순례 문제에 대한 답을 구하는 프로그램입니다. 처음에는 거창하게 여러가지 알고리즘으로 여러가지 뷰 환경을 사용해서 보여줄 생각이었으나, 정작 구현된 것은 아마도 완드로프의 알고리즘으로 슬라이드 뷰만 보여주게 됩니다. 타임아웃 값도 무의미 하군요... ㅋㅋㅋ...
기사 순례 문제란, 체스판에서 기사가 특정 위치에서 시작해서 체스판의 전체 칸을 한번씩 다 방문하는 경로를 구하는 것을 말합니다. 물론 한 곳에 두번 갈 수 없는 것은 당연하겠죠. 퀸문제와 더불어서 백트래킹의 대표적인 샘플입니다. 즉, 이 문제를 푸는 방정식이 없다는 이야기죠.
방정식이 없어서 백트래킹을 할 경우 매우 시간이 오래 걸립니다. 실제로 8x8에서의 경로를 구하는 데에도 엄청난 시간이 소요됩니다. 그 많은 길들을 다 검사하니 당연하겠죠... 그런 문제에 혜안을 던진이가 있으니, 그가 바로 완드로프 입니다. 완드로프는 이 문제에 대한 천재적인 해결책을 제시했는데, 그건 다름 아닌 출구가 가장 작은 쪽으로 기사를 이동시키는 전략입니다. 즉, 1,1에서 갈수 있는 곳이 세곳이라고 할때 각각의 세곳에서 갈수 있는 곳을 조사한 후, 가장 적은 곳으로 기사를 이동 시키는 방법이죠. 이럴때 통하는 말이 Simply the best... ㅋㅋㅋ~~~ 그런데 사실 조금만 말을 놓고 고민해 본 사람이라면 금새 그 방법을 생각해 낼 만큼 간단한 것입니다. 완드로프는 이러한 방법을 1823년에 생각해 냈다고 전해집니다..
하지만 그의 천재적인 방법에도 몇가지 헛점이 있습니다. 그것은 첫째로, 모든 말의 이동 경로를 구하지는 못한다는 것. 둘째로, 보드의 크기가 특정 크기 이상이 될 경우 사각 지대가 발생한다는 것입니다. 사각 지대란 그의 알고리즘으로는 말이 도달하지 못하는 지역을 말합니다. 이러한 두 가지 헛점에도 불구하고, 아직도 그의 알고리즘은 기사 순례를 푸는 가장 천재적인 방법으로 인정 받고 있습니다.
후에 그의 헛점 중의 하나인 사각 지대를 없애는 방법으로는 보드를 조각내는 방법이 나왔습니다. 즉, 큰 보드를 작은 보드의 배열로 생각한 후, 문제를 풀기 시작하는 것이죠. 시작 점과 끝 점을 맞춰서 하면 사각 지대 없이 큰 보드를 순례 할 수 있다고 합니다.
사설이 너무 길었군요... ㅋㅋㅋ~~ 아래는 참고 자료와 소스, 그리고 제가 작성한 프로그램에 대한 간략한 설명입니다. mfc를 배우고 싶은 분들은 소스를 좀 더 좋게 고치는 것도 좋을 것 같군요... ㅋㅋㅋ
Download
Reference Book
- C++ 자료 구조론 - 저희 과 교수님의 교수님의 교수님이라고 불리는 사니 할아버지가 쓴 유명한 책입니다.
- Visual C++ Bible 6.X(영진) - 그 당시 유명한 책이었는데, 요즘은 악평이 많은 책이죠.
- Visual C++ Bible 6.X(삼양) - 요즘 호평을 받고 있는 책입니다.
처음 실행하면 뜨는 화면입니다. 보드의 크기를 입력하면 됩니다. 보드란 체스판의 크기를 말합니다. 가로, 세로를 입력하게 되면 나중에 그 만한 보드에서 기사가 이동하게 됩니다.
첫 화면에서 다음을 누른 경우 표시되는 화면입니다. 기사의 첫 시작 위치를 지정하는 화면입니다. x,y는 각각 보드에서 기사가 처음 배치될 위치를 말합니다. 즉, 기사가 어디서 여행을 시작할지 정해주는 것이라 생각하면 됩니다. 그 다음 나오는 내용은 모두 변수 처리가 안된 것들입니다. 그냥 다음, 다음 누르시면 됩니다.
위의 단계를 거치면 위와 같은 보드가 표시됩니다. 보드에서 "시작해 보세요" 버튼을 누르면 말이 첫 위치에서 다음 위치로 이동하게 됩니다.