Szia!

 

Öröm látni, hogy még van valaki aki rajtam kívül is foglalkozik a témával. :)

A linken a megoldások nem valódiak, több egyforma elemet is tartalmaznak.

 

Szvsz. a 6x6-os táblán a 115 milliárd kombinációt a mostani algoritmusom kb. 1 óra alatt bejárná.

Legalábbis 4 éve 2 óra kellett hozzá és azóta még egy kicsit tudtam csiszolni rajta.

A sebességre lentebb lesz még célzás...

 

Jelenleg 1-1 bittel reprezentálom az adatokat és a back-track algoritmust csak a visszakonvertálásra használom.

A lényeg, hogy a bitmátrixból próbálom kiszűrni az adott helyekre nem lerakható kombinációkat.

 

A teljes táblát 3x3-as, 3x2-es és 2x3-as csoportokra osztottam fel, így kaptam egy 14x14-es, 14x15-ös és egy 15x14-es táblákat.

Az általad említett 895-ös hozzászólásban látszó képnek megfelelően így nézett ki 2015.02.27-én a 3x3-as tábla:

 

 

Ez a 895-ös hozzászólásban látható 1x1-es "kombinációkból" generált állapothoz képest a jelenlegi állapot kb. 15%-kal kevesebb bejegyzést tartalmaz ( ennyi bit lett már nullázva a mátrixban ). Érdekes módon, mikor visszaskálázom az adatokat 1x1-esre, tehát a "895"-ös elrendezésre, akkor még mindig ugyanott vagyok. :) Szeretnék legalább egy puzzle-t kiiktatni valahonnan a triviális eseteken kívül. Azt nem hiszem, hogy valaha is eljutnék a tábla bármely részén ( legvalószínűbb, hogy a bal alsó negyedben a két clue puzzle közti átlón ) egy "összeomlásig". Legalábbis a 3x3-as elemekkel ( kb. 100 milliárd bejegyzés / cella ) biztosan nem lehetséges, de tesztek alapján a 4x4-es sem lenne elég. Talán az 5x5-ös elrendezés (12x12-es tábla). Megjegyzem, hogy a 3x3-as esetén kb. 1 óra a számítási igény a legtöbb cellánál ( mindig, mind a 100 milliárd bejegyzést szépen sorban elő kell állítani, hogy az 1 bit alapján el tudjam dönteni, kell-e még foglalkozni vele vagy sem ). Jelenleg 34,5GB RAM-ot foglal a program és egy 4TB-os merevlemezt. 4x4-es tábla esetén a RAM igényt ezen a szinten lehetne tartani, viszont minden cellához kellene abból a merevlemezből úgy 2-2000 darab ami azt is jelenti, hogy egy cella feldolgozási ideje kb. 390 nap lenne.

 

A 3x2-es és 2x3-as táblákról csak annyit említenék, hogy ezeket a jóval kisebb méret miatt már majdnem direktbe (átlagosan kb. 15ns alatt) tudom ide-oda konvertálgatni, ami egy érdekes lehetőséget nyitott 5x4-es illetve 4x5-ös méretű szűrőablakok alkalmazásához. Az ablak lehetne nagyobb is, de így kb. 0,2-1,5 óra / cella a szűrőrutin sebessége ami még emberinek tekinthető. Mivel 2x210/420 cellám van, így kb. egy hét alatt fut egy kört a szűrő a mátrixon. Sajna minden körben egyre kevesebb és kevesebb kombináció esik ki ( most, hogy már 15% kibukott, kb. 0,1% / kör a tempó és egyre rosszabb lesz... :( ).