Crucea Amiralul Makarov
Lumea este aranjat astfel încât lucrurile din ea poate trai mai mult decat persoanele care au nume diferite, la momente diferite și în diferite țări. Jucăria, pe care o puteți vedea în figură, cunoscută în țara noastră ca un „puzzle Admiral Makarov“. În alte țări, are alte nume, dintre care cele mai frecvente - „Crucea Diavolului“ și „nod al naibii“.
Această unitate este legată la 6 bari pătrați. Barele au caneluri, care fac posibile și trecere baruri din centrul nodului. Una dintre bare nu are caneluri, este pus în ultimul nod, iar la demontare se îndepărtează mai întâi.
Varietatea de noduri sângeroase
Înainte de începutul secolului, câteva sute de ani de existență jucării în China, Mongolia, India, și a fost inventat mai mult de o sută de variante ale puzzle-ului, care diferă în configurația crestăturilor în baruri. Dar cele mai populare sunt două opțiuni. Acesta este prezentat în prima imagine rezolvat destul de ușor, pur și simplu și să-l. Este această structură folosită în vechiul sicriu indian. Din al doilea model de bare puzzle format este numit „nod Diavolului“. După cum s-ar putea imagina, numele a primit pentru decizii dificile.
În Europa, în cazul în care, de la sfârșitul secolului trecut, „nodul Diavolului“, a câștigat popularitate, entuziaști au început să se gândească și de a face seturi de bare cu diferite configurații de decupaje. Unul dintre kit-ul cel mai de succes produce 159 puzzle-uri și este format din 20 bare de 18 specii. In timp ce toate nodurile sunt identice în aparență, ele sunt destul de diferit aranjate în interior.
Stăruitor toate în această căutare a fost un profesor olandez de matematica Van De Boer, care, cu propriile sale mâini a făcut o colecție de câteva sute de bare și tabele compilate care arată modul de a asambla 2906 opțiuni noduri.
Acesta a fost în anii '60, iar în 1978 matematicianul american Bill Cutler a scris un program pentru calculator, și forța brută a stabilit că există 119,979 opțiuni de puzzle-uri de 6 elemente, combinații de proeminențe și adâncituri diferite în baruri, precum și plasarea bare, cu condiția că nu golurile din interiorul nodului. Un număr surprinzător de mare pentru o astfel de jucărie mică! Prin urmare, pentru a rezolva problema și a avea nevoie de un calculator.
Pe măsură ce computerul rezolva puzzle-ului?
Desigur, nu ca o persoană, dar nu într-un mod magic. Computer rezolvă puzzle-uri (și alte obiecte) pe program, programatorii să scrie programe. Scrie, așa cum le convine, dar astfel încât să fie clar și calculatoare. Cum poate un calculator manipuleaza bare de lemn?
Noi pornim de la faptul că avem un set de bare 369, care diferă de la fiecare alte configurații ale protuberanțele (primul set de identificat Van De Boer). Computerul trebuie să introducă o descriere a acestor bare. Locașul minimă (sau protuberanța), în bar - un cub cu latura de grosime 0,5 bari. Să-l numim un singur cub. În general, barul oferă 24 dintre aceste zaruri. Calculatorul pentru fiecare bara Începe matrice „mici“ de 6h2h2 = 24 numere. O bară cu crestături secvență de 0 și 1 definit în matrice „mici“: 0 corespunde sculptat cub, 1 - întreg. Fiecare dintre matricele „mici“ are numărul propriu (1-369). Oricare dintre ele poate fi alocat unui alt număr de la 1 la 6, care corespunde poziției barei din interiorul puzzle-ului.
Ne întoarcem acum la puzzle. Imaginați-vă că se potrivește în interiorul unui cub 8h8h8 de măsurare. In acest cub calculator corespunde unei matrice „mare“, format din celule 8h8h8 = 512 numere. Pune niste bar in interiorul cubului - înseamnă să umple în celula matrice corespunzătoare „mare“ de un număr egal cu numărul de bar.
Comparând 6 matrice „mici“ și de bază, un calculator (E. Programul de ex.,), Deoarece adaugă împreună cele 6 baruri. Conform rezultatelor adăugarea de numere determină cât de mult și ce fel de „gol“, „umplut“ și „celule supraaglomerate“, formate în matrice principală. celula „Blank“ corespund spațiul gol din interiorul puzzle-ului, „umplut“ - care corespunde proeminențelor în baruri, și „aglomerat“ - o încercare de a combina două singur cub, care, desigur, interzise. O astfel de comparație este făcută în mod repetat, nu numai cu diferite baruri, dar, de asemenea, având în vedere rândul lor, locurile pe care le ocupă într-o „cruce“, și așa mai departe. N.
Ca rezultat, selectați acele opțiuni, care nu sunt celule goale și supraaglomerate. Pentru a rezolva această problemă ar fi suficient de „mare“ celule 6h6h6 dimensiune matrice. Se pare, totuși, că există combinații de bare, umplând complet volumul intern al puzzle-ului, dar ele nu pot fi demontate. Prin urmare, programul trebuie să fie în măsură să verifice nodul cu privire la posibilitatea de demontare. În acest scop, Cutler și a luat o serie 8h8h8, deși dimensiunea acesteia nu poate fi suficient pentru a testa toate cazurile.
El este umplut cu detalii despre puzzle-uri variante. În cadrul programului matrice încearcă să „muta“ barele, T. E. Se deplasează în matrice „mare“ de dimensiunea barei 2h2h6 celule. Cilindree are loc la o celulă în fiecare din cele 6 direcția paralelă cu axele puzzle-ului. Rezultatele celor șase încercări de care nu se formează celule „aglomerate“ sunt stocate ca poziția inițială pentru următoarele sesari încercări. Arborele rezultat este construit din toate mișcările posibile atâta timp cât orice bloc nu este în totalitate în afara corpului principal sau după toate încercările de a rămâne celule „aglomerate“, care a fost cea care nu poate fi demontată.
Asta au fost obținute prin calculator 119 979 versiuni ale „Nodul Diavolului“, inclusiv nu 108, așa cum anticii, iar versiunea 6402 cu 1 întreg, fără tăieturi bar.
Rețineți că Cutler a renunțat la problema generală - atunci când un nod conține atât goluri interne. În acest caz, numărul de noduri de 6 bare este mult crescută și căutarea exhaustivă necesară pentru a găsi soluții fezabile, este nerealist, chiar și pentru calculator moderne. Dar, așa cum vom vedea acum, cele mai interesante și provocatoare puzzle-a găsit în cazul general - dezasambla puzzle, atunci puteți face o departe de banală.
Datorită prezenței de goluri, este posibil să se deplaseze secvențial câteva bare înainte de a va fi capabil să separe complet orice bar. Mutarea bara decuplează unele bare, permite deplasarea barei următoare, și în același timp se angajează celelalte bare.
Cu cât trebuie să faceți manipulări în timpul demontării, cu atât mai interesantă și mai dificilă versiune a puzzle-ului. Canelurile din bare sunt aranjate, astfel încât cunningly căutarea de soluții amintește că rătăcind labirintul întunecat în care tot timpul veni împotriva ceva pe perete, apoi se termină mort. Acest tip de nod este, fără îndoială, merită un nume nou; vom numi „supernode“. măsură complexitatea supernodes se numește numărul de mișcări de bare individuale, care trebuie să se facă înainte de primul membru este separat de puzzle.
Nu știm cine a venit cu prima supernode. Cele mai cunoscute (și cele mai dificile în decizie) două supernodes „spin Bill“ de 5, inventat de W. Cutler, și „complexitatea supernode Dubois 7. Până acum, se credea că gradul de 7 poate fi cu greu bate. Dar a reușit să îmbunătățească, „nod Dubois“ și de a crește dificultatea de a 9, și apoi, folosind unele dintre cele mai noi idei, pentru a primi supernodes cu complexitatea de 10, 11 și 12. Dar numărul 13 rămâne irezistibil. Poate, numărul 12 este marea complexitate a supernodes?