E D R , A S I H C RSS

Eight Queen Problem2 Discussion

EightQueenProblem2 ํ’€ฉด„œ ํ˜€ ํ‘ธŠ”ฐ ‹คํŒจํ•˜ฉด„œ –ป€ ThreeFs ณตœ , ํ† ก 

‹‹ € –ด–ค ‹œกœ ด ฌธ œ—  ‘„ ํ–ˆณ , –ด–ค ‚ฌณ ˜  •„ ณคœฉฐ, –ด–ค  •œกœ ํ”„กœทธž˜ฐ„ ํ–ˆœฉฐ, –ด–ค ””žธ ฒฐ •„ ํ–ˆŠต‹ˆŒ? งŒ•ฝ ‹คํŒจํ–ˆ‹คฉด ‹‹ ด ํ–ˆ˜ ฒƒ ํ˜€ ํ•˜€ •Š•˜˜ ฒƒ ค‘ ฌด—‡ด ‹คํŒจ˜ š”ธด—ˆ‹คณ  „„„ ํ•˜‹ญ‹ˆŒ?

ดฒˆ ฒฝํ—˜„ ํ†ตํ•ด ฐฐšด ฒƒ€ ฌด—‡ž…‹ˆŒ? „กœ —†Šต‹ˆŒ? ทธŸฌฉด ‹ค‹œ ํ•œฒˆ ƒฐํ•ด ณด‹ญ‹œ˜ค. ‚จ˜ ฒฝํ—˜„ “ฃณ , ‚จ ํ† ก ํ•ด ณด‹ญ‹œ˜ค. ฐฐšด ฒƒ„ —†Š” — ช‡ ‹œ„„ ํˆฌžํ•˜Š” ฒƒ€ •„Œšด ž…‹ˆ‹ค.

ฒ˜Œ ฌธ œ ํ•ดฒฐํ•  •Œ, •„ฌด –ด ค›€ด‚˜ žฅ• „ —†—ˆ‚˜š”? €ธˆ ’คŒ•„ •Œ— ž‹ ด œ  • ค‘— "ฐœ„ ˜—ˆœฉด ํ•˜Š” €„"ด žˆ‚˜š”? งŒ•ฝ ด ฌธ œ ‹ค‹œ ฒ˜Œ€„ƒˆกœ ํ’€ธฐ ‹œž‘ํ•œ‹คฉด —ญ‹œ ˜‘ฐ™€ ฐฉ‹œกœ ํ”„กœทธž˜ฐ„ ํ•  ฒƒ ฐ™Šต‹ˆŒ(see also EightQueenProblemSecondTry)? กฐธˆ ” ””ํ•˜ณ  Œˆฐ•ํ•˜ฒŒ ํ‘ธŠ” ฐฉฒ•„ žˆ„Œš”? –ด–ปฒŒ ฒ˜Œ—  ‘ํ–ˆ”ฉด ” "—ํ•œ" ฝ”“œ€ ‚˜˜ฌ ˆ˜ žˆ—ˆ„Œš”? „Šทํ•œ ฌธ œ— งฉดํ–ˆ„ •Œ ฐ˜ œกœ  šฉํ•  ˆ˜ žˆŠ” –ด–ค "ถ”ƒ  ํŒจŸฌ‹คž„" ฐ™€ ฒƒ„ ฐœฒฌํ•  ˆ˜ žˆ„Œš”? ทธ ฝ”“œ ‚œƒ ฒ˜Œ ณดŠ” ‚ฌžŒด žˆ‹คณ  ํ–ˆ„ •Œ ช‡ „งŒ— ทธ ฝ”“œ ดํ•ด‹œํ‚ฌ ˆ˜ žˆฒ Šต‹ˆŒ? งŒ•ฝ ทธ ‚ฌžŒ ํ˜ž ทธ ฝ”“œ ณธ‹คฉด ‰ฝฒŒ ดํ•ดํ•  ˆ˜ žˆ„Œš”? „ด —†ด„š”? ํ˜‹œ ฝ”“œ ‚ด— ค‘ณต˜Š”  •ณดŠ” —†Šต‹ˆŒ? ณธธ˜ ˜„€ ชจ‘ „ช…ํžˆ “œŸฌ‚˜ณ  žˆŠต‹ˆŒ? --€ฐฝ€

ฌธ œ ‚˜„Œ€กœ ํ•ดฒฐํ•œ ‚ฌžŒ“ค€ StepwiseRefinement ณต€ํ•ด ณด„š”.

ด•Œณ ฆฌฆ˜ ˆ˜—… ‹œ„„ ํ†ตํ•ด ƒฐํ•ดณธ ฌธ œดธฐ—  €—†ด ํŠธž˜ํ‚(BackTracking) ธฐฒ•„ „ ํƒํ•ด„œ Šˆ„ฝ”“œ ข…ด— ž‘„ํ•ดณด•˜ณ  ทธ ฐ”ํƒ•œกœ ตฌํ˜„— “ค–ดฐ”Šต‹ˆ‹ค.(ทธƒฅ ํ˜ธธฐ‹ฌ—„œ งˆฌธ ํ•˜‚˜. •Œณ ฆฌฆ˜ ˆ˜—…—„œ ํŠธž˜ํ‚„ ฐฐ› ‚˜š”? ตœ—Š” Œ€€„ AIชฝœกœ „ง‘–ด ‚ด„œ €ฅด˜Š” ฒƒด ถ”„ž…‹ˆ‹คงŒ... ตžฌ€ ฌด—‡ด—ˆ‚˜š”? --€ฐฝ€ Foundations of Algorithms Using C++ Pseudocode, Second Edition ด—ˆŠต‹ˆ‹ค. ISBN:0763706205 --ด•€) ํŠธž˜ํ‚€ BruteForce‹ •Œณ ฆฌฆ˜œกœ ํ™•žฅํ•˜ธฐ— šฉดํ•ด„œ ˆ˜ •—” ทธฆฌ งŽ€ ‹œ„ด ฆฌ€ •Š•˜Šต‹ˆ‹ค. งŒ EightQueenProblem— Œ€ํ•œ ‚ฌ „ €‹ด —†—ˆ‹คฉด ‘ฒˆงธ  œ—„œ ฌดฒ™ ‹ํ™ฉํ–ˆ„ฒƒ ฐ™Šต‹ˆ‹ค. ดฒˆ ธฐํšŒ— ฝ”“œ˜  ‘„„ ค‘š”ํ•จ„ ƒˆ‚ ํ™•ธํ–ˆŠต‹ˆ‹ค. --ด•€

ดฌธ œŠ” ฒ˜Œ  ‘ํ•ดณธ ฌธ œ  € ข…ด— ฒดŠคํŒ„ ทธฆฌณ  ง ‘ ฌธ œ ํ’€ คณ  ํ•ดณด•˜Šต‹ˆ‹ค. ทธฆฌณ  ƒฐํ•ด‚ธฒƒ„ ข…ด—  ณ (1—ฌ™•€ €กœ,„กœ,Œ€ฐ„  ฐ™€„— žˆŒ •ˆœ‹ค. 2, € ฒซฒˆงธ —ฌ™•„ †“ณ  ‘ฒˆงธ —ฌ™•ด †“ œ„˜ ฒฐ •ํ•œ‹ค. 3 €‚ฌํ•˜Š” ฐฉฒ•€ €กœ->„กœ->Œ€ฐ„  ˆœœกœ ํ•œ‹ค. 4 —ฌ™•8ฐœ€ ‹ค†“ดฉด
†“ธ žฆฌ •Œ คณ  ‚œ‹ค.) ด  € ฒƒ„ ํ† Œ€กœ ฝ””ฉ„ ํ•˜˜€ณ  ฒ˜Œ —ฌ™•€ 0,0— †“•˜Šต‹ˆ‹ค. ƒฐํ•œŒ€กœ ฝ””ฉ„ ํ–ˆ‹คณ  ƒฐํ•˜ณ  ‹คํ–‰„ ํ•˜ž ฌดํ•œฃจํ”„ Œ•˜Šต‹ˆ‹ค.  „ ฒ˜Œ —ฌ™•ด –ดŠ œ„˜— †“ด˜„ฐ ธฐ— งžŠ” ‹ตด žˆŠ”ณ  ƒฐํ–ˆŠ”ฐ ทธฒƒด ž˜ชป˜—ˆ‹คณ  ƒฐํ•ฉ‹ˆ‹ค. ฒ˜Œ€„ด ฌธ œ˜ ‹ต„ •Œณ žˆ—ˆ‹คฉด ํ”„กœทธžจ„ งœŠ”ฐ €” „ฒฐํ•œ ฝ”“œ งคˆ˜žˆ—ˆ„ํ…ฐ ž€ƒฐด “ค–ด„œ ฝ””ฉ„ ฉˆถ”ณ  ข…ด ‚ด ฌธ œ ํ’€ธฐ ‹œž‘ํ–ˆŠต‹ˆ‹ค. ํ•˜€งŒ ‹ต€ ‚˜˜ค€•Š•˜ณ   œ€ํ‘ธŠ”ฐฉ‹(—ฌ™•„  € •„ฌดœ„˜—‚˜ †“ณ  ทธœ„˜— งžฒŒ €กœ„กœŒ€ฐ„ — —†Š” ณณ— †“Š”‹ค)„ ทธƒฅ ฝ””ฉ„ ํ•˜˜€Šต‹ˆ‹ค. ฒ˜Œ —ฌ™•˜ œ„˜ 8*8— Œ•„€ฉด„œ †“ณ  €‚ฌ ํ•˜˜€Šต‹ˆ‹ค. ฌด‹ํ•˜ธดํ•˜€งŒ ‹ต€ ‚˜™”Šต‹ˆ‹ค. ‘ฒˆงธ  œŠ” ฒ˜Œ ฝ””ฉํ• •Œ€„ฐ ํŒ˜ ํฌธฐ™€ —ฌ™•˜ ˆซž defineํ•ด„œ 썻ธฐ 떄ฌธ— ˆซžงŒ ฐ”พธ–ด —ˆŠต‹ˆ‹ค. ํ•˜€งŒ ‹ตด งžŠ”€ ํ™•‹ ด „œ€ •ŠŠต‹ˆ‹ค. ทธดœ Š” ดฌธ œ˜ Œ€ํ•œ •Œณ ฆฌฆ˜„ ชจฅดธฐ •Œฌธดณ  ƒฐํ•ฉ‹ˆ‹ค. ทธฆฌณ  c++„Š”ฐ ฐฉํ•™™•ˆ ญ‰ žฐ”กœ ํ”Œฐํ•˜‹ค€ c++„ “ดดœ € „–ํˆด˜ ””„…„ ดšฉํ•˜ คŠ” ƒฐด—ˆŠ”ฐ ฌดŠจฌธ  € ””„…„ ํ• ˆ˜—†–ด„œ ฐธ ‚œฐํ–ˆŠต‹ˆ‹ค. ””„…ํ•˜ฉด ธˆฐฉ•Œˆ˜žˆŠ” ฌธ œ ˆˆœกœ ฐจฐจœฉด„œ ด•ํ–ˆŠต‹ˆ‹ค. --ตœด‘‹

‘ฒˆงธ ฌธ œ— ‹ตด žˆ—ˆตฐš”.. —ญ‹œ  œ‹ตด ํ‹€ฆฌตฐš” ‹คํŒจ˜ ›ธ€  œŒ€œ •Œณ ฆฌฆ˜ด —†‹คŠ” ฒƒดณ  ƒฐํ•ฉ‹ˆ‹ค BackTracking •Œณ ฆฌฆ˜„ ณดณ  ™”€งŒ ดฌธ œ— Œ€ํ•œ „ช…„ ณด™”Šต‹ˆ‹ค. ํ•˜€งŒ •Œณ ฆฌฆ˜— ฌด€ํ•ด„œ ทธŸฐ€ ž˜ ˆˆ— “ค–ด˜ค€ •ŠŠต‹ˆ‹ค. ทธž˜„ ฐคƒˆ ํ’€ฉด„œ(—‰šํ•œ ‹ตด‹ค„) ˜คž˜งŒ— žฌฐŒ—ˆŠต‹ˆ‹ค. ^^-ตœด‘‹
ธฐณธ œกœ ด ฌธ œŠ” •Œณ ฆฌฆ˜„ ŠคŠคกœ ณ •ˆ(invent)ํ•ด ‚ดŠ” ฒฝํ—˜ด ค‘š”ํ•ฉ‹ˆ‹ค. BackTracking •Œณ ฆฌฆ˜„  „ํ˜€ ชจฅดŠ” ‚ฌžŒ„ ด ฌธ œ ํ’€ ˆ˜ žˆŠต‹ˆ‹ค. •„‹ˆ, –ด–ปฒŒ  ‘„ ํ•ด• 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
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:23:11
Processing time 0.0344 sec