Sudokuban felcserélésekkel megkapható az összes tábla?

Kiindulunk 1 táblából, 4 féle lépés lehet: 2 sor/oszlop felcserélése 1 sor/oszlop 3-ason belül: a 1 3*3-ason belüli sorok/oszlopok cserélőnek, nem 2 3*3-as között cserélődnek: például a szélső és a mellett levő, nem a 2 szélső. A másik 2 lépés egy sor/oszlop 3-as felcserélése 1-ben: például a középső 3 oszlop marad, a bal szélső 3 és a jobb szélső 3 helyet cserél. Ilyen lépésekkel megkapható-e az összes helyesen kitöltött tábla? Ha nem, akkor ha számokat is cserélhetünk fel? Például az 1-esek helyére 9-est, a 9-esek helyére meg 1-est írunk. Nyilván ezen lépésekkel a helyesen kitöltöttség megmarad, és mindenféle sor/oszlop/szám sorrend elérhető: 2 elem felcserélésének sorozatával tetszőleges sorrendbe tehető egy sorozat: ha az elején nem az van ami kell, akkor felcseréljük azzal ami oda való, ezzel a kezdő eleme megvan, a megmaradt rész 1-gyel kisebb: arra vezettük vissza, olyan mint a teljes indukció.

Ez úgy jutott eszembe, hogy nyilván a feladványokat számítógéppel generálják. Egy feladvány megoldása 16 KB RAM-mal Intel 8008-on nagyjából 1 másodperc lehet. A legegyszerűbb generálási módszer kiindulni egy kitöltött táblából, azt permutálni véletlenszerűen, majd elhagyni belőle számokat, adott milyen nehéz feladványt akarunk készíteni, ráereszteni az olyan nehézségi szintű megoldóalgoritmust, és ha az elakad, hogy 1 helyre több szám is lehet, akkor az ilyen helyek közül véletlenszerűen választani, és azt visszatenni, folytatni a megoldóalgoritmussal. Ha már sikeres, akkor még végigmehetünk az összes megadott számon, megnézzük hogy azt elhagyva még megoldja-e, ha igen, elhagyjuk. Ez a végigmenés nem fontos.

Ha cél hogy tetszőleges táblát elő tudjon állítani, akkor 1 számot véletlenszerűen kiválasztunk, a többi 8 számhoz véletlenszerűen helyet választunk, ha nincs megoldása, újabb 8 számot generálunk. Ha van, több is van, mert legalább 17 adott kell legyen: adottak a helyek, ahol több szám is előfordulhat, ezek közül választunk, az oda tehető számok közül is választunk, megoldjuk: ha nincs megoldása, elhagyjuk és újabb számot generálunk, ha 1 megoldása van, kész, ha több, akkor még további helyeket és számokat választunk. Gyorsítható hogy egyszerre többet választunk, és csak utána nézzük meg hány megoldása van, ekkor ha nincs, az összes egyszerre választott hely-szám pár helyett új kell. Ekkor ritkábban kell megoldani: ha az is számít hogy több megoldás van-e, backtrackkel belassulhat. Ha könnyű feladvány kell, akkor mostmár adott az 1 megoldás, a 81 hely közül véletlenszerűen választunk, minden egyes választott után megnézhetjük hogy a könnyű megoldóalgoritmus megoldja-e, ha nem, újabbat kell megadni. Ezek után is lehet az elhagyhatók elhagyása: amiket elhagyva még mindig csak 1 megoldás van, és nem nehezebb: de ahány szám van, annyiszor meg kell oldani. Ez az általános módszer a kitalálásakor 1979-ben percekbe is telhetett, így gondolom a kész tábla permutálását használták, akár az elhagyhatók elhagyása nélkül: például az utolsó cellába számbeírás miatt lehet hogy az előző cellába számbeírás felesleges. Esetleg az igazival néhányat generálva, és azt permutálva.

Megoldási módszerek: minden cellára tudjuk mely számjegyek fordulhatnak ott elő: 9 bit/cella: ha ismert lett, a sorában, oszlopában, négyzetében a többi helyen nem lehet. Ami csak 1 helyen lehet, azt beírjuk oda. Ha ez is kevés, egy négyzet és vele átfedő sor/oszlop metszete 3 cella, a maradék rész 6+6 cella. Ami az egyik 6-osban nem lehet, az a 3-asban van, de akkor a másik 6-osban nem lehet: a 6 cellára unió, ezzel metszet a másik 6 cellára. Ha az unió 6-nál kevesebb elemű, nincs megoldás, ha pont 6 elemű, akkor mind a 6 szám ebben fordul elő, így a másik 3 cellában nem lehet: kivesszük. A 3 cellára is lehet unió, ha 3-nál kevesebb elemű, nincs megoldás, ha pont 3 elemű, akkor mindkét 6-os minden elemére: ezek nem fordulhatnak ott elő: kivesszük. Ezalapján 3 szint hogy melyekre volt szükség, +1 szint hogy ezek se elegek: maradt cella amiben több is lehet: például a legkisebb elemszámúak közül 1-et kiválasztunk, azok értéke közül 1-et választunk, lemásoljuk a táblát, és abban a kiválasztott lesz: ismert lesz, azzal folytatjuk. Ha nem sikerült, akkor ott az az 1 nem lehet, kivesszük az eredeti táblából, és megint próbáljuk megoldani, előbb az egyszerű módon. Ez a backtrack. Ha kell hogy több megoldás is van-e, akkor ha kellett a feltételes vizsgálat, és sikeres volt, akkor nézünk egy másik megoldást is: beírjuk hogy a kiválasztott érték ott nem lehet, és megpróbáljuk azt is megoldani, ekkor már nem számít hány megoldás van, csak hogy van-e. Köszi.