Történelem - nesharnirnye puzzle
Kereszt Admiral Makarov
A világ úgy van kialakítva, hogy a dolgokat akkor tovább élnek, mint az emberek, akik különböző nevek különböző időpontokban és különböző országokban. A játék, ami látható az ábrán, ismert hazánkban, mint egy „kirakós Admiral Makarov”. Más országokban, azt más nevek, amelyek közül a leggyakoribb - „ördög Cross” és „rohadt csomót”.
Ez az egység kapcsolódik a 6 négyzet rúd. A rudak barázdák, amelyek lehetővé teszik, keresztezésének bár a központban a csomópont. Az egyik a rudak nincsenek barázdák, akkor kerül az utolsó csomópont, és a szétszerelés során először eltávolítjuk.
A különböző véres csomók
Mielőtt az a század elején, több száz éves fennállása játékok Kínában, Mongóliában és Indiában találták több mint száz változatait puzzle, konfigurációjában különböznek a bevágások a bárokban. De a legnépszerűbb két lehetőség van. Ez jelenik meg az első kép megoldható nagyon könnyen, egyszerűen és azt. Ez a struktúra használják az ősi indiai koporsót. A második minta formált rudak puzzle az úgynevezett „Ördög csomót”. Amint lehet képzelni, a neve megkapta a nehéz döntéseket.
Európában, ahol, mert a múlt század végén, a „Ördög Knot” már egyre népszerűbb, rajongók kezdtek gondolkodni, és nem állítja bár különböző konfigurációk kivágások. Az egyik legsikeresebb kit állít 159 rejtvények és áll 20 bar 18 faj. Míg az összes csomópont külleme nem különböztethető meg, ezek egészen másképp belsejében elrendezett.
Kitartóan minden ebben a keresést egy holland matematika professzora Van De Boer, aki saját kezével készített egy gyűjtemény több száz bar és összeállított táblázatok hogyan kell összeállítani a 2906 lehetőségek csomópontokat.
Ez volt a 60-as, 1978-ban az amerikai matematikus Bill Cutler írt egy programot a számítógép, és a nyers erő határozza meg, hogy van 119.979 lehetőségek rejtvények 6 elem, különböző kombinációi kiemelkedések és bemélyedések a bárokban, valamint az elhelyezés rúd, azzal a megkötéssel, hogy nem üregek belsejében a csomópont. A meglepően nagy számú ilyen kis játék! Ezért, hogy megoldja a problémát, és szükség van egy számítógépre.
Mivel a számítógép oldja meg a puzzle?
Persze, nem egy személy, de nem valamilyen mágikus módon. Számítógépes megoldja rejtvényeket (és más tárgyak) a program, a programozók programokat írni. Írd meg, ahogy nekik megfelel, de úgy, hogy világos és számítógépek. Hogyan lehet egy számítógépes manipulálja a fa rudak?
Mi jár az a tény, hogy van egy sor 369 rudak, amelyek különböznek egymástól konfigurációi kiemelkedések (az első készlet azonosított Van De Boer). A számítógép kell adnia egy leírást a rudak. A minimális mélyedés (vagy a kiálló) a bárban - egy kocka éle 0,5 bar vastagságú. Nevezzük egy kocka. Általában a bár pedig 24 ilyen kocka. A számítógép minden mozogni kezd a „kis” tömb 6h2h2 = 24 számot. A bár bevágások meghatározott szekvenciát a 0 és 1 a „kis” tömb: 0 felel vájt kocka, 1 - egész. Mind a „kis” tömbök saját számát (1-369). Ezek közül bármelyik lehet rendelni egy másik számot 1-6, megfelelő helyzetben a rúd belsejében puzzle.
Most viszont, hogy a kirakós. Képzeljük el, hogy az belefér egy kocka mérési 8h8h8. Ebben a számítógépes kocka felel meg „nagy” tömb álló sejtek 8h8h8 = 512-számok. Tegyél egy kis sáv belsejében a kocka - ez azt jelenti, hogy töltse ki a megfelelő mobil „nagy” tömb számok számával megegyező a bárban.
Összehasonlítva 6 „kis” tömbök és egyszerű, a számítógép (azaz. E. Program), mivel egészíti ki együtt a 6 bar. Az eredmények szerint a számok hozzáadását ez határozza meg, hogy mennyi és milyen „üres”, „tele” és a „túlzsúfolt” képződő sejtek fő tömb. „Üres” cella felel meg az üres tér belsejében a puzzle, „tele” - megfelel a kiemelkedések a bárokban, és a „zsúfolt” - kísérlet összevesd két egyszemélyes kocka, ami természetesen tilos. Egy ilyen összehasonlítást végzünk többször, nem csak a különböző bárokban, hanem tekintettel azok fordulat, a helyeket foglalnak el a „kereszt”, és így tovább. N.
Ennek eredményeként választják ki azokat a lehetőségeket, amelyek nem üresek és túlzsúfolt sejteket. A probléma megoldására lenne elég „nagy” tömbméret 6h6h6 sejteket. Kiderült azonban, hogy vannak olyan kombinációk bárok, teljesen kitöltve a belső térfogata a puzzle, de nem szedhető szét. Ezért a program képesnek kell lennie arra, hogy ellenőrizze a csomópont lehetőségét szétszerelés. Ebből a célból, Cutler és felvette egy tömb 8h8h8, bár a méret nem lehet elegendő ahhoz, hogy teszteljék minden esetben.
Ő tele van részleteket a variáns rejtvényeket. Belül a tömb program megpróbálja „mozog” a bárokban, t. E. mozgatja a „nagy” tömb méretét a bárban 2h2h6 sejteket. Displacement történik egy sejtet mind a 6 párhuzamos irányban tengelyei a puzzle. Az eredmények a hat kísérlet, amely nem alakul „zsúfolt” sejtek vannak tárolva, mint a kiindulási helyzetbe a következő hatos kísérleteket. Az eredmény fa gyártani az összes lehetséges mozgások, amíg minden blokk nem teljesen ki a váza vagy miután minden kísérlet, hogy továbbra is „túlzsúfolt” sejtek, ez volt az egyik, hogy nem lehet szétszerelni.
Ami kaptuk számítógép 119 979 változat a „Ördög Knot”, beleértve a nem 108, mint a régiek, és a 6402 verzió 1 egész nélkül vágások bar.
Vegye figyelembe, hogy Cutler feladta az általános probléma - ha a csomópont tartalmaz mind a belső üregek. Ebben az esetben a csomópontok száma 6 bar jelentősen nőtt, és a teljes keresési megtalálásához szükséges megvalósítható megoldásokat, nem reális, még a modern számítógépes. De mint látni fogjuk őt, a legérdekesebb és kihívást jelentő rejtvényeket találta az általános esetben - szétszedése puzzle, akkor lehet, hogy egy távol triviális.
Mivel a pórusok jelenléte, lehetséges, hogy egymás után mozgatni néhány rúd előtt képes lesz teljes mértékben elválasztani minden bárban. Mozgó bár elválik néhány bár ez megengedi a mozgás a következő sáv, és ezzel egyidejűleg bevonja a másik rúd.
Minél többet kell tennie manipulációk szétszerelés közben, annál érdekesebb és nehezebb változata a puzzle. A nyílások a bárokban úgy vannak elrendezve, ravaszul, hogy a megoldások keresése emlékeztet vándor a sötét labirintusban, ahol minden alkalommal jön valami ellen a falra, majd zsákutcák. Ez a fajta csomópont kétségtelenül megérdemel egy új nevet; fogjuk nevezni „SuperNode”. Szupercsomópontok komplexitás intézkedés hívják a mozgások számát az egyes rudak amelyet meg kell tenni, mielőtt az első elem elkülönül a puzzle.
Nem tudom, ki találta ki az első szupercsomópont. A legismertebb (és legnehezebb a döntés) két szupercsomópontok „tüskés Bill” 5 által kitalált W. Cutler, és a „szupercsomópont Dubois komplexitása 7. Eddig azt hitték, hogy a mértéke 7 aligha lehet megverni. De sikerült javítani, „Dubois csomópont”, és növeli a nehézséget, hogy 9, majd segítségével néhány új ötletek, hogy szupercsomópontok összetettsége 10., 11. és 12. De ez a szám 13 marad ellenállhatatlan. Talán a 12-es szám a nagy komplexitása szupercsomópontok?