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μκ°μ΄ κ±Έλ¦° λΆλΆμ΄ λ°λ‘ λ€μ λΆλΆμ΄μλλ°μ.
.png)
~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;.
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λΆλΆμ΄ μΆ©λΆν μμμ§μ§ λͺ»ν κ² κ°λ€.
ThreeFs
μ΄μΉνκ³Ό PairProgrammingμ νλ©° λ¬Έμ λ₯Ό νμμ΅λλ€. TDDλ₯Ό νμ§ μκ³ 30λΆμ μμ±νκ³ λλ¨Έμ§ 1μκ°30λΆμ TDDλ‘ νμ΅λλ€.
μ΄μΉνκ³Ό PairProgrammingμ νλ©° λ¬Έμ λ₯Ό νμμ΅λλ€. TDDλ₯Ό νμ§ μκ³ 30λΆμ μμ±νκ³ λλ¨Έμ§ 1μκ°30λΆμ TDDλ‘ νμ΅λλ€.
μ λΉν μλ£κ΅¬μ‘°λ₯Ό λκΉμ§ μ°Ύμ§ λͺ»ν΄ ν€λ§Έλ€λ λλμ
λλ€. μ²μ TDDλ₯Ό μ νλ ννΈλλ‘μλ ν
μ€νΈλ₯Ό 빨리 μ΄ν΄ν μ μμ΄μ ν λμ νμ΄ μ¬μ΄μ κ³΅λ°±μ΄ λκ»΄μ‘μ΅λλ€. μλλ₯Ό λ¦μΆκ³ ννΈλμ λ§μΆμ, ννΈλκ° λλΌμ΄λΈλ₯Ό νλ μμμ 보μμ΅λλ€. μμ±νμ§ λͺ»ν΄ λ€λ₯Έ μ΄μ μ½λμ λΉκ΅νλ μκ°μ΄ μμ΄μ μνκΉμ΅λλ€.
μ λΉν μλ£κ΅¬μ‘°λ₯Ό μκ°νλ μκ°μ΄ μ΄λ°μ΄λ , μ€λ°μ΄λ κΌ νμνλ€λ μκ°μ΄ λλλ€. --Leonardong