Minimum Sudoku

Minimum Sudoku

Az ember már csak olyan, hogy minden helyzetben, feladatban kíváncsi a szélsőséges esetekre. Gyakran keresi a válaszokat így: mi a leghosszabb, mi a legkisebb, melyik a leggyorsabb, stb. Nincs ez másképp a Sudokuval kapcsolatban sem. A feladványok a teljes táblából csak a számok töredékét tartalmazza. Így nyilvánvaló lehet a kérdés: vajon legalább hány elemet kell elhelyezni a feladványban, hogy megoldható legyen. Nagyon egyszerű a kérdés, de mint ahogy az gyakran előfordul, a válasz korántsem az. Mármint úgy tűnik, hogy van válasz, de a helyességét még soha senki nem bizonyította be. Számtalan (pontosabban általam megtippelni sem merem, hogy hány) elkészült feladvány alapján azt állíthatjuk, hogy nagy valószínűséggel a legkisebb elemszám a 17. Azaz még senkinek (és semminek) nem sikerült 16-os feladványt készíteni. A 17 elemű Sudoku feladványt szokták minimum Sudokunak nevezni.

Gordon Royle 2012. február 28-án tette közzé az általa összegyűjtött minimum Sudokukat. Letöltöttem a 49151 feladványt tartalmazó szöveges állományt, melynek eleje így néz ki:

A feladványokat sorfolytonosan tárolták szövegesen, minden sor egy-egy feladványt tartalmaz. Felfedezhető, hogy mint szöveg (de felfoghatjuk 81 jegyű számnak is) növekedő sorrendben található a listában. Ahhoz, hogy én kezelni tudjam a saját rendszeremben konvertálnom kellett az adatokat. Kíváncsi voltam, milyenek a feladványok nehézség szerint. Akadt néhány tucat, aminek az alaptábláját BTR-rel kellet meghatároznom, mert a metódusok nem voltak rá jók (ezek lehettek a törlés nélkül meg nem oldható feladványok). Végül sikerült mindegyiket minősíteni. Ezt az eredményt kaptam:

Nincs különösebb meglepetés. A feladványok 45%-a HS-el megoldható, de 8747 darab nehéz (100-asnál magasabb fokú) feladvány is van köztük. Ugyanakkor 1-es nehézségűt nem lehet találni. Mint ahogy az én félmillió 17-es feladványom között sem. Próbáltam csak BS-el 17-es feladványt készíteni, de eddig nem sikerült (még úgy sem, hogy 1-es szintű 18-asokból redukálnám). Így adott egy újabb, látszólag egyszerű kérdés: létezik-e 1-es szintű 17-es feladvány? (Én nem tudom rá a választ. Valaki igen?)

A következő vizsgálat ugyanakkor gondolkodóba ejtett. A Feladványok vizsgálata lapon került szóba a Bázisok keresése. Vajon a Royle gyűjteményben nincsenek-e bázisszerű képződmények? A legkisebb százalékos érték, amikor megjelent a helyre vonatkozó érték, a 42% volt. De nem is akármekkora! A D4-es cellában 21009 van, ami azt jelenti, hogy ennyi feladványban itt szám található (ahol nem üres a cella, ott nem éri el a foglalt cellák összes száma a 42%-ot).

Kíváncsi lettem, hogy mi lehet kisebb érték esetén. Íme a 15%-os szint (figyeljük meg az üres cellák elhelyezkedését):

Vajon mi van 1%-nál? Ezt láthatjuk:

Az látható, hogy a tartományok bal-felső cellájában sokkal több elemet találunk, mint a jobb-alsóban és annak környezetében. Az arány 8-9-szeres. Vajon minek köszönhető ez az egyenetlenség? A rendezettségnek nem, mert a vizsgálat ettől független. Valószínű azoknak a transzformációknak, amellyel csak alapvetően különböző feladványokat szeretett volna felsorolni, ez tehát egy szűrés eredménye lehet. Szerintem minden feladványt alávetett egy olyan transzformáció-sorozatnak, amellyel az egymáshoz hasonló (nevezzem most így őket) feladványokból kiválasztotta a listája alapján látható „legkisebbet”. (Vagy nem – csak tipp.) Ezt most még nem tudom, a transzformációkkal való ismerkedés még nekem ezután következik. Majd visszatérek még erre a kérdésre, ha tudok válaszolok rá.

Az érték szerinti egyezésnél sok a 9-es. Ez valószínű azért van így, mert ezeken a helyeken 1-től 9-ig találhatók a feltételt teljesítő számok (8-nál 8-ig). Ahol 1-es van, ott biztosan csak 1-es ilyen tulajdonságú. Van olyan cella 6 db is, ahol nincs ilyen szám. Az F6-os cellában 2480 a hely szerinti egyezés, de érték szerint nincs 1%-ot elérő. Ha a 2480-at az érték egyenletes eloszlásúnak gondoljuk (1-9 között), akkor 275-ös átlag jön ki, ami az 1%-nál kisebb (491-nél). Így elfogadható, hogy ezek a helyek üresek.

Arra is kíváncsi voltam, hogy vajon az általam előállított és a Royle-féle gyűjteményben van-e közös feladvány. Az eredmény több mint érdekes. Nem találtam közös elemeket egyetlen 17-es adatbázisommal sem. Lehet, hogy itt is a transzformációk állnak a háttérben. Az egymáshoz hasonló feladványokból én nem azokat találtam meg, amelyeket Royle valamilyen logika szerint elsőnek gondolt, és felvett a gyűjteményébe. Egy összevetést azért nézzünk meg (a többi adatbázissal kapcsolatban is hasonló a helyzet, néhány barát az egyezőség):

Az egy alapból származtatható feladványok összességét nevezhetjük családnak is. Kérdés, hogy egy rögzített alaptábla esetén milyen és mekkora család generálható? Mármint a szerint, hogy hány eleműek a feladványok. A 17-nél nagyobb elemszámú feladványok tekintetében szerintem bőségben állunk, azzal az esettel nem túl érdekes foglalkozni. De mi a helyzet a 17-es testvérekkel? Egy adott alaptábla esetén vajon hány generálható belőle. Ilyen vizsgálat eredményét találtam Gary McGuire, Bastian Tugemanny és Gilles Civario által 2013. szeptember 31-én közzétett, There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem via Hitting Set Enumeration című jegyzetében (Sudoku16clue2013.pdf állomány 30. oldal). Az alábbi alaptábla 29 darab 17-es táblát rejt, melyek mindegyike megtalálható Royle gyűjteményében: