Eight Queen Problem2 Discussion

EightQueenProblem2를 풀면서 혹은 푸는데 실패하면서 얻은 ThreeFs 공유, 토론

당신은 어떤 식으로 이 문제에 접근을 했고, 어떤 사고의 과정을 거쳤으며, 어떤 과정으로 프로그래밍을 했으며, 어떤 디자인 결정을 했습니까? 만약 실패했다면 당신이 했던 것 혹은 하지 않았던 것 중 무엇이 실패의 주요인이었다고 분석을 하십니까?

이번 경험을 통해 배운 것은 무엇입니까? 별로 없습니까? 그러면 다시 한번 생각해 보십시오. 남의 경험을 듣고, 남과 토론해 보십시오. 배운 것도 없는 일에 몇 시간을 투자하는 것은 아까운 일입니다.

처음 문제를 해결할 때, 아무 어려움이나 장애도 없었나요? 지금 뒤돌아볼 때에 자신이 거친 과정 중에 "개선되었으면 하는 부분"이 있나요? 만약 이 문제를 다시 처음부터 새로 풀기 시작한다면 역시 똑같은 방식으로 프로그래밍을 할 것 같습니까(see also EightQueenProblemSecondTry)? 조금 더 깔끔하고 쌈박하게 푸는 방법도 있을까요? 어떻게 처음에 접근했더라면 더 "깨끗한" 코드가 나올 수 있었을까요? 비슷한 문제에 직면했을 때 일반적으로 적용할 수 있는 어떤 "추상적 패러다임" 같은 것을 발견할 수 있을까요? 그 코드를 난생 처음 보는 사람이 있다고 했을 때 몇 분만에 그 코드를 이해시킬 수 있겠습니까? 만약 그 사람 혼자 그 코드를 본다면 쉽게 이해할 수 있을까요? 주석이 없이도요? 혹시 코드 내에 중복되는 정보는 없습니까? 본인의 의도가 모두 분명히 드러나고 있습니까? --김창준

문제를 나름대로 해결한 사람들은 StepwiseRefinement를 꼭 공부해 보세요.

이미 알고리즘 수업 시간을 통해 생각해본 문제이기에 주저없이 백트래킹(BackTracking) 기법을 선택해서 슈도코드를 종이에 작성해보았고 그를 바탕으로 구현에 들어갔습니다.(그냥 호기심에서 질문 하나. 알고리즘 수업에서 백트래킹을 배웠나요? 최근에는 대부분 AI쪽으로 끄집어 내서 가르치는 것이 추세입니다만... 교재가 무엇이었나요? --김창준 Foundations of Algorithms Using C++ Pseudocode, Second Edition 이었습니다. 0763706205 --이덕준) 백트래킹은 BruteForce식 알고리즘으로 확장하기에 용이해서 수정엔 그리 많은 시간이 걸리지 않았습니다. 만일 EightQueenProblem에 대한 사전 지식이 없었다면 두번째 과제에서 무척 당황했을것 같습니다. 이번 기회에 코드의 적응도도 중요함을 새삼 확인했습니다. --이덕준

이문제는 처음 접해본 문제라 먼저 종이에 체스판을 그리고 직접 문제를 풀려고 해보았습니다. 그리고 생각해낸것을 종이에 적고(1여왕은 가로,세로,대각선 같은줄에 있음 안된다. 2,먼저 첫번째 여왕을 놓고 두번째 여왕이 놓일 위치를 결정한다. 3 검사하는 방법은 가로->세로->대각선 순으로 한다. 4 여왕8개가 다놓이면
놓인 자리를 알려주고 끝난다.) 이 적은 것을 토대로 코딩을 하였고 처음 여왕은 0,0에 놓았습니다. 생각한대로 코딩을 했다고 생각하고 실행을 하자 무한루프를 돌았습니다. 전 처음 여왕이 어느 위치에 놓이던간데 거기에 맞는 답이 있는거라고 생각했는데 그것이 잘못되었다고 생각합니다. 처음부터 이 문제의 답을 알고있었다면 프로그램을 짜는데 좀더 간결한 코드를 짤수있었을텐데 란생각이 들어서 코딩을 멈추고 종이를 꺼내 문제를 풀기 시작했습니다. 하지만 답은 나오지않았고 제가푸는방식(여왕을 먼저 아무위치에나 놓고 그위치에 맞게 가로세로대각선에 없는 곳에 놓는다)을 그냥 코딩을 하였습니다. 처음 여왕의 위치를 8*8에 돌아가면서 놓고 검사를 하였습니다. 무식하긴하지만 답은 나왔습니다. 두번째 과제는 처음 코딩할때부터 판의 크기와 여왕의 숫자를 define해서 썻기 떄문에 숫자만 바꾸어 주었습니다. 하지만 답이 맞는지 확신이 서지 않습니다. 그이유는 이문제의 대한 알고리즘을 모르기 때문이라고 생각합니다. 그리고 c++을 썻는데 방학동안 쭉 자바로 플밍하다가 c++을 쓴이유가 비주얼툴의 디버깅을 이용하려는 생각이었는데 무슨문젠지 디버깅을 할수없어서 참 난감했습니다. 디버깅하면 금방알수있는 문제를 눈으로 차근차근 훓으면서 봐야했습니다. --최광식

두번째 문제에 답이 있었군요.. 역시 제답이 틀리군요 실패의 원인은 제대된 알고리즘이 없다는 것이라고 생각합니다 BackTracking 알고리즘을 보고 왔지만 이문제에 대한 설명도 보왔습니다. 하지만 알고리즘에 무지해서 그런지 잘 눈에 들어오지 않습니다. 그래도 밤새 풀면서(엉뚱한 답이다도) 오래만에 재밌었습니다. ^^-최광식

저는 뭐 아무것도 없이 문제만 보고 뛰어들었습니다. 일단 두번의 실패 (자세한 내용은 EightQueenProblemDiscussion)이후 세번째로 잡은 생각은 일단 한줄에 한개만 말이 들어간다는 점이었습니다. 그 점에 착안하여. 8*8의 모든 점을 돌게 만들었습니다. 좀 비효율적인데다가 아주 엉망인 소스 덕분에.. 문제는 풀었지만.. 수정/보완에 엄청난 시간이 걸리더군요(종료조건을 찾을수가 없었다는.. 그래서 수정에 30분 이상 걸렸습니다.) 후...... 이래저래 많은 생각을 하게 한 소스였습니다. ㅡ.ㅡ;; 왠지 더 허접해 진 느낌은.. --선호

원래 만들어놓은것이 전체가 표시되는 것이여서 특별히 고친것은 없었습니다. (단, 디버깅문제로 소스수정문제 빼고는..)
BackTracking 이야기가 나오는데, 대강 수업시간에 들은것이 있었지만 그냥 연습장에 판을 그리고 직접 궁리했고요. 결국은 전체 방법에 대한 비교방법이 되어서 (8단계에 대한 Tree) 최종 구현부분은 BackTracking의 방법이 되어버리긴 했네요. (사전지식에 대해 영향받음은 어쩔수 없겠죠. 아에 접해보지 않은이상은. --;) --석천

하..하하.. BackTracking이.. 뭐죠? 거꾸로.. 추적한다는 이야기같은데.. ㅡㅡa --선호

저는 일단 10*10배열을 만들었습니다.(경계선 생각하면 귀찮아지므로..) 그다음에 1~8까지 랜덤한 수를 두번 찾아서 보드의 아무 위치에다 Queen상수를 찍어줍니다. 그리고 그 주변의 8방향을 또 다른 상수 Other로 설정해줍니다. 이제 루프 돌면서 겹치지 않게 골라주면서 Queen으로 설정해주다가 8개가 되면 종료하게.. --인수

저는 문제를 보고 각 줄별로 작업을 해도 되겠지만, 맵에 퀸이 들어갈 수 있는 자리를 정하는 것을 위주로 햇습니다.
처음에는 자리를 잘못정해 실패 했을때 다음 자리로 옮겨가는 방법을 잘못 생각해 1시간 이상 소모했습니다.
두번째 문제에서는 최소한의 처음에 찾은 자리에 대해 가장 변화가 적은 자리부터(가능한) 생각하게 설계를 조금 바꿨습니다.

어제 서점에서 Foundations of Algorithms Using C++ Pseudocode를 봤습니다. 알고리즘 수업 시간에 백트래킹과 EightQueenProblem 문제를 교재를 통해 공부한 사람에게 이 활동은 소기의 효과가 거의 없겠더군요. 그럴 정도일줄은 정말 몰랐습니다. 대충 "이런 문제가 있다" 정도로만 언급되어 있을 주 알았는데... 어느 교재에도 구체적 "해답"이 나와있지 않을, ICPC(ACM의 세계 대학생 프로그래밍 경진대회) 문제 같은 것으로 할 걸 그랬나 봅니다. --김창준

음.. 전 처음 본 문제였습니다.
(위키 역시 머리털나고 처음인데... 이거 상당히 매력적이네요..^^;;
매번 위키나 블로그나.. 이야기만 들어봤지 실제 사용은 안해봤는데..
그런데 동시에 수정에 들어가면 어떻게 처리되는거지요? cvs처럼 되나?)

학교에서 알고리즘 시간에 너무 많이 놀았기 때문인지.. -_-;; 우리 학교에서는 BackTracking이 AI시간에 배우는 부분이라서 그런지..
BackTracking에 대해 찾아보니 결국 제가 한 방법이 그 방법이군요. 알고리즘자체는 좀 틀리지만 (전 리커시브를 이용...)
개념은 동일한 듯합니다.

어쨌든 참 좋았습니다. ^^;; 이런 자리를 만들어주신 주인님께 감사드립니다.

요즘들어 '복학하면 정말 열심히 공부해야겠다'는 생각이 자주 듭니다.
특히 자료구조나 알고리즘같은 기본 과목을 소홀히 했던게 너무 후회가 되는...T_T

내가 조금 성장하는 만큼 세상이 점점 넓어지는게 느껴집니다. 세상은 넓고 고수는 많다~~~

by Da_Answer