A Sudoku szabályai

Adott egy 9 * 9-es tábla. 9 sor, 9 oszlop. A tábla egy mezője 0-9-ig tartalmazhat számokat.
A 0 jelentse az üres (még kitöltetlen) mezőt.

Egy sorban, egy oszlopban és egy blokkban egy szám legfeljebb egyszer szerepelhet.
Egy rejtvénynek lehet egy, vagy több megoldása is aszerint, hogy hányféleképpen lehet kitölteni a szabályoknak megfelelően.

The One
„Avagy létezik-e az egyetlen 16-os”

Feltevések szerint egy sudoku táblában 17 kezdőelemnek kell szerepelni, hogy egy és csakis egy helyes kitöltése létezzen. A projekt célja, hogy ezen feltevést igazoljam vagy cáfoljam.

Kiindulás. („Miért nem vagy okos?”)

Nem rendelkezem túl nagy matematikai képzettséggel, ezért a problémát a programozás tudásom segítségével, nyers erő módszerével próbálom megoldani. Bár kétségkívül ez a legkevésbé hatékony módja a feltevés vizsgálatának, azonban bízom benne, hogy sikerrel járok.

A kezdő lépések. („Miért?”)

A problémával Iványi Antal tanár úr „Sudoku algoritmusok” elnevezésű óráján találkoztam. Ő vetette fel számunkra a lehetőségét, egy „3 indexes probléma” megfejtésének. Sajnos a kezdeti próbálkozások nem jártak sikerrel, ezért kifutottam az adott félévben rendelkezésre álló időből. Egy hónapig szinte minden nap foglalkoztam a megoldás keresésével, de végül mire véget ért a félév, még nem tartottam sehol. A nagy számításigényű módszerrel mindössze néhány százmillió lehetséges tizenhat kezdőelemet tartalmazó táblát sikerült előállítanom. Fontos az előállítás szó, ugyanis a táblák ekkor még csak a sudoku szabályainak feleltek meg, de nem volt ellenőrizve, hogy valójában hány megoldásuk létezik.

A csiga. „”(„Előbb gondolkodj, aztán cselekedj.”)

Mint egy rutintalan programozó gondolkodás nélkül nekiestem a feltevés belátását igazoló/cáfoló program megírásának. Kár volt elsietni a dolgot. Ismételten beigazolódott, hogy előbb tervezz, aztán végezz módszer sokkal célravezetőbb. Az első változatok rendkívül átgondolatlanok voltak.

Az első módszer

Bár tudtam, hogy nagy számítási kapacitást igénylő módszerről van szó, úgy gondoltam, hogy mit nekem kapacitás, megírok egy egyszerű minden lehetséges táblát legeneráló programot. Ennek a megvalósítása a legegyszerűbb:

- Végy egy kombinatorikai programcsomagot.
- Majd vizsgáld meg a keletkezett táblákat, hogy 16 nem nulla elem legyen benne, és megfelelnek-e a sudoku szabályainak.

A módszer a következő volt. Ismétléses variációs modul segítségével helyezzük el az 0..9-ig a számokat a 81 helyre az összes lehetséges módon. Amikor ennek nekikezdtem még nem számoltam utána, hogy ez valójában hány táblát is jelentene. Tegyük fel, hogy az üres mezőket a 0 jelöli.

Az összes lehetséges tábla 10^81 féle képpen áll elő. Ami egészen pontosan:

1.000.000.000.000.000.000.000.000.000.000.000.000.000.
000.000.000.000.000.000.000.000.000.000.000.000.000.000

Ez tartalmazná az összes lehetséges táblát:

000000000000000000000000000000000000000000000000000000000000000000000000000000000
…
…
999999999999999999999999999999999999999999999999999999999999999999999999999999999

Nyilvánvalóan ez egy járhatatlan út. Erről a megközelítésről hamar letettem. Amint láttam, hogy maguknak a tábláknak az előállítása is hihetetlenül sok időt vesz igénybe, tudtam, hogy ezzel a módszerrel nem nagyon jutnék el a siker kapujáig.

A módszer nyilvánvaló reménytelensége ellenére, azért írtam egy sor-, oszlop- és blokk ellenőrző, valamint egy olyan algoritmust, ami megmondta egy tábláról, hogy pontosan 16 nullától különböző elemet tartalmaz-e. Körülbelül 2 napig futott a program, ez alatt még odáig sem jutott el, hogy legenerálja az első 16 elemet tartalmazó táblát. Valahol az első 10 vagy 11 nullától különböző elemet tartalmazó táblánál tarthattam. A nem nullát tartalmazó mezők növekedésével természetesen az eltelt idő is exponenciálisan nőtt.

A második kísérlet. („Hogyan csináljunk az elképzelhetetlen sokból rengeteget.”)

Láttam, hogy az összes tábla legenerálása emberi időszámítással nem mérhető ideig tartana. A föld kora ~10^13 másodperc. Ha minden másodpercben trilliónyi táblát állítottam volna elő, akkor sem végzett volna vele még az 100.-ik ük unokám sem.
Persze minden más lenne egy Quantum számítógéppel, de olyat ugye nem kapni a közértben.

A módszer lényege következőn alapult. Állítsuk az összes lehetséges 16 elemet tartalmazó táblát, anélkül, hogy foglalkoznánk azok érvényességével.
Nem tudom már pontosan honnan jött az ötlet, de kitaláltam, hogy igen sokat javíthatnék a módszer hatékonyságán, ha nem kellene a sorok validálásával foglalkozni.
Ennek megvalósításához mindössze arra volt szükség, hogy előállítsam az összes lehetséges, a sudoku szabályainak megfelelő sort.

Erre szintén a kombinatorikai programcsomagot használtam fel. A módszer egyszerű volt. Ismétlés nélkül először elhelyeztem az 1, majd a 2, majd a 12, 13, …..., 123456789 számokat az összes lehetséges módon a kilenc helyre úgy, hogy egy szám ne szerepelhessen kétszer.
Így jutottam el a 000000000, 000000001, 000000010-tól a 987654321-ig.

Már rendelkezésemre állt az összes lehetséges érvényes sudoku szabályoknak megfelelő sor.
Az összes ilyen típusú sorok száma beleértve a csupa nullát tartalmazó sort is 17.573.114.
Így már jelentősen csökkenthettem a műveletek számát, hiszen pl. a 000000011 és hasonló nem érvényes sorokat már nem kellett előállítani.

A következő lépés: rakjuk a sorokat az összes lehetséges módon egymás „alá”.
Ehhez készítettem egy egymásba ágyazott kilenc mélységű ciklust.

cvi: i. ciklusváltozó. (Minden ciklusnak saját).
tömb: a fenti ~17 millió érvényes sort tartalmazó lista (indexelés 0-tól)
tábla: egy 81 hosszú vektor (nem 9*9-es mátrix). A sorokat és oszlopokat a vektor konkrét eleme alapján számítva.

táblába_beszúr(poz, sor): a poz mezőtől beszúrja a táblába a 9 hosszú ’sor’-t. A poz lehet 0, 9, 18, 27, 36, 45, 54, 63, 72. pl.: táblába_beszúr(3, <213094000>). A sudoku tábla „3. sorába” beszúrja a megadott elemeket.

vizsgál(): megvizsgálja az adott tábla megfelel-e a sudoku szabályainak (oszlop- és blokk ellenőrzés) valamint 16 nullától különböző elemet tartalmaz-e.

cv1 = 0;
ciklus1 amíg (cv1 < 17573114)
táblába_beszúr(0, tömb[cv1])
vizsgál(tábla);
cv2 = 0;
ciklus2 amíg (cv2 < 17573114)
táblába_beszúr(9, tömb[cv2])
vizsgál(tábla);
cv3 = 0;
ciklus3 amíg (cv3 < 17573114)
táblába_beszúr(18, tömb[cv3])
vizsgál(tábla);
cv4 = 0;
ciklus4 amíg (cv4 < 17573114)
táblába_beszúr(27, tömb[cv4])
vizsgál(tábla);
cv5 = 0;
ciklus5 amíg (cv5 < 17573114)
táblába_beszúr(36, tömb[cv5])
vizsgál(tábla);
cv6 = 0;
ciklus6 amíg (cv6 < 17573114)
táblába_beszúr(45, tömb[cv6])
vizsgál(tábla);
cv7 = 0;
ciklus7 amíg (cv7 < 17573114)
táblába_beszúr(54, tömb[cv7])
vizsgál(tábla);
cv8 = 0;
ciklus8 amíg (cv8 < 17573114)
táblába_beszúr(63, tömb[cv8])
vizsgál(tábla);
cv9 = 0;
ciklus9 amíg (cv9 < 17573114)
táblába_beszúr(72, tömb[cv9])
vizsgál(tábla);
cv9 = cv9 + 1
ciklus9 vége
cv8 = cv8 + 1
ciklus8 vége
cv7 = cv7 + 1
ciklus7 vége
cv6 = cv6 + 1
ciklus6 vége
cv5 = cv5 + 1
ciklus5 vége
cv4 = cv4 + 1
ciklus4 vége
cv3 = cv3 + 1
ciklus3 vége
cv2 = cv2 + 1
ciklus2 vége
cv1 = cv1 + 1
ciklus1 vége

Bár első látásra ez jobb módszer volt, mint legenerálni az összes lehetséges táblát, de hamar kiderül, hogy ez is túl sok lépéssel járna.

Egész pontosan:

= 159822736423088010091679208174190876262472358735015281194343163574

Bár lényegesen kevesebb (~10^65), mint a 10^81, de még mindig túl sok.
A fő problémát az okozta, hogy még mindig előállítja az algoritmus a kevesebb vagy éppen több mint 16 nullától különböző elemet tartalmazó táblákat is. Ennek kiküszöbölésére bevezettem a következőket.

Minden sorhoz eltároltam, hogy hány darab nullától különböző számot tartalmaz. Pl. (134007689 : 7). Ennek segítségével megvizsgáltam, hogy az adott sorig hány nullától különböző számot tartalmaznak az egyes sorok. Ennek megfelelően a kód a következőképp módosult:

htömb: a ’tömb’ soraihoz tartalmazza, hogy az adott sor hány nem nulla elemet tartalmaz.
ki: i. sorig hány nem nulla elem található.

cv1 = 0;
ciklus1 amíg (cv1 < 17573114)
k1 = htömb[cv1]
táblába_beszúr(0, tömb[cv1])
vizsgál(tábla);
cv2 = 0;
ciklus2 amíg (cv2 < 17573114)
k2 = k1 + htömb[cv2]
ha k2 > 16, akkor ciklus2-t megszakít
ha k2 = 16, akkor { táblába_beszúr(9, tömb[cv2]); vizsgál(tábla); }
cv3 = 0;
ciklus3 amíg (cv3 < 17573114)
k3 = k2 + htömb[cv3]
ha k3 > 16, akkor ciklus3-t megszakít
ha k3 = 16, akkor { táblába_beszúr(18, tömb[cv3]); vizsgál(tábla); }
cv4 = 0;
ciklus4 amíg (cv4 < 17573114)
k4 = k3 + htömb[cv4]
ha k4 > 16, akkor ciklus4-t megszakít
ha k4 = 16, akkor { táblába_beszúr(27, tömb[cv4]); vizsgál(tábla); }
cv5 = 0;
ciklus5 amíg (cv5 < 17573114)
k5 = k4 + htömb[cv5]
ha k5 > 16, akkor ciklus5-t megszakít
ha k5 = 16, akkor { táblába_beszúr(36, tömb[cv5]) vizsgál(tábla); }
cv6 = 0;
ciklus6 amíg (cv6 < 17573114)
k6 = k5 + htömb[cv6]
ha k6 > 16, akkor ciklus6-t megszakít
ha k6 = 16, akkor { táblába_beszúr(45, tömb[cv6]); vizsgál(tábla); }
cv7 = 0;
ciklus7 amíg (cv7 < 17573114)
k7 = k6 + htömb[cv7]
ha k7 > 16, akkor ciklus7-t megszakít
ha k7 = 16, akkor { táblába_beszúr(54, tömb[cv7]); vizsgál(tábla); }
cv8 = 0;
ciklus8 amíg (cv8 < 17573114)
k8 = k7 + htömb[cv8]
ha k8 > 16, akkor ciklus8-t megszakít
ha k8 = 16, akkor { táblába_beszúr(63, tömb[cv8]); vizsgál(tábla); }
cv9 = 0;
ciklus9 amíg (cv9 < 17573114)
k9 = k8 + htömb[cv9]
ha k9 > 16, akkor ciklus9-t megszakít
ha k9 = 16, akkor { táblába_beszúr(72, tömb[cv9]); vizsgál(tábla); }
cv9 = cv9 + 1
ciklus9 vége
…

Ez a módszer vizsgálta a 16-osságot, de nem úgy, mint az előző algoritmus, amely még végigment a táblán és megszámolta, hogy hány nem nulla eleme van benne. Így a vizsgál eljárás már csak az oszlopok és a blokkok vizsgálatát tartalmazza. Fontos megjegyezni, hogy a ’tömb’-ben „nagyság” szerint követik egymást a sorok, azaz:

000000000 (első sor)
000000001
000000010
…
987654231
987654312
987654321 (utolsó sor)

A következő ötlet az utolsó két sorra született meg.

Tegyük fel, hogy a tábla így néz ki:

k1 = 1
k2 = 1
k3 = 1
k4 = 1
k5 = 1
k6 = 1
k7 = 2
…
Most a 8. sornál járunk már. Az algoritmus ekkor berakja a 000000000 sort a legutolsó sorba. Így kaptunk egy összesen 2 nullától különböző elemet tartalmazó táblát. Bár ezt nem vizsgáljuk meg, de mégis létrehozzuk, pedig nem is vesszük hasznát. Az algoritmus ezt egészen addig csinálja, még el nem jut az utolsó előtti sorban az első legalább 5 nem nulla elemet tartalmazó sorig. Ezt beszúrja, majd beszúrja az utolsó sorba a 000000000, majd 000000001, stb. sorokat. De ez még mindig nem jó nekünk, hiszen ameddig el nem jutunk a 9 hosszú sorokig a ’tömb’-ben, addig csak másoljuk be a sorokat feleslegesen, hiszen nem teljesül a 16-os feltétel.
Éppen ezért ha az utolsó előtti sorban vagyunk, akkor ahhoz, hogy 16 elem legyen legalább a táblában 16-ból vonjuk ki az utolsó sorban található legnagyobb sorszámot a 9-et + amennyi a k6 értéke.
A fenti példára: Az utolsó előtti sorban összesen két nem nulla mező van. Mivel lentről felfele nőnek a sorok értékei, ezért a lenti sorba 9 hosszú elemet még biztos berakhatunk. Így 16 – 9 – 2 = 5 hosszú sort kell legalább beszúrni az utolsó előtti sorba, hogy a 16-os feltétel teljesüljön.
Ezért amikor a sorokat beolvasom, eltárolom egy 10 elem tömbben, a tömb megfelelő indexén tárolom, hogy a nem nulla karakterek a ’tömb’-ben, hol kezdődnek.

Lásd:

kezdőindexek[0] = 0
(csak egy teljesen nulla sor van).

kezdőindexek[1] = 1
(a pontosan egy nem nulla számot tartalmazó sorok itt kezdődnek a ’tömb’-ben).

kezdőindexek[2] = 82
(a pontosan két nem nulla számot tartalmazó sorok itt kezdődnek a ’tömb’-ben).

kezdőindexek[3] = 2674
(a pontosan három nem nulla számot tartalmazó sorok itt kezdődnek a ’tömb’-ben).

kezdőindexek[4] = 45010
(a pontosan négy nem nulla számot tartalmazó sorok itt kezdődnek a ’tömb’-ben).

kezdőindexek[5] = 426034
(a pontosan öt nem nulla számot tartalmazó sorok itt kezdődnek a ’tömb’-ben).

kezdőindexek[6] = 2331154
(a pontosan hat nem nulla számot tartalmazó sorok itt kezdődnek a ’tömb’-ben).

kezdőindexek[7] = 7411474
(a pontosan hét nem nulla számot tartalmazó sorok itt kezdődnek a ’tömb’-ben).

kezdőindexek[8] = 13943314
(a pontosan nyolc nem nulla számot tartalmazó sorok itt kezdődnek a ’tömb’-ben).

kezdőindexek[9] = 17209234
(a pontosan kilenc nem nulla számot tartalmazó sorok itt kezdődnek a ’tömb’-ben).

Ennek megfelelően a ciklus a következőképp:

...
ciklus8 amíg (cv8 < 17573114)
k8 = k7 + htömb[cv8]
ha k8 > 16, akkor ciklus8-t megszakít
ha k6 < 7, akkor cv8 = [k7 = 7 – k6]
ha k8 = 16, akkor { táblába_beszúr(63, tömb[cv8]); vizsgál(tábla); }
cv9 = 0;
ciklus9 amíg (cv9 < 17573114)
k9 = k8 + htömb[cv9]
ha k9 > 16, akkor ciklus9-t megszakít
ha k9 < 16, akkor cv9 = 16 – k8
ha k9 = 16, akkor { táblába_beszúr(72, tömb[cv9]); vizsgál(tábla); }
cv9 = cv9 + 1
ciklus9 vége
...

Ennek köszönhetően az algoritmus két lépésben előállította az első 16 hosszú sort.
Ezzel 7411474 * 17573114 = 130242677510036 lépést spórolva rögtön induláskor. Megbecsülni sem tudom, hogy hány lépést spóroltam ezzel, de nagyon sokat az egészen biztos.

Sajnos hamar rá kellett jönnöm, hogy még így is túl hosszú idő lenne az algoritmus lefutása.

A harmadik kísérlet. („Többet ésszel, mint erővel.”)

Egyértelművé vált, hogy ez az út sem járható, mert ez a módszer sem jobb futásidejű, mint 81 alatt a 16.
A legjelentősebb problémát még mindig az okozza, hogy előállítom a szimmetrikus táblákat is.
Most összefoglalva az algoritmus működését eltekintve az utolsó két sorra vonatkozó feltételtől:
Beírjuk az utolsó sorba az összes lehetséges 17 millió sort, majd az utolsó előtti sorba az első nem nulla sort és az utolsó sorba ismét az összes 17 millió lehetséges sort. Majd az utolsó előttibe a második nem nulla sort és az utolsóba az összes 17 millió sort. És így halad végig ameddig az első sorba be nem írta az összes lehetséges 17 millió sort.

Az utolsó lépés:

17573114
17573114
17573114
17573114
17573114
17573114
17573114
17573114
17573114

A negyedik kísérlet. („A kevesebb néha több.”)

Pont az előbbi ötleten felbuzdulva legeneráltam a sorokban található nem nulla karakterek alapján az összes lehetséges variációt aszerint, hogy a 16 nem nulla számot hogyan lehet elrendezni a sorokban.

Az eddigi algoritmus alapján ez a következőképp nézett ki.

000000079
000000088
000000097
000000169
…
961000000
970000000

708444 lehetséges módon lehet a sorokat úgy rendezni, hogy 16 hosszú legyen.

Uppsz. Az utolsó elemek megegyeznek az első rész bizonyos elemeivel, csak éppen a fordítottja. Ami a szimmetriát tekintve ekvivalens.

Vegyük a Sudoku táblán a következő szimmetriát.

Ha az algoritmus a narancs részre az összes lehetséges módon elhelyezi a sorokat, akkor az pont ugyanazt az eredményt fogja adni, mint ha a kék részre helyeztük volna el azokat.
De, akkor ez azt jelenti, hogy az eredeti lépésszámot -re csökkentettük. Ami 33594090947249085 lépés helyett 16797045473624542 lépést jelentene mindössze.
A 81 hosszú 10^81-enhez képest azért ez igen jelentős javulás.

Ennek megfelelően a teljes algoritmust átalakítottam. Generáltam a lehetséges 16-os sor variációkat (pl: 123261100) úgy, hogy ha a fordítottja még nem szerepel a listában, akkor berakom a listába, különben eldobom az adott elemet. Így végül a 708444 lehetséges verzióból 354452 lett.

Ehhez igazítva az algoritmus, most a következő történik. A fenti legenerált sortömbön végigmegyünk egyesével és ezek alapján olvassa be a ’tömb’-ből a megfelelő sorokat. Így már végképp nem kell foglalkozni azzal, hogy 16 nullától különböző elemet tartalmaz-e a tábla, hiszen a megfelelő sorba csak azokat a sorokat szúrjuk be, amelyek összege 16. Hogy érthetőbb legyen egy példa.
Legyen az egyik ilyen 16-os sor a következő: (A 354452 lépés egyike).
pl: 123261100

1: a tábla 1. sorába csak az egy nem nulla elemet tartalmazó sorokat szúrjuk be
2: a tábla 2. sorába csak a kettő nem nulla elemet tartalmazó sorokat szúrjuk be
3: a tábla 3. sorába csak a három nem nulla elemet tartalmazó sorokat szúrjuk be
2: a tábla 4. sorába csak a kettő nem nulla elemet tartalmazó sorokat szúrjuk be
6: a tábla 5. sorába csak a hat nem nulla elemet tartalmazó sorokat szúrjuk be
1: a tábla 6. sorába csak az egy nem nulla elemet tartalmazó sorokat szúrjuk be
1: a tábla 7. sorába csak az egy nem nulla elemet tartalmazó sorokat szúrjuk be
0: a tábla 8. sorába csak a csupa nulla sort szúrjuk be
0: a tábla 9. sorába csak a csupa nulla sort szúrjuk be

Az oszlop és a blokk vizsgálat

Az első változat még úgy működött, hogy végigment az összes oszlop minden mezőjén. A blokkvizsgálatnál szintén. A fenti verzióban a sorok beszúrás egyesével történik. Amikor beolvasom a 16-os tömbből az egyik elemet például a fenti elemet, akkor eltárolom, hogy hol az első nem nulla elem és hol az utolsó nem nulla elem. A fenti példával. 123261100. Első nem nulla az első, az utolsó nem nulla a hetedik sorban van.
Megnézzük hol az első és utolsó nem csupa nullát tartalmazó sor. Így amikor az oszlopokat vizsgáljuk, akkor elég csak az első nem nulla sortól az utolsó nem nulla sorig vizsgálni az mezőket.
A blokkok érvényességének vizsgálatánál az használom ki, hogy tudom melyik sorba szúrtam be egy sort, így elég csak az adott sort tartalmazó 3 blokk vizsgálatát elvégezni.

Miközben ezt a dokumentációt írtam rájöttem egy apróságra. A csupa nulla sort többször is beszúrom, pedig az nem változtat a táblán éppen ezért meg kell oldani, hogy a nulla sort ne is szúrja be. Hiszen a tábla létrehozásakor alapból minden sor 0-ákat tartalmaz. Amikor pedig a 16-os sorban lépünk a következő elemre újra kinullázzuk a táblát. Így a csupa nulla sort nem is szúrjuk be.

A probléma továbbra is az, hogy a táblák létrehozása és ellenőrzése (megfelel-e a Sudoku szabályainak) ~10.000.000 tábla/3 perc sebességgel történik, addig a táblák megoldásszámának vizsgálata ~100.000 tábla / 2 perc sebességgel történik. Ezzel a sebességgel pedig továbbra is reménytelen a projekt befejezése. A megoldások számának vizsgálatát Knuth DLX algoritmusával végzem.

Ötödik kísérlet. („Ki a kicsit nem becsüli.”)

Alapvetően a megoldások számát vizsgáló algoritmust kell javítani és nem a táblák létrehozását. Éppen ezért a következő kísérletet végeztem el. A Knut DLX 0, 1 vagy 2 megoldásig fut legfeljebb. Megfigyeltem, hogy a 0 megoldások száma nagyjából megegyezik a 2 megoldásúak számával. Ebből kifolyólag kipróbáltam, hogy egy visszalépéses Brute-Force algoritmus mennyi idő alatt döntené el egy nagy sorról (3 blokk egymás mellett), hogy egyáltalán lehetne-e helyes kitöltése.

A nagy sort azért hangsúlyoztam, mert elég sok olyan 16-os kombináció van, ahol csak az egyik nagy sorban szerepelnek értékek. Éppen ezért elég lenne megvizsgálni azt, hogy egy ebben létezik-e helyes kitöltés.

Például:

000000000
000000000
000000000
000000000
000000000
000000000
001234567
589617234

Jelen állapotában ez a létrehozás pillanatában megfelel a szabályoknak. Sorok alapból jók. Az oszlopokban sincs ütközés. Az egyes blokkokon belül is minden rendben van.
Mégis felesleges a kitölthetőséget vizsgálni.

Miért?

Az utolsó előtti sorban láthatjuk, hogy értéket már csak az első két helyre tudnánk beírni. Igen ám, de ide már csak a 8 és a 9 számokat írhatnánk, de az szerepel az utolsó sorban a blokk elején. Így nem fog megfelelni a sudoku szabályainak. Így viszont már felesleges "ráengedni" a megoldások számát kereső algoritmust.

Ha létezik kitöltése, akkor átadjuk vizsgálatra a DLX-nek, viszont ha nincs helyes kitöltése, akkor nem kell a rengeteg időt feláldozni a DLX vizsgálatra. A Brute-Force egy nagy sor vizsgálatát exponenciálisan rövidebb idő alatt végzi el. Épp ezért, amit elvesztünk időt a 2 megoldással is rendelkező tábláknál a Brute-Force algoritmus miatt, azt behozzuk a megoldással nem rendelkező táblák vizsgálatánál.

Friss: Sajnos első teszteredmények azt mutatják, hogy pár másodperccel lassabb volt az ellenőrzés 100.000 különböző táblára, mint ha csak a DLX-et szabadítottam volna rá.
Az első 100.000 táblánál 2.37 BF-el, anélkül 2.27.

Sokat javítana a helyzeten, ha valahogy sorokhoz hasonlóan az oszlopoknál is el tudnám dönteni konstans idő alatt, hogy helyes-e az adott sorkombináció oszlop szerint.

pl.

000000000
000000000
000000000
000000000
000000000
000000000
000000000
001234567
231456789

pl. ezt a táblát teljesen felesleges legenerálnom, mert a harmadik oszlopban a két egyes miatt már nem megfelelő. Itt pl. 13 lépéses oszlop ellenőrzési folyamatot megspórolnék.

A következő az "intelligens" ellenőrző algoritmusok bevezetése lesz.
Ehhez azonban elemzések szükségesek, hogy az egyes algoritmusokkal hány lépést lehetne spórolni a DLX-hez képest.

folyt köv. Akinek bármi ötlete van az ne legyen rest megosztani