E D R , A S I H C RSS

Eight Queen Problem Discussion

EightQueenProblem을 풀면서 혹은 푸는데 실패하면서 얻은 ThreeFs를 이야기해 봅시다.

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

만약 당신보다 더 짧은 시간에, 더 짧은 코드로 문제를 해결한 사람이 있다면, 그 사람과 함께 PairProgramming (혹은 NetMeeting 등을 이용, VirtualPairProgramming)을 해서 그 문제를 함께 새로 풀어보세요. 당신은 무엇을 배웠습니까? 그 사람은 어떤 방식으로 프로그램의 올바름(correctness)을 확인합니까? 그 사람은 디버깅을 어떻게 합니까(혹은 디버깅이 거의 필요하지 않은 접근법이 있던가요)? 그 사람은 어떤 순서로 문제에 접근해 갑니까? 그 사람은 어느 정도로까지 코드를 모듈화 합니까? 이 경험이 당신의 프로그래밍에 앞으로 어떤 변화를 불러올 것이라 생각합니까?

일단 구석에서부터 채워나가면 실패한다.. (7개까지는 되지만.. 여덟개는 되지 않는다) 뭔가 다른방법을 찾아 보아야겠다.

두번째.. 가장 작은 자리수를 채워나가면 실패한다 (역시 7개까지 되지만.. 여덟개는 되지 않는다.) 역시 다른방법을 찾아야겠다.

세번째각도.. 성공적이다. 일단 한줄에 한개의 퀸만 들어간다는 점에 착안하여 모든 점을 검사하였다... 비효율적이지만 확실한 방법ㅡㅡ;

-- 선호

  • Facts - 접근방법:
말 그대로 그냥 정공법 (이 될지는 모르겠지만. -_-;)으로 나갔다. 여기서는 테스트 코드로 대신을..

맨 처음에는 해당 체스판에 대한 적절한 처리를 하는 것 부터 접근해 나아갔다. 판에 퀸을 놓는 것 부터 시작.
~cpp 
    def testBoardEmpty (self):
        self.assertEquals (self.bd.GetData (2,2), 0)

    def testSetQueen (self):
        self.bd.SetQueen (2,2)
        self.assertEquals (self.bd.GetData (2,2) ,1)

    def testPrintBoard (self):
        self.bd.SetQueen (1,1)
        self.bd.SetQueen (2,2)
        self.bd.SetQueen (7,7)
        self.assertEquals (self.bd.PrintBoard (), '''00000000\n01000000\n00100000\n00000000\n00000000\n00000000\n00000000\n00000001\n''')

그 다음에는 '퀸을 놓을 수 있는 위치가 안전한 곳일까?' 하는 점에 대해 접근. 이를 SelftyZone 이라 칭했다. 이를 체크하기 위해서는 가로/세로/대각선방향을 모두 체크해야 하므로 다시 4개의 작은 모듈로 나누어졌다. 그중 대각선 체크의 경우 처음 비교를 시작할 위치를 측정하기 위한 모듈을 하나 더 추출하게 되었다.
~cpp 
    def testIsSelftyZone (self):
        self.bd.SetQueen (2,2)
        self.assertEquals (self.bd.IsSelftyZone (3,3), 0)
        self.assertEquals (self.bd.IsSelftyZone (1,5), 1)

    def testFindQueenInSameVertical (self):
        self.bd.SetQueen (2,2)
        self.assertEquals (self.bd.FindQueenInSameVertical (2), 1)
        self.assertEquals (self.bd.FindQueenInSameVertical (3), 0)

    def testFindQueenInSameHorizonal (self):
        self.bd.SetQueen (2,2)
        self.assertEquals (self.bd.FindQueenInSameHorizonal (2), 1)
        self.assertEquals (self.bd.FindQueenInSameHorizonal (3), 0)

    def testFindQueenInSameCrossLeftTopToRightBottom (self):
        self.bd.SetQueen (2,2)
        self.assertEquals (self.bd.FindQueenInSameCrossLeftTopToRightBottom (3,3), 1)
        self.assertEquals (self.bd.FindQueenInSameCrossLeftTopToRightBottom (1,1), 1)
        self.assertEquals (self.bd.FindQueenInSameCrossLeftTopToRightBottom (4,1), 0)

    def testFindQueenInSameCrossLeftBottomToRightTop (self):
        self.bd.SetQueen (2,2)
        self.assertEquals (self.bd.FindQueenInSameCrossLeftBottomToRightTop (3,3), 0)
        self.assertEquals (self.bd.FindQueenInSameCrossLeftBottomToRightTop (3,1), 1)
        self.assertEquals (self.bd.FindQueenInSameCrossLeftBottomToRightTop (1,3), 1)

~cpp 
    def testGetFirstCornerInCrossLeftTopToRightBottom (self):
        self.assertEquals (self.bd.GetFirstCornerInCrossLeftTopToRightBottom (3,3), (0,0))
        self.assertEquals (self.bd.GetFirstCornerInCrossLeftTopToRightBottom (4,3), (1,0))
        self.assertEquals (self.bd.GetFirstCornerInCrossLeftTopToRightBottom (1,5), (0,4))
        self.assertEquals (self.bd.GetFirstCornerInCrossLeftTopToRightBottom (0,0), (0,0))

    def testGetFirstCornerInCrossLeftBottomToRightTop (self):
        self.assertEquals (self.bd.GetFirstCornerInCrossLeftBottomToRightTop (2,2), (0,4))
        self.assertEquals (self.bd.GetFirstCornerInCrossLeftBottomToRightTop (3,5), (1,7))
        self.assertEquals (self.bd.GetFirstCornerInCrossLeftBottomToRightTop (7,7), (7,7))

해당 자리에 놓았을 경우. 다른 퀸을 공격할 수 있는 위치에 대해 알아보기 위한 부분에 대해 생각했다.
~cpp 
    def testIsAttackableOthers (self):
        self.bd.SetQueen (2,2)
        self.assertEquals (self.bd.IsAttackableOthers (3,3),1)
        self.bd.SetQueen (7,1)
        self.assertEquals (self.bd.IsAttackableOthers (7,1),0)
        self.assertEquals (self.bd.IsAttackableOthers (4,4),1)

해당 level (0번째줄~7번째줄) 에 대해서 공격당하지 않는 위치를 얻어내기 위한 리스트 (정확히는 튜플)를 얻어내는 부분.
~cpp 
    def testGetUnAttackablePositon (self):
        self.bd.SetQueen (0,0)
        self.assertEquals (self.bd.GetUnAttackablePosition (1), ((2,1),(3,1),(4,1),(5,1),(6,1),(7,1)))
        self.assertEquals (self.bd.GetUnAttackablePosition (2), ((1,2),(3,2),(4,2),(5,2),(6,2),(7,2)))

해당 알고리즘을 구현하기 위한 기반이 되는 체크 관련 부분에 대해 (여기까지) 만드는데는 52분정도가량이 걸렸다. 하지만, 정작 Queen 을 배열하는 알고리즘을 생각해내는데 3시간 가량이 걸렸다. --;

  • Feelings - 느낀점: 시간이 넘 오래걸려서 한편으로는 쪽팔리긴 하다. -_-; 뭐.. 알고리즘 부분에 대해서 너무 시간을 오래 끌었다. 왜 그랬을까 생각하는데.. 아마 특정 알고리즘들이 먼저 머릿속에 떠올라서가 아닐까 한다. (이 부분에 대해서는 stack을 쓸까 recursive 로 대신할까 이리저리군시렁군시렁) 이런 부분에 대해서는 어떻게 test가능한 부분으로 접근해나갈수 있을까.

-- 석천

석천군에게.

자신에게 항상 "What is the simplest thing that could possibly work?"라는 질문을 하면서 TestDrivenDevelopment를 했나요? 테스트/코드 사이클을 진행하면서 스텝을 작게 하려고 노력했나요? 중간에 진척이 별로 없는 경우, 어떤 액션을 취했나요? 그 때 테스트 사이클의 스텝을 더 작게하려고 했나요? 만약 다시 같은 문제를 새로 푼다면 어떤 순서로 테스트를 하고 싶나요? (직접 다시 한번 새로 시작하는 것도 강력 추천) 왜 다른 사람들에 비해 시간이 상대적으로 많이 걸렸을까요? 테스트 코드를 사용한 것이 그 시간만큼의 이득이 있었나요? TestDrivenDevelopment를 해내가면서 현재 패스하려고 하는 테스트 케이스에서 무엇을 배웠나요? 켄트벡이 말하는 것처럼 사고의 도구가 되어 주었나요? 참고로 저는 EightQueenProblem을 파이썬으로 약 30분 정도 시간에 50 라인 이내로(테스트 코드 제외) 풀었습니다. TestDrivenDevelopment로요. --김창준

.

직접 다시 새로 시작하는 것에 대해서는 비교계산을 내리기 힘들것 같네요. (더 좋은 디자인을 얻어내는 것과 훈련라는 점에서는 물론 저도 추천) 제가 잘못했다고 생각되는 부분은, 퀸을 배열하는 방법 알고리즘 부분에 대해 TestDrivenDevelopment 를 지키지 못했다는 점이죠. (머릿속에 먼저 재귀함수 호출 등의 특정 알고리즘들이 먼저 떠오른지라. )

알고리즘 궁리 부분에 대해서도 80/20 법칙이 통용되려나요. :) 3시간이 걸린 부분이 바로 다음 부분이였는데요.
~cpp 
    def DefineQueen (self, Level):
        if Level == 8:
            self.Count = self.Count + 1
            print "%d. level : %d \n" % (self.Count, Level)
            print self.PrintBoard ()
            return 0
        
        PositionList = self.GetUnAttackablePosition (Level)

        for position in PositionList:
            self.SetQueen (position[0], position[1])
            Ret = self.DefineQueen (Level + 1)
            if not Ret:
                self.SetData (position[0],position[1], 0)
즉, 실제 Queen의 위치들을 정의하는 재귀호출 코드인데요. 이 부분에 대한 TestCase 는 최종적으로 얻어낸 판에 대해 올바른 Queen의 배열인지 확인하는 부분이 되어야 겠죠. 연습장에 계속 의사코드를 적어놓긴 했었는데, 적어놓고 맞을것이다라는 확신을 계속 못했죠. 확신을 위해서는 테스트코드로 뽑아낼 수 있어야 할텐데, 그때당시 이 부분에 대해서 테스트코드를 못만들었죠.

지금이라면 'Level 8일때 바로 판을 찍지 않고, 저 상황의 데이터구조체를 그대로 복사해서 결과만 넣어놓는 리스트를 하나 더 만들고, 그 결과들에 대해 올바른 배열을 했는지 테스트하는 코드를 뽑아낼 수 있겠다' 라는 아이디어가 떠오르긴 하네요. (그렇더라도 100라인은 넘어갈것 같긴 하네요. ^^;)

사고의 도구로써는 연습장과 TFP 둘 다 이용했지만, 순수하게 적용하지는 않았습니다. (위의 Queen을 놓는 부분에 대한 재귀호출부분에서는 적용못함) 테스트작성시간/코드작성시간 등에 대한 관리는 하지 않았습니다. (이 부분에 대해서는 반성을. ^^;) 흠.. 그리고 'The Simplest Thing'을 찾아나갔다기 보다도, 이미 해당 문제에 대해서 의사코드를 생각하고, 해당 코드에 대해 Top-Down 형태로 모듈을 나눈뒤에 모듈에 대해 테스트를 만들어갔다는 생각이 드네요. --석천

지금가지 모두 C++, Python, Java 등 OOPL을 이용했는데 그 중 OOP로 푼 사람은 아무도 없네요 -- class 키워드가 있다고 OOP라고 하긴 힘들겠죠. 사람은 시간이 급하다고 생각이 들수록 평소 익숙한 도구와 멘탈리티로 돌아가려고 하죠. 어쩌면 OOP가 편하고 수월하다고 느끼는 사람이 없다는 이야기가 될지도 모르겠네요. 물론 모든 문제를 푸는데 OOP가 좋다는 이야기를 하려는 것은 아닙니다만. --김창준

이런 암호같은 프로그램도 있다는..

Eight Queens program written by Marcel van Kervinck
~cpp 
/* Marcel van Kervinck <xxxxxxx@xxxxx.xxx.xxx.xx> */
t(a,b,c){int d=0,e=a&~b&~c,f=1;if(a)for(f=0;d=(e-=d)&-e;f+=t(a-d,(b+d)*2,(
c+d)/2));return f;}main(q){scanf("%d",&q);printf("%d\n",t(~(~0<<q),0,0));}

When the program is run, one has to give a number n (smaller than 32), and the program will return in how many ways n Queens can be put on a n by n board in such a way that they cannot beat each other.
Note that the d=(e-=d)&-e; statement can be compiled wrong on certain compilers. The inner assignment should be executed first. Otherwise replace it with e-=d,d=e&-e;.


실패한 이유
  • 문제 인식 잘못, 풀이 계획 잘못. 완성되었다고 생각한 순간에, 크나큰 실수가 있었음 인지하였다. 답이 없는 줄 알았다. TT
  • 말에 대한 정보를 체스판에만 가지게 하였다. (문제 분석 소홀히한 댓가 TT)
  • TFD로 시도하였는데. test와 code간 이동이 빠르지 못하였다. 즉, test부분이 충분히 작아지지 못한 것 같다.

내일 다시 도전하자...조영봉
DeleteMe) 앗.. 붉은미르님도 들리셨군요..~ ^^ --1002

ThreeFs
이승한PairProgramming을 하며 문제를 풀었습니다. TDD를 하지 않고 30분을 작성했고 나머지 1시간30분을 TDD로 했습니다.

적당한 자료구조를 끝까지 찾지 못해 헤맸다는 느낌입니다. 처음 TDD를 접하는 파트너로서는 테스트를 빨리 이해할 수 없어서 한 동안 페어 사이에 공백이 느껴졌습니다. 속도를 늦추고 파트너에 맞추자, 파트너가 드라이브를 하는 의욕을 보였습니다. 완성하지 못해 다른 이의 코드와 비교하는 시간이 없어서 안타깝습니다.

적당한 자료구조를 생각하는 시간이 초반이든, 중반이든 꼭 필요하다는 생각이 듭니다. --Leonardong
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2009-05-27 07:09:19
Processing time 0.7961 sec