[prolog] vindt Sudoku oplossing niet

[aawe mwan]

Heel voorzichtig ben ik mijn eerste stapjes op Prolog gebied aan het maken. Ik gebruik swi-prolog onder Ubuntu (eerst uit de repository, later uit de ppa van SWI), met het voorbeeldprogramma in Prolog dat je overal op internet kunt vinden voor het oplossen van een Sudoku puzzel.

Dit is de Sudoku die ik wil oplossen, omgezet naar Prolog:

Prolog:

problem(3, [[6,_,_,5,_,4,3,_,_],
            [_,_,9,_,_,_,_,_,_],
            [1,_,_,_,_,_,_,_,5],
            [8,_,_,_,5,3,_,_,6],
            [_,6,5,_,_,7,_,_,_],
            [4,_,_,9,_,_,_,_,7],
            [_,1,_,_,4,_,_,9,_],
            [_,_,2,_,8,_,_,_,_],
            [_,_,_,3,_,5,2,_,4]]).

Als ik deze Sudoku door Prolog laat oplossen, dan kan het programma niet een oplossing vinden. Maar met wat handmatig beredeneerwerk kan je afleiden dat het vakje rechtsboven een 1 of een 2 zal moeten zijn; als je deze twee varianten uitprobeert dan zie je dat je bij het invullen van de waarde "1" wel meteen de oplossing van de puzzel krijgt en dat "2" niet tot een oplossing leidt.

Mijn vraag: waarom kan prolog deze puzzel niet oplossen?

De video waarin je de puzzel ziet en waarin je de afleiding ziet waarom het vakje rechtsboven een 1 of een 2 zal moeten zijn: YouTube: Another Sudoku Breakthrough: Man Vs Machine (vanaf 15:28)

On-line op het on-line Sudoku voorbeeld van SWI Prolog met een iets ander demo-programma werkt deze puzzel ook niet. Voor de volledigheid ook de details van mijn lokale installatie:

Prolog:

% Prolog versie: SWI-Prolog (threaded, 64 bits, version 8.2.4)

/* Aanroep:
problem(3, Rows), sudoku(Rows), maplist(portray_clause, Rows).
*/

sudoku(Rows) :-
        length(Rows, 9), maplist(same_length(Rows), Rows),
        append(Rows, Vs), Vs ins 1..9,
        maplist(all_distinct, Rows),
        transpose(Rows, Columns),
        maplist(all_distinct, Columns),
        Rows = [As,Bs,Cs,Ds,Es,Fs,Gs,Hs,Is],
        blocks(As, Bs, Cs),
        blocks(Ds, Es, Fs),
        blocks(Gs, Hs, Is).

blocks([], [], []).
blocks([N1,N2,N3|Ns1], [N4,N5,N6|Ns2], [N7,N8,N9|Ns3]) :-
        all_distinct([N1,N2,N3,N4,N5,N6,N7,N8,N9]),
        blocks(Ns1, Ns2, Ns3).

( https://sudokuspoiler.azurewebsites.net/ vindt precies 1 oplossing voor deze puzzel. )

[Woy]

Wat heb je zelf al geprobeerd en wat doet het programma niet wat je verwacht.

Je zegt dat rechtsboven een 1 of 2 moet zijn. Welke logica gebruik je daarvoor, en waar denk je dat die regels geïmplementeerd zijn in je programma?

Als je dat weet kun je gaan debuggen waarom het niet doet wat je verwacht

[aawe mwan]

Het programma lost Sudoku puzzels op. Het programma dat ik gebruik is de voorbeeldapplicatie van swi Prolog, wat voor mij een reden zou zijn om aan te nemen dat het correct is.

Dit programma werkt zo:
Regel 8 en 9 zetten een grid op dat bestaat uit een lijst van 9 lijsten, van elk 9 integers in het domein 1..9.
Regel 10 definieert dat van elke "rij" in dit grid alle waarden uniek moeten zijn.
Regels 11 en 12 samen definiëren dat van elke "kolom" in dit grid alle waarden uniek moeten zijn.
Regels 13 t/m 21 definiëren dat de waarden binnen elk van de 9 3×3 blokken uniek moeten zijn (loopt de lijsten van het grid recursief door, met het stopcriterium op regel 18).
Kortom: dit programma is een implementatie van de normale Sudoku regels.

Prolog werkt zo dat je als programmeur alleen het probleem definieert en dat de taal daarna zelfstandig op zoek gaat naar oplossingen voor het probleem; dat is niet iets wat je zelf nog moet bouwen, dit zit al in de taal. Daarom denk ik dat mijn vraag specifiek te maken heeft met de prolog implementatie van swi.

Het afleiden van de 1 of 2 rechtsboven is een Sudoku dingetje; hoe je dat precies doet zie je uitgelegd in de video uit de OP, maar dit heeft verder niets met programmeren te maken. In plaats daarvan (heb ik daadwerkelijk geprobeerd) kan je de puzzel domweg 9 keer laten oplossen voor de waarden 1 t/m 9 in het middelste vakje en dan zie je dat je met de waarde "1" de oplossing krijgt en dat swi-prolog bij alle andere waarden terecht zegt dat er geen oplossing mogelijk is. Dus het is niet zo dat dit programma helemaal niet werkt, sterker nog: voor alle andere Sudoku's die ik geprobeerd heb werkt het programma wel gewoon.

Wat ik begrepen heb is dat Prolog tijdens het zoeken naar een oplossing zou omschakelen tussen een methode van gestructureerd elimineren en als dat niet meer werkt simpele backtracking. Maar misschien gebeurt dat omschakelen in swi-prolog niet automatisch? Want ik kan me voorstellen dat deze ene specifieke puzzel met de meer voor de hand liggende eliminatietechnieken misschien niet op te lossen is.

[bwerg]

Even een sanity-check: is het ding wel oplosbaar? Gooi het eens in een duizend-in-een-dozijn sudoku-oplosser (of los 'm zelf op, natuurlijk). Dat je het eerste vakje hebt kunnen oplossen doet niet veel als dat later tot een tegenspraak leidt.

Ik heb verder zelf geen ervaring met prolog, maar als de sudoku inderdaad oplosbaar is is een tutorial in debugging misschien een goed idee (zoals gezegd, geen expert hier: het linkje is gewoon de eerste hit die ik vond). Kunnen debuggen is bij elke programmeertaal een noodzaak om het zelf te leren en zelf te begrijpen, ook al is het een aparte taal als prolog.

[aawe mwan]

Om een oplossing te vinden heb ik ook Gnu Prolog en Scryer Prolog geïnstalleerd.

Gnu Prolog heb ik gekozen omdat ik daarvoor gemakkelijk een andere Sudoku oplosser kon vinden en die vond gewoon de oplossing voor mijn puzzel (in 15 milliseconden).

Scryer Prolog heb ik gekozen omdat de maker van de CLP(FD) module van swi-prolog zelf overgestapt is van Swi naar Scryer. Ik dacht dat die module de oplossing had moeten vinden. De Scryer versie van de module (omgedoopt naar CLP(ℤ)) heeft 3 maanden geleden nog een update gehad.

En wat denk je: het programma uit de TS werkt wel gewoon onder Scryer Prolog!

Uiteindelijk blijkt het allemaal om een misverstand te gaan en op de laatste regel van het voorbeeld in de Swi manual stond al een subtiele hint: „In this concrete case, the constraint solver is strong enough to find the unique solution without any search.”. Het logisch elimineren wat Prolog standaard al voor je doet, is blijkbaar voor de meeste Sudoku puzzels al krachtig genoeg om ze op te lossen. Alleen voor moeilijke puzzels is in Prolog een „search” nodig en die moet je blijkbaar zelf activeren (en je moet de methodiek opgeven).

Prolog:

% Sudoku oplossen met alleen eliminatie:
problem(3, Rows), sudoku(Rows), maplist(portray_clause, Rows).

% Sudoku oplossen met eliminatie en search:
problem(3, Rows), sudoku(Rows), maplist(labeling([ff]), Rows), maplist(portray_clause, Rows).

[Voutloos]

aawe mwan schreef op zaterdag 25 september 2021 @ 20:35:
Het afleiden van de 1 of 2 rechtsboven is een Sudoku dingetje; hoe je dat precies doet zie je uitgelegd in de video uit de OP, maar dit heeft verder niets met programmeren te maken.

Natuurlijk kan het er wel mee te maken hebben. Je kan prima als algoritme kiezen dat je de ‘sudoko dingetjes’ implementeert. Dat is misschien zelfs de leukere route: Dan kan je ook aangeven hoe een mens het zonder gumwerk zou doen. En afhankelijk van de gebruikte regels kan je dan zelfs een waarde voor de moeilijkheidsgraad bedenken etc.

Maar bij sudoku is de andere route, namelijk bruteforce, veel sneller geimplementeerd én alsnog performant omdat voor een computer de bruteforce zoekruimte niets voorstelt.

(Sterker nog, het bruteforcen is zo goed te doen, dat het geen gegeven is dat je met zomaar een logica gebaseerde implementatie een kortere walltime haalt)

[ Voor 8% gewijzigd door Voutloos op 26-09-2021 12:21 ]

[NMe]

Je hebt de video van Cracking the Cryptic helemaal gezien, toch? Simon legt best goed uit dat een solver niet echt chocola kan maken van twee finned X-wings die samen combineren en daardoor dat ene vakje reduceren naar een 1 of een 2. Pas zodra dat vakje gereduceerd is naar een 1 of 2 is de sudoku verder door een solver op te lossen zonder complexe technieken waar alleen een computer aan denkt.

Tenzij je echt handmatig support gaat bouwen voor dit hele specifieke patroon gaat een solver hier nooit iets mee kunnen doen. En zelfs als je de support voor dat specifieke patroon inbouwt gaat het weer mis als een andere setter een finned X-wing combineert met niet een andere finned X-wing maar een finned swordfish, of elke andere combinatie van technieken die samen één cel vastpinnen.

[ Voor 4% gewijzigd door NMe op 26-09-2021 13:38 ]

[aawe mwan]

@Voutloos, @NMe:
De oplossing voor het probleem is gegeven in mijn reactie van 11:34. Dat het programma de Sudoku oplost is voldoende, ik ben niet op zoek naar een beschrijving van de stappen die nodig zijn om de Sudoku op te lossen.

Als je wilt dat Prolog een „search” doet naar de waarde van variabelen (wat je bruteforce zou kunnen noemen), dan moet je blijkbaar variabelen een labeling geven. Doe je dit niet, dan laat hij het bij eliminatie. Dat wist ik niet, ik dacht dat deze vervolgstap altijd zou gebeuren (automatisch).

Je zou labeling gewoon in het programma zelf kunnen zetten, maar in de Prolog wereld doen ze dat juist liever niet, omdat ze graag gemakkelijk willen kunnen zien hoe ver een probleem op te lossen is zonder search te gebruiken. Vandaar dat labeling ook in dit voorbeeld pas achteraf gebeurt.

[Voutloos]

Ik heb wel wat met Prolog gespeeld ooit.

aawe mwan schreef op zondag 26 september 2021 @ 14:27:
maar in de Prolog wereld doen ze dat juist liever niet, omdat ze graag gemakkelijk willen kunnen zien hoe ver een probleem op te lossen is zonder search te gebruiken. Vandaar dat labeling ook in dit voorbeeld pas achteraf gebeurt.

Dat klinkt als een waardevol inzicht. Je zoekstrategie staat los van wat je op elk specifiek punt doet. Dat herkennen in andere talen kan ook waardevol zijn. Als je OO bezig bent en je Cell class een property geeft om op de zoekstrategie te letten wordt het misschien tijd om een koffiepauze in te lassen.

Het was puur een selectieve quote om iets over bruteforce vs rulebased aanpak iets te zeggen. De sudoku-familie van puzzels is heel behapbaar met bruteforcen. En rulebased iets voor vierdubbele x-wings met een flikflak en flux capicitator implementeren is vast vrij pijnlijk.

[ Voor 49% gewijzigd door Voutloos op 26-09-2021 17:06 ]

[NMe]

Voutloos schreef op zondag 26 september 2021 @ 16:46:
En rulebased iets voor vierdubbele x-wings met een flikflak en flux capicitator implementeren is vast vrij pijnlijk.

Dat is inderdaad wat het is. Los zijn alle technieken als X-wings, Y-wings, swordfishes, jellyfishes, beide al dan niet finned, etc. prima in zo'n solver te bouwen, maar als je ze gecombineerd toe moet passen om één bepaalde cel te reduceren op een manier die de puzzel daarna triviaal maakt dan betekent dat dat je algoritme in staat moet zijn om alle mogelijke technieken met alle andere mogelijke technieken te combineren, en dat wordt snel nogal traag.

Bruteforcen daarentegen moet altijd mogelijk zijn, al dan niet op basis van bifurcation. En hoewel dat waarschijnlijk computerkracht scheelt bij puzzels als deze die geen nette oplossing hebben in een solver vind ik persoonlijk wel dat je daar weinig aan hebt, tenzij je enige doel is om aan te tonen dát er een oplossing is.