[PHP] Sudoku Solver

[Verwijderd]

Heb gezocht, helaas geen topics hierover.

Puur voor vermaak ben ik bezig geweest met het maken van een sudoku solver. Een belangrijk gegeven is dat ik niet de intentie heb snelle of efficiente code te schrijven, ik heb het dus aangepakt volgens de rapid style methode (alle mogelijke combinaties proberen tot de juiste is gevonden)

Wat is gelukt:

• Het checken van een array van waardes of deze voldoen aan de randvoorwaarden van de sudoku (horz. vert. block. integrity zeg maar)
• Een aantal for/foreach loops die alle waardes proberen in chronologische volgorde
• Het recursief aanroepen van de functie om de volgende waarde te proberen

De huidige status is, dat alles wel lijkt me werken... met als enige uitzondering dat als de juiste oplossing gevonden is, de recursieve functie niet afbreekt, eigenlijk wel logisch gezien de code, alleen heb even geen flauw idee wat ik er tegen kan doen.

iemand die hulp kan bieden??

Hieronder volgt de functie, deze gebruikt een associatieve array[x][y] = waarde, waarbij x het rijnummer is en y het kolomnummer, gerekend vanaf het blokje rechtsboven (0=1). In de functie wordt de functie verify($array) aangeroepen, deze returned true of false afhankelijk van de correctheid van de sudoku tot op dat punt. edit: $size is de afmeting van de sudoku, een 3 betekent een 3x3 sudoku, de code moet namelijk instaat zijn "alle" verschillende soorten sudokus op te lossen (ik weet dat het qua processorpower bijna onmogelijk is op deze wijze een 4x4 op te lossen maar toch)

PHP:

function checkSudoku() {
    global $original_array, $current_array, $counter, $size; // globale variabelen
    
    if(verify($current_array)) { // als de huidige sudoku valideerd
        foreach($current_array as $row => $column_array) { // voor elke rij
            foreach($column_array as $column => $value) { // voor elke kolom
                if($original_array[$row][$column] != null) { // als het originele vakje ingevuld was (in de opgave)
                    continue; // ga door naar volgende
                } else if($current_array[$row][$column] == null) { // als het huidige vakje leeg is
                    for($x=1; $x <= pow($size,2); $x++) { // voor alle mogelijke waardes (1-9 voor een 3x3)
                        $current_array[$row][$column] = $x; // zet een waarde in het huidige vakje
                        if(verify($current_array)) { // kijk of de sudoku valideerd
                            $counter++;
                            if(checkSudoku()) { // roep de functie recursief aan
                                echo "de oplossing is gevonden";
                            } else { // als er false terug komt
                                continue; // ga door met de volgende mogelijkheid
                            }
                        } else { // als de sudoku niet valideerd
                                if($x==9) { // als de counter tot 9 is gekomen, is er dus een mogelijkheid geprobeerd die niet tot een oplossing leidt en,
                                $current_array[$row][$column] = ""; // moet het huidige vakje weer blanco worden gemaakt
                                //$counter--;
                                return false; // en wordt er false terug gegeven
                                }
                            if($counter >0) {
                                print_r($current_array);
                                $current_array[$row][$column] = "";
                            }
                        }
                    }
                }
            }
        }
    } else {
        die("De begin sudoku is ongeldig!!");
    }   
}

[ Voor 4% gewijzigd door Verwijderd op 09-02-2007 14:47 ]

[Verwijderd]

hint: break

[Verwijderd]

@kikkei, maar waar te plaatsen??

Ik zat zelf te denken dat ik wellicht aan het begin van de functie een eindconditie kan maken, die checkt of en alle waardes zijn ingevuld en de sudoku correct is... maar kan ik met break alle voorgaande aanroepen van de functie afbreken dus:

functie aanroep 1 -> functie aanroep 2 -> functie aanroep 3 (break)

dan

terug naar functie 2, of totale stop?

[IntToStr]

Misschien kun je het beter iets anders aanpakken. Beginnen met alle mogelijke waarden aan een vakje hangen en die overal bij elke stap updaten. Volgens mij zou je zo bij elke stap minstens 1 cijfer ergens weg moeten kunnen strepen. Als dat niet mogelijk is, is de sudoku niet geldig.

Door telkens alle mogelijke regels te controleren vind je volgens mij (bijna?) altijd een vakje waar nog maar 1 getal in staat en heb je dus weer een cijfer. Misschien dat je niet altijd een cijfer vindt, maar dan heb je volgens mij wel altijd ten minste wat mogelijkheden weg kunnen strepen.

Verzin dit overigens ter plekke, dus ik voel me niet aansprakelijk voor fouten

[4VAlien]

In het kader van de leesbaarheid liever niet dieper dan drie secties aan if/else blokken coden. Je kan dit eventueel anders opschrijven of de diepere lagen in een aparte functie onderbrengen. Verder kan je vast wel controleren of alle vakjes vol zijn zodra je een nummer toevoegt, daarna kan je gewoon via return terugkeren uit de recursieve functie.

Dit betekent wel dat de structuur van je programma zo moet zijn dat je calls maakt als "return checkSudoku();" zodat alle aangeroepen instanties van checkSudoku ook inderdaad de waarde aan elkaar doorgeven.

[ Voor 23% gewijzigd door 4VAlien op 09-02-2007 14:55 ]

[Verwijderd]

@IntToStr, ik weet dat er efficientere methodes zijn om sudokus op te lossen, mijn methode hier is echter gewoon "brute force" een resultaat te bereiken. Het nadeel van jouw methode is namelijk, dat een lege sudoku niet op te lossen is, terwijl mijn implementatie leidt tot een van de mogelijke oplossingen.

@4VAlien, zou je de return checkSudoku() toe willen lichten, ik snap even niet wat hier uiteindelijk het resultaat van is!

[Megamind]

Nou je zet of onder echo "de oplossing is gevonden"; een break zodat ie hem afkapt of je doet
echo return checkSudoku();
En dan maak je van alle echo's in je functie een return, dan geeft hij de waarde terug.

[PolarBear]

Verwijderd schreef op vrijdag 09 februari 2007 @ 14:45:
rapid style methode (alle mogelijke combinaties proberen tot de juiste is gevonden)

Dat is gewoon brute force

Zullen we het gezellig houden?

[ Voor 8% gewijzigd door RobIII op 10-02-2007 16:20 ]

[Verwijderd]

IntToStr schreef op vrijdag 09 februari 2007 @ 14:52:
Beginnen met alle mogelijke waarden aan een vakje hangen en die overal bij elke stap updaten. Volgens mij zou je zo bij elke stap minstens 1 cijfer ergens weg moeten kunnen strepen. Als dat niet mogelijk is, is de sudoku niet geldig.

Door telkens alle mogelijke regels te controleren vind je volgens mij (bijna?) altijd een vakje waar nog maar 1 getal in staat en heb je dus weer een cijfer.

Bijna ja. Er zijn gevallen waar je niet in iedere stap een aantal mogelijkheden kunt schrappen. Neem bvb een geldige oplossing (dus 9 blokken van 3x3). Stel dat in het blok linksboven op de eerst rij 'x 1 2' staat en in het blok eronder staat ergens op een rij 'y 2 1' (x en y een willekeurig geldig cijfer). Als je nu die eerste rij vervangt door 'x 2 1' en in het blok eronder de genoemde rij vervangt door 'y 1 2' heb je nog steeds een geldige oplossing: voor een rij verandert er namelijk niets, voor een 3x3 blok ook niet en per kolom blijft alles ook geldig. Stel dat ik je nu een sudoku geef waar alle cijfers al zijn ingevuld behalve die 4 cijfers (dus twee keer de 1 en twee keer de 2): je kunt dan niet eenduidig zeggen wat de oplossing is, omdat er namelijk 2 zijn. Dus je moet voorzien zijn op meerdere geldige oplossingen als je 't goed wil doen en er dan maar eentje kiezen - of nog beter: ze allemaal genereren natuurlijk

[jvdmeer]

Persoonlijk zou ik niet voor een recursieve oplossing gaan, maar voor een iteratieve. Als ik het goed lees, heb je in jouw geval soms een nesting-niveau van meer dan 60. Terwijl dit juist een probleem is wat je zeer goed iteratief kan oplossen.
Brute-force:

code:

1) Begin met eerste vrije vakje
2) Is het vakje leeg?
3a) ja, vul daar een 1 in.
3b) nee, vehoog de waarde met 1
4) Controleer of rij, kolom en vlak nog geldig zijn.
5a) Zo ja, ga naar het volgende vrije vakje en terug naar stap 2.
5b) Zo nee, verhoog de waarde van het huidige vakje.
6) Controleer of de waarde > 9 is
6a) Zo ja, maak vakje leeg, ga naar het vorige vrije vakje en ga verder naar stap 2
6b) Ga naar stap 2

7) Ben je bij vakje 81 dan goede oplossing gevonden

Je blijft hierin dus in een enkelvoudige lus (stap 2 tot en met 6) en springt er automatisch uit bij de oplossing.

Dit is in veel gevallen te optimaliseren, en te versnellen, maar je gaf aan dat niet te willen.

Succes.

[Verwijderd]

@PolarBear, idd brute force, ook wel genaamd Rapid Style (http://en.wikipedia.org/wiki/Sudoku#Computer_solutions), precies waar ik op uit ben.

Hierna is het namelijk de bedoeling dat ik een "intelligentere" versie ga schrijven van deze code.

@jvdmeer, jouw omschrijving ziet er goed uit! Ik probeer alleen nog even te doorgronden wat hier de consequensies van zijn, maar het lijkt me een goede manier om eenvoudiger hetzelfde te doen! Ontzettend bedankt, ik ga dit even proberen. (ps. het enige wat nog ontbreekt is dat je in de gaten houdt of je geen vakje aan het veranderen bent die onderdeel is van de "opgave")

[ Voor 12% gewijzigd door Verwijderd op 10-02-2007 17:28 ]

[jvdmeer]

Verwijderd schreef op zaterdag 10 februari 2007 @ 17:27:
het enige wat nog ontbreekt is dat je in de gaten houdt of je geen vakje aan het veranderen bent die onderdeel is van de "opgave"

Dat is aan jou. Het staat wel in de omschrijving: "volgende vrije vakje" en "vorige vrije vakje".

In code loste ik dat op door negatieve getallen te gebruiken voor de vaste waarden en positieve voor CGV*.

offtopic:
* creatieve afkorting voor Computer Generated Values

[Zeror]

Mail/DM Soultaker eens. Hij heeft al eens een Sudoku solver gemaakt en kan misschien wel licht op de zaak werpen.

Linkje naar een post in de HK

[ Voor 39% gewijzigd door Zeror op 12-02-2007 12:44 ]

[TweakerNummer]

Je kan toch gewoon echo "de oplossing is gevonden"; vervangen door exit("de oplossing is gevonden"); ???? Of mis ik iets?

[ Voor 7% gewijzigd door TweakerNummer op 12-02-2007 12:49 ]

[Chesta]

TweakerNummer schreef op maandag 12 februari 2007 @ 12:48:
Je kan toch gewoon echo "de oplossing is gevonden"; vervangen door exit("de oplossing is gevonden"); ???? Of mis ik iets?

return

[.oisyn]

TweakerNummer schreef op maandag 12 februari 2007 @ 12:48:
Je kan toch gewoon echo "de oplossing is gevonden"; vervangen door exit("de oplossing is gevonden"); ???? Of mis ik iets?

Ja. Of wil je voorstellen dat de rest van het verloop van het programma ook op de plek waar nu die echo staat geimplementeerd moet worden?

[TweakerNummer]

.oisyn schreef op maandag 12 februari 2007 @ 12:58:
[...]

Ja. Of wil je voorstellen dat de rest van het verloop van het programma ook op de plek waar nu die echo staat geimplementeerd moet worden?

Ik wil voorstellen dat het nogal verwarrend is (voor iemand die de code niet leest) dat er staat "de oplossing is gevonden", want dit lijkt erop dat de oplossing van het probleem (= oplossen Sudoku puzzel) is gevonden.

[ Voor 3% gewijzigd door TweakerNummer op 12-02-2007 13:23 ]

[.oisyn]

Nee, je stelt voor om een exit() te gebruiken, en daar reageerde ik op.

[Verwijderd]

Zo... bedankt voor de hulp allemaal, ik heb hem eindelijk weten op te lossen. Ik heb ten eerste een check ingebouwd die het hele loopje beeindigd als een bevredigende oplossing is gevonden. Daarnaast heb ik iets veranderd in de afhandeling wanneer in een bepaald vakje geen geldig getal kan komen (oftewel, ergens terug moet een andere mogelijkheid geprobeerd worden).

Binnenkort ga ik een intelligentere versie maken, die tevens kijkt of er al velden vooraf kunnen worden ingevuld aan de hand bepaalde logica. Wanneer dan een punt bereikt wordt dat er op trial-and-error moet worden doorgegaan kan ik deze functie hergebruiken. Zal vast tegen die tijd nog wel wat nieuwe vraagjes droppen

[Voutloos]

Bij de intelligente versie weet je dat je de unieke oplossing gevonden hebt.
Als je bruteforce bezig bent, heb je die garantie niet en daarom zou ik dus doorgaan met zoeken zodat gemeld kan worden dat het een baggersudoku is wanneer er meer oplossingen zijn. Je wil niet een oplossing, je wil dé oplossing (een oplossing en weten dat er niet meerdere oplossingen zijn).

[Verwijderd]

Het magische nummer is '45'

[Vaan Banaan]

Verwijderd schreef op maandag 12 februari 2007 @ 16:37:
Het magische nummer is '45'

Inderdaad, als in 1+ 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9

[.oisyn]

Voutloos schreef op maandag 12 februari 2007 @ 16:31:
Bij de intelligente versie weet je dat je de unieke oplossing gevonden hebt.

Dat weet je net zo min als bij de brute force versie. Het enige verschil is dat een intelligentere versie sneller door de boom van mogelijkheden heen gaat door bepaalde paden gewoon niet te bewandelen. Maar het hoeft nog niet zo te zijn dat als je een oplossing gevonden hebt dat je ook meteen weet dat dat de enige is - daarvoor zul je door moeten zoeken

Verwijderd schreef op maandag 12 februari 2007 @ 16:37:
Het magische nummer is '45'

Wat heb je daar precies aan dan? Ik zie niet helemaal in hoe je dat kunt gebruiken in het algoritme. Ik denk dat het magische nummer '511' handiger is.

[ Voor 21% gewijzigd door .oisyn op 12-02-2007 17:25 ]

[Voutloos]

.oisyn schreef op maandag 12 februari 2007 @ 17:19:
[...]
Dat weet je net zo min als bij de brute force versie. Het enige verschil is dat een intelligentere versie sneller door de boom van mogelijkheden heen gaat door bepaalde paden gewoon niet te bewandelen. Maar het hoeft nog niet zo te zijn dat als je een oplossing gevonden hebt dat je ook meteen weet dat dat de enige is - daarvoor zul je door moeten zoeken

Het lijkt mij dat een intelligente versie alleen iets invult als het de enige mogelijkheid is? Pas als je gaat gokken, moet je ook de andere mogelijkheden proberen.

[.oisyn]

Nee, het is niet zo dat er tijdens het oplossen _altijd_ een vakje is dat maar 1 mogelijkheid over heeft. Soms moet je kiezen tussen meerdere mogelijkheden en vandaaruit verder werken. Soms loopt dat dood en zal je de andere mogelijkheden moeten verkennen. Maar als de eerste keuze tot een oplossing leidt weet je nog niet of andere keuzes dood zouden lopen - die kunnen ook best tot een oplossing leiden. Om te kijken of de oplossing uniek is zul je die andere mogelijkheden alsnog moeten bestuderen, net als bij de brute force aanpak.

[ Voor 16% gewijzigd door .oisyn op 12-02-2007 17:38 ]

[Voutloos]

Nou, dat 'soms moet je kiezen' is voor mij gelijk aan 'pas als je gaat gokken', dus ik heb al gezegd dat je dan door moet gaan.

[.oisyn]

Ok, maar dan ben je het er dus mee eens dat je eerdere opmerking niet klopt:

Bij de intelligente versie weet je dat je de unieke oplossing gevonden hebt.

?

Even voor de duidelijkheid, het is natuurlijk niet zo dat een intelligente versie nooit hoeft te "gokken" (meerdere mogelijkheden verkennen lijkt me een betere verwoording, 't is niet dat ie een willekeurige oplossing pakt en daar bij blijft) - anders kan zo'n algoritme niet alle sodoku's oplossen

[ Voor 49% gewijzigd door .oisyn op 12-02-2007 17:56 ]

[Verwijderd]

@.oisyn, dat lijkt me compleet afhankelijk van het type sudoku die je aan het oplossen bent en de bewering die je na afloop wilt kunnen doen.

Een goede sudoku heeft per definitie namelijk 1 oplossing, als er meerdere zijn kan je of genoegen nemen met "een van de oplossingen is...", hij voltooid namelijk toch de opgave, indien je echt wilt kunnen zeggen alle mogelijke oplossingen zijn: zal je inderdaad meer dan dat moeten doen.... stel ik echter wel als uitdaging, probeer eens alle mogelijke oplossingen te vinden van een lege sudoku

Dit zijn er namelijk bij benadering 6,7 E21

[.oisyn]

Verwijderd schreef op maandag 12 februari 2007 @ 18:01:
@.oisyn, dat lijkt me compleet afhankelijk van het type sudoku die je aan het oplossen bent en de bewering die je na afloop wilt kunnen doen.

I know, dat is het hele punt niet, de discussie ging over het feit of een zogenaamde intelligente oplossing ook meteen weet of dat de enige juiste is. Lees Voutloos in "[PHP] Sudoku Solver" en verder

[Voutloos]

Ik heb een paar jaar terug een sudoku solver geschreven welke alleen waardes invulde als ze de enige mogelijkheid voor een vakje waren en dat ding loste alle puzzels in het 3-sterren sudoku boekje dat ik had op. Ik vond het al niet meer boeiend toen en heb niet eens moeilijkere puzzels geprobeerd.

Met goede sudoko's kom je gewoon echt heel ver op basis van zekerheden. Er zat dus logica in als: in een blok kan getal X alleen in de 1e kolom, dus in de overige blokken is X niet meer mogelijk in de kolom. Maar dus niet constateren dat X maar in 2 of 3 vakjes kan en dan die 2 resp. 3 mogelijkheden 'verkennen'. Als dus had gebleken dat bij 4-sterren sudoko's gegokt (verkend) had moeten worden, had ik dat heus wel kunnen implementeren, maar dan zou ik op dat punt ook zeker een rood vlaggetje hijsen dat er doorgezocht moet worden. Dat was mijn punt: je kan heel ver komen op een deterministische manier. En ja, misschien moet je wel op een moment de regels laten varen en brute-forcen/gokken/verkennen, maar vanaf dat punt noem ik het niet intelligent meer.

Het was een leuke vingeroefening, als ik echt een solver zou moeten maken in beperkte tijd (als in: een opdracht met deadline), zou ik voor een bruteforce aanpak gaan, maar dus wel alle oplossingen zoeken (hopelijk 1); dat is minder werk/code.

[.oisyn]

Voutloos schreef op maandag 12 februari 2007 @ 21:04:
Ik heb een paar jaar terug een sudoku solver geschreven welke alleen waardes invulde als ze de enige mogelijkheid voor een vakje waren en dat ding loste alle puzzels in het 3-sterren sudoku boekje dat ik had op. Ik vond het al niet meer boeiend toen en heb niet eens moeilijkere puzzels geprobeerd.

Dat soort Sudoku's vind ik dan weer geen uitdaging om zelf (als in: met de hand) op te lossen . Ik vind het wel leuk als je op bepaalde momenten even wat verder vooruit moet denken (maar natuurlijk niet te veel en niet te vaak, de mens is nogal slecht in backtracken )

Overigens een beetje offtopic maar toch niet helemaal (maar dat waren we toch al ): een ander interessant probleem is het genereren van goede unieke sudokus. De solver is hier uiteraard bij nodig om te verifieren of een gegenereerde sudoku uniek is (en of ie uberhaupt wel kan ). Je zou kunnen beginnen met een random volledig ingevuld sudoku veld, en dan willekeurig vakjes leeg maken totdat de puzzel geen unieke oplossing meer heeft. Wat lastiger is om hier een goede moeilijkheidsgraad bij in te bouwen; meer blokjes weghalen hoeft de sudoku niet per se moeilijker te maken, dus dan moet je gaan kijken naar de logica die overblijft om de puzzel op te lossen.

In other news: http://www.sudoku.org.uk/blunder.htm

[flashin]

andere algoritmes worden hier nog besproken:
http://phpfreakz.nl/library.php?sid=21635

[PiepPiep]

Voor zover ik weet zijn er nog geen sudoku's gevonden waar de computer voor moet gokken.
Enige is wel dat er dan bepaalde tabellen worden aangemaakt die erg groot zijn en dus met de hand voor de mens niet echt te doen zijn, de oplossing die er dan gevonden wordt is meestal echter wel weer makkelijk voor de mens te begrijpen.
Voorbeeld is dat als er in een vakje nog een 3 en een 5 mogelijk zijn, als je de 3 zou invullen dan volgt daaruit dat er ergens een 4 komt, daaruit dat er ergens een 7 komt en dan ergens dus een 2 moet komen. Op diezelfde manier forceert de 5 ook een 2 op die plaats, maar dan via een ander pad.
Erg moeilijk om te vinden, maar ik vind dit zeker geen gokken.

[schoene]

Natuurlijk wel. Je hebt 2 mogelijkheden, en je probeert eerst de eerste. Lukt de eerste niet, dan is het de tweede. Je doet dus een gok met 1 van de nog beschikbare mogelijkheden.

Edit: sorry, had verkeerd gelezen: jij bedoelt iets anders. Wat jij bedoelt is ongeacht wat je in een bepaald vakje invult, je zowiezo dezelfde waarde krijgt in een ander vakje. Dit zou ik inderdaad ook niet als gokken aanzien.

[ Voor 39% gewijzigd door schoene op 13-02-2007 14:32 ]