Sudoku FlowHogyan oldják meg a számítógépek a sudokut
Frissítve: 2026-10-05
Visszalépéses keresés
A megoldó egy üres cellába beír egy szabályos számjegyet, és továbbhalad. Ha egyik számjegy sem vezet megoldáshoz, visszavon egy korábbi döntést, és mással próbálkozik. Ha először azt a cellát választja, amelybe a legkevesebb számjegy kerülhet, a keresés gyakran sokkal rövidebb lesz.
Források: Wikipedia: Sudoku solving algorithms, Peter Norvig: Solving Every Sudoku Puzzle
Pontos lefedés és Dancing Links
A sudoku pontos lefedési feladatként is megfogalmazható: úgy kell kiválasztani a beírásokat, hogy minden cella, valamint minden sorban, oszlopban és négyzetben minden számjegy pontosan egyszer legyen lefedve. Donald Knuth egy 2000 novemberéből származó tanulmányában leírta a Dancing Links módszert, amellyel hatékonyan futtatható a visszalépésen alapuló X algoritmusa; a sudoku pontos lefedési modelljére alkalmazva gyorsan megtalálja egy rejtvény összes megoldását.
Források: Wikipedia: Sudoku solving algorithms, Knuth, Dancing links (arXiv cs/0011047, 2000)
Véletlenszerű keresés
Egyes programok véletlenszerűen töltik ki a rácsot, majd a számok cserélgetésével csökkentik az ütközések számát, például szimulált hűtéssel vagy genetikus algoritmusokkal. Ezeket alternatív megközelítésként vizsgálták; hogy mennyire sikeresek, az a programtól és a rejtvénytől függ.
Források: Wikipedia: Sudoku solving algorithms
Emberként gondolkodó megoldók
A tippmotor feladata más: nemcsak a választ kell megtalálnia, hanem meg kell mutatnia a következő lépést is, amelyet egy ember követni tud. Alkalmazásunk motorja rögzített sorrendben próbálja ki az emberi technikákat, a legkönnyebbtől, például a rejtett egyestől, a legnehezebbig, például a láncokig és a majdnem zárt halmazokig, és az első olyat alkalmazza, amely egy számjegy beírásához vezet; a nehezebbek úgy működnek, hogy először jelölteket zárnak ki. A legnehezebb technika, amelyet egy rejtvényen használ, határozza meg a rejtvény szintjét az alkalmazásban.
Források: Mit vár tőled a Sudoku minden nehézségi szintje
