Fejtörő

A múlt héten eljátszogattam egy sudoku programmal és szokatlan dologba futottam bele. Elakadtam.

Javítsatok ki, ha nincs igazam, de úgy tudom, hogy a játékban alapfeltétel, hogy mindig lennie kell legalább egy számnak, mely pusztán logikát használva egyértelműen kitalálható. Azaz nem fordulhat elő olyan patthelyzet, ahonnan csak try&error módszerrel lehet – ezernyi radírozás után – továbblépni.

Itt van a tábla.

Hangsúlyozom, nem a megoldásra vagyok kíváncsi, azt a Sudoku Solver egyből kidobta. Sőt, ha a programban beállítom, hogy figyelmeztessen, ha hibázok, akkor egy percen belül meg tudnám oldani.

Nem, az érdekelne, hogy szerintetek ezen a táblán van-e pusztán logikával kitalálható következő szám? És ha van, akkor mi az a logika?
Vagy az a normális, hogy az erősebb táblákat már csak próbálgatással lehet megoldani?

9 Comments

  1. Ez megadja a következő lépésnél alkalmazott algoritmust:
    http://www.sudokuwiki.org/sudoku.htm

    • Kösz. Már tanultam is egy új technikát. És még csak most kezdtem el nyomkodni a gombot.

    • Nincs mindig egyértelmű lépés. Ahogy Minesweeperben is van, amikor kockáztatni kell.

      • @S.E.
        “Nincs mindig egyértelmű lépés.”
        Valószínűleg tényleg van ilyen, mivel pl. a sudokuwikin is vannak trial and error típusú stratégiák. Nem tudom hogy van-e bizonyíték pro/kontra a témában, az is lehet hogy minden helyes (egyetlen megoldással rendelkező) sudoku-ra van logikus lépéssorozat, legfeljebb még nem fedezték fel az összes algoritmust hozzá.
        De én még nem láttam SOHA olyan “proper” sudoku feladványt, aminél találgatni kellett volna.
        Esetek többségében legfeljebb arról van szó hogy a játékos nem ismer elég algoritmust a megoldáshoz.
        A könnyebb (25-nél több) megadott számot tartalmazó helyes feladványok esetében szinte kizártnak gondolom hogy lenne olyan feladvány, amit ne lehetne step-by-step logikus lépésekkel megoldani.

  2. Régebben én is rengeteget fejtettem, s én is azt tapasztaltam, amit írtál: bizonyos szint felett (igaz, hogy csak 1-2 lépésig) csak a brute-force segített.

  3. Az eredeti felvetésre visszatérve: “a játékban alapfeltétel, hogy mindig lennie kell legalább egy számnak, mely pusztán logikát használva egyértelműen kitalálható”.
    Szerintem egyetlen egy Sudoku-s előfeltétel van, amit a szakmai oldalakon is gyakran látni:
    Helyes, vagy jó egy Sudoku feladvány, ha pontosan egy megoldása van, tehát a megadott számokkal kiindulva nem lehet többféle megoldásra jutni.
    Olyan feladvány simán van, aminél nem könnyű megtalálni a következő lépést (mert gyenge a player :)).
    Elvben ha elfogadunk egy backtrack jellegű megoldó algoritmust is, akkor nyilván mindig lesz következő “logikus” lépés, más kérdés hogy manuálisan nem biztos hogy kivitelezhető…

    • A backtrack az kifejezetten számítógépes algoritmus, nem igazán sorolnám a “logikus” megoldások közé. De ha igen, akkor már egy brute-force módszer is annak vehető…

      • Általában alkalmazható heurisztika, így egy helyes feladvány esetében találsz olyan kockát, ahol 2-3 lehetséges érték van. Ezek közül jól választva manuálisan is végrehajtható lehet egy brute force jellegű try&error algoritmus.
        Konkrétan 3-4 mélységi szinten megtett A vagy B (esetleg C) lépéssel valószínűleg ki lehet futtatni egy esetet. 1-2 új számjegy után általában már nem kell brute force, a sima eljárások működnek. Ez lesz max 10-20 eset. De lehet hogy csak 6-8.
        Azért ez nem ezernyi radírozás lenne.
        Ismétlem, hogy még nem láttam olyan feladványt, amit a fenti sudokuwiki solver ne nyomott volna le.

Leave a Reply to S.E. Cancel reply

Your email address will not be published. Required fields are marked *

Discover more from MiVanVelem

Subscribe now to keep reading and get access to the full archive.

Continue reading