Википедија

Da poludiš

Slagalica Da poludiš se sastoji od četiri kocke čije su stranice obojene nekom od četiri boje (najčešće crvena, plava, zelena i bela). Cilj igre je napraviti stub od kockica tako da svaka strana (prednja, zadnja, leva i desna) stuba sadrži svaku od četiri boje. Raspored boja na svakoj zasebnoj kocki je jedinstven.

"Da poludiš" u rešenom redosledu. Boje (sleva nadesno) od pozadi su plava, crvena, zelena, bela. A na dnu (sleva nadesno) su bela, zelena, plava, crvena.

Problem se rešava pomoću teorije grafova, graf sa četiri čvora označenih sa B,Z,C,V (plavo, zeleno, crveno i belo) služi za predstavljanje svake od kocki; grana između dva čvora postoji ako su dve boje koje predstavljaju čvorove na suprotnim stranama kocke, čvor ima petlju ako su boje koje se nalaze na suprotnim stranama kocke iste. Metodom "uzaludnih pokušaja" ovaj problem se rešava veoma sporo, jer postoji 41,472 kombinacije, od kojih su samo dve rešenje slagalice. Verzija slagalice sa četiri (ili više) kocke je NP-kompletna.[1][2]

Slagalicu je osmislio Franc Oven Armbruster, poznat kao Frank Armbruster, a objavili su je braća Parker 1967. Prodato je preko 12 miliona kopija slagalice. "Da poludiš" je slična brojnim slagalicama, među kojima je i Katcenjammer,[3][4] patentirana[5] od strane Frederika A. Šosova 1900 godine, i "Tantalove muke" (približno 1940, to je najpopularnije ime ove igre pre "Da poludiš"). Slagalice koriste podskup od 30 kocki osmišljenih od strane Persija Aleksandra MekMahona, ali nije poznato da li su kreatori slagalica znali za MekMahonove kocke.

Rešenje problema sa četiri kocke

uredi

Imamo četiri kocke obojene sa četiri različite boje (crvena, zelena, plava i bela), pokušaćemo da generišemo graf koji jasno predstavlja sve pozicije boja na svim kockama. Rezultujuć graf sadrži četiri čvora (po jedan za svaku boju) i označićemo grane brojevima od jedan do četiri (po jedan broj za svaku kocku). Ako grana spaja dva čvora (npr. crveni i zeleni) i broj grane je tri, to onda znači su na trećoj kocki boje crvena i zelena na različitim stranama kocke.

Slika 1 prikazuje četiri kocke i njihove boje.

Slika 2 prikazuje graf generisan na osnovu četiri kocke.

 
Četiri kocke i njihove boje.

Da bismo našli rešenje problema potrebno je da utvrdimo kako su uređene boje na svakoj od četiri strane stuba, za svaku kocku. Da bismo predstavili raspored boja na suprotnim stranama stuba (za svaku kocku) potreban nam je usmereni podgraf (dva smera predstavljaju dve suprotne strane).

Dakle, ako imamo dva usmerena podgrafa možemo da predstavimo sve četiri strane (koje su bitne), za svaku kocku.

  • Prvi usmereni graf predstavlja prednje i zadnje strane.
  • Drugi usmereni graf predstavlja leve i desne strane.
 
Slika prikazuje graf generisan na osnovu četiri kocke.

Ne možemo nasumično izabrati bilo koja dva podgrafa - dakle, koji je kriterijum za odabir?

Ove grafove treba odabrati tako da:

  1. dva pografa nemaju zajedničkih grana, jer ako postoji zajednička grana to znači da bar jedna kocka ima par suprotnih stranica tačno iste boje. Primer: kocka ima crvenu i plavu napred i pozadi kao i levo i desno.
  2. podgraf sadrži samo jednu granu za svaku kocku, jer podgraf mora da objasni sve kocke i jedna grana može u potpunosti da predstavlja par suprotnih strana.
  3. pograf može sadržati samo čvorove stepena dva, jer čvor stepena dva označava da boja može biti prisutna na stranicama dve kocke. Lak način da se razume je da ima osam stranica koje moraju jednako biti podeljene u četiri boje. Dakle dve po boji.

Posle razumevanja ovih uslova ako pokušamo da izvedemo dva podgrafa možda ćemo završiti sa jednim od mogućih rasporeda, kao što je prikazano na slici 3. Svaka obojena grana predstavlja kocku.

 
Jedan od mogućih rasporeda podgrafova.

Iz prvog podgrafa ćemo izvesti boje prednje i zadnje strane odgovarajuće kocke. Na primer:

  1. crna strelica iz žutog ka plavom čvoru govori nam da prva kocka napred ima žutu boju a pozadi plavu.
  2. plava strelica iz zelenog ka žutom čvoru govori nam da druga kocka napred ima zelenu boju a pozadi žutu.
  3. narandžasta strelica iz plavog ka crvenom čvoru govori nam da treća kocka napred ima plavu boju a pozadi crvenu.
  4. ljubičasta strelica iz crvenog ka zelenom čvoru govori nam da četvrta kocka napred ima crvenu boju a pozadi zelenu.

Iz drugog podgrafa ćemo izvesti boje leve i desne strane odgovarajuće kocke. Na primer:

  1. crna strelica iz crvenog ka žutom čvoru govori nam da prva kocka levo ima crvenu boju a desno zelenu.
  2. plava strelica iz plavog ka crvenom čvoru govori nam da druga kocka levo ima plavu boju a desno crvenu.
  3. narandžasta strelica iz žutog ka plavom čvoru govori nam da treća kocka levo ima žutu boju a desno plavu.
  4. ljubičasta strelica iz zelenog ka žutom čvoru govori nam da četvrta kocka levo ima zelenu boju a desno žutu.

Treća slika pokazuje stub koji je rešenje problema.

Reference

uredi
  1. ^ Garey, M. R.; Johnson, D. S. (1979), Computers and Intractibility: a guide to the theory of NP-completeness, W.H. Freeman, str. 258  (problem GP15);
  2. ^ Robertson, E.; Munro, I. (1978), „NP-completeness, puzzles, and games”, Util. Math., 13: 99—116 
  3. ^ Slocum; Botermans (1986), Puzzles Old & New, str. 38 
  4. ^ http://home.comcast.net/~stegmann/pattern.htm
  5. ^ U.S. Patent 646,463
Preuzeto iz „https://sr.wikipedia.org/w/index.php?title=Да_полудиш&oldid=26862795”