Да полудиш
Слагалица Да полудиш се састоји од четири коцке чије су странице обојене неком од четири боје (најчешће црвена, плава, зелена и бела). Циљ игре је направити стуб од коцкица тако да свака страна (предња, задња, лева и десна) стуба садржи сваку од четири боје. Распоред боја на свакој засебној коцки је јединствен.
Проблем се решава помоћу теорије графова, граф са четири чвора означених са Б,З,Ц,В (плаво, зелено, црвено и бело) служи за представљање сваке од коцки; грана између два чвора постоји ако су две боје које представљају чворове на супротним странама коцке, чвор има петљу ако су боје које се налазе на супротним странама коцке исте. Методом "узалудних покушаја" овај проблем се решава веома споро, јер постоји 41,472 комбинације, од којих су само две решење слагалице. Верзија слагалице са четири (или више) коцке је НП-комплетна.[1][2]
Слагалицу је осмислио Франц Овен Армбрустер, познат као Франк Армбрустер, а објавили су је браћа Паркер 1967. Продато је преко 12 милиона копија слагалице. "Да полудиш" је слична бројним слагалицама, међу којима је и Катценјаммер,[3][4] патентирана[5] од стране Фредерика А. Шосова 1900 године, и "Танталове муке" (приближно 1940, то је најпопуларније име ове игре пре "Да полудиш"). Слагалице користе подскуп од 30 коцки осмишљених од стране Персија Александра МекМахона, али није познато да ли су креатори слагалица знали за МекМахонове коцке.
Решење проблема са четири коцке[уреди | уреди извор]
Имамо четири коцке обојене са четири различите боје (црвена, зелена, плава и бела), покушаћемо да генеришемо граф који јасно представља све позиције боја на свим коцкама. Резултујућ граф садржи четири чвора (по један за сваку боју) и означићемо гране бројевима од један до четири (по један број за сваку коцку). Ако грана спаја два чвора (нпр. црвени и зелени) и број гране је три, то онда значи су на трећој коцки боје црвена и зелена на различитим странама коцке.
Слика 1 приказује четири коцке и њихове боје.
Слика 2 приказује граф генерисан на основу четири коцке.
Да бисмо нашли решење проблема потребно је да утврдимо како су уређене боје на свакој од четири стране стуба, за сваку коцку. Да бисмо представили распоред боја на супротним странама стуба (за сваку коцку) потребан нам је усмерени подграф (два смера представљају две супротне стране).
Дакле, ако имамо два усмерена подграфа можемо да представимо све четири стране (које су битне), за сваку коцку.
- Први усмерени граф представља предње и задње стране.
- Други усмерени граф представља леве и десне стране.
Не можемо насумично изабрати било која два подграфа - дакле, који је критеријум за одабир?
Ове графове треба одабрати тако да:
- два пографа немају заједничких грана, јер ако постоји заједничка грана то значи да бар једна коцка има пар супротних страница тачно исте боје. Пример: коцка има црвену и плаву напред и позади као и лево и десно.
- подграф садржи само једну грану за сваку коцку, јер подграф мора да објасни све коцке и једна грана може у потпуности да представља пар супротних страна.
- пограф може садржати само чворове степена два, јер чвор степена два означава да боја може бити присутна на страницама две коцке. Лак начин да се разуме је да има осам страница које морају једнако бити подељене у четири боје. Дакле две по боји.
После разумевања ових услова ако покушамо да изведемо два подграфа можда ћемо завршити са једним од могућих распореда, као што је приказано на слици 3. Свака обојена грана представља коцку.
Из првог подграфа ћемо извести боје предње и задње стране одговарајуће коцке. На пример:
- црна стрелица из жутог ка плавом чвору говори нам да прва коцка напред има жуту боју а позади плаву.
- плава стрелица из зеленог ка жутом чвору говори нам да друга коцка напред има зелену боју а позади жуту.
- наранџаста стрелица из плавог ка црвеном чвору говори нам да трећа коцка напред има плаву боју а позади црвену.
- љубичаста стрелица из црвеног ка зеленом чвору говори нам да четврта коцка напред има црвену боју а позади зелену.
Из другог подграфа ћемо извести боје леве и десне стране одговарајуће коцке. На пример:
- црна стрелица из црвеног ка жутом чвору говори нам да прва коцка лево има црвену боју а десно зелену.
- плава стрелица из плавог ка црвеном чвору говори нам да друга коцка лево има плаву боју а десно црвену.
- наранџаста стрелица из жутог ка плавом чвору говори нам да трећа коцка лево има жуту боју а десно плаву.
- љубичаста стрелица из зеленог ка жутом чвору говори нам да четврта коцка лево има зелену боју а десно жуту.
Трећа слика показује стуб који је решење проблема.
Референце[уреди | уреди извор]
- ^ Garey, M. R.; Johnson, D. S. (1979), Computers and Intractibility: a guide to the theory of NP-completeness, W.H. Freeman, стр. 258 (problem GP15);
- ^ Robertson, E.; Munro, I. (1978), „NP-completeness, puzzles, and games”, Util. Math., 13: 99—116
- ^ Slocum; Botermans (1986), Puzzles Old & New, стр. 38
- ^ http://home.comcast.net/~stegmann/pattern.htm
- ^ U.S. Patent 646,463
