Weblog januari 2005

Naar de vorige aflevering (november 2004)

Zweedse Getallenraadsels

Dit voorjaar heeft in Intermediair een aantal malen een Zweeds Getallenraadsel gestaan. Ik heb er vijf opgelost, er kunnen er meer geweest zijn, maar niet heel veel meer. Het gaat hierbij om kruis'woord'puzzels, waarbij de 'woorden' uit cijfers bestaan in plaats van uit letters. In een woord mag ieder cijfer (1-9) slechts één maal voorkomen. Van ieder woord is de som van de cijfers gegeven. Die omschrijvingen staan niet onder de puzzel, maar in de zwarte hokjes van de puzzel. Dit laatste zorgt voor de benaming Zweeds. Internationaal worden dergelijke puzzels aangeduid met het Japanse woord kakro. Het lijkt er overigens op dat Japan de bakermat is van allerlei logische en wiskundige puzzels. In Nederland zijn Zweedse Getalraadsels op het moment nog te vinden in de boekjes Logimix van Puzzelsport en in de boekjes Logische Puzzels en Logische Getallen van Puzzelkampioen. Het huis-aan-huis krantje 'De Oplossing' gebruikt voor dit type puzzel het woord Kakuro, dus Kakro met een extra u erin. In dit krantje zijn een aantal vakjes al ingevuld.

Ben je hier gekomen op zoek naar hulp bij de Japanse Puzzels (de plaatjespuzzels), die nog steeds iedere twee weken in Intermediair verschijnen? Klik dan hier.

Het combineren en optellen in kakro-puzzels ligt op het niveau van begin-basisschool. Niettemin lukte het mij eerst niet de puzzels uit Intermediair op te lossen. Ik verloor het overzicht over mijn kladblaadjes met invulmogelijkheden. Hieronder kun je laten berekenen met welke cijfercombinaties een bepaald totaal bereikt kan worden. Zet het rondje neer bij het gewenste aantal cijfers, vul in wat het totaal moet zijn en klik op Berekenen. De uitkomst verschijnt in het grote vak. Je kunt dit zo vaak herhalen als je maar wilt.

Aantal cijfers: 2 3 4 5 6 7 8 9
Gewenste som:


De bovenstaande berekening "via js" wordt verwezenlijkt door een javascript-programma. Het kan zichtbaar worden gemaakt via View, keuze Source of wat daarmee in het Nederlands overeenkomt. Javascript-programma's worden uitgevoerd op je eigen computer.

Bij berekenen "via php" wordt een programma aangeroepen, dat draait op de computer waarvan deze webbladzijde afkomstig is.

Voordat ik het javascript-programma maakte heb ik geprobeerd hulp te krijgen bij het oplossen via prolog-programma's. Dankzij die computerhulp kon ik een puzzel met ongeveer honderd cijfers in enkele uren oplossen. Hieronder staat het prologprogramma, daarna volgt een uitleg ervan. Tenslotte bespreek ik de programmeertaal Prolog. Wie geen benul heeft van Prolog, kan deze onderdelen maar beter in omgekeerde volgorde lezen.

Kakro-programma in Prolog

append([],Lijst2,Lijst2). append([Kop|Staart1],Lijst2,[Kop|Staart3]):- append(Staart1,Lijst2,Staart3). pick(Lijst,Element,Overige):- append(Beginstuk,[Element|Staart],Lijst), append(Beginstuk,Staart,Overige). deelpermutatie([],_). deelpermutatie([Element|Staart],Lijst):- pick(Lijst,Element,Overige), deelpermutatie(Staart,Overige). lijstsom([],0). lijstsom([Element|Staart],Som):- lijstsom(Staart,Staartsom), Som is Staartsom+Element. opgave(Lijst,Som):- deelpermutatie(Lijst,[1,2,3,4,5,6,7,8,9]), lijstsom(Lijst,T), T=Som. orde([Enige|[]]). orde([Eerste|[Tweede|Staart]]):- Eerste<Tweede, orde([Tweede|Staart]). overzicht(Lijst,Som):- opgave(Lijst,Som), orde(Lijst), write(Lijst), nl,fail. puzzeleinde([A,B,C,D,E,F,G,H,I,J]):- opgave([7,A,B,C],14), opgave([6,9,D,E,F],33), opgave([G,H,2,6,8],30), opgave([2,3,6,I,J],22), opgave([A,D,7],12), opgave([B,E,G,I,6],23), opgave([C,F,H,J],28).

Toelichting op het kakro-programma

  1. append is een woord dat zo vaak nodig is, dat het eigenlijk in prolog ingebouwd zou moeten zijn. Het plakt de eerste twee lijsten aan elkaar tot de derde lijst. De eerste definiërende regel maakt het einde van de derde lijst gelijk aan de tweede lijst. Het tweede deel van de definitie voegt de elementen van de eerste lijst stuk voor stuk toe aan de voorkant van de derde lijst.
  2. pick haalt een element uit Lijst, waardoor een lijst Overige overblijft. Pick maakt gebruik van append.
  3. deelpermutatie brengt alle permutaties voort van deelverzamelingen van Lijst. De woorden in een kakro-puzzel zijn ieder een deelpermutatie van de Lijst [1,2,...,8,9]. Deelpermutatie maakt gebruik van pick.
  4. lijstsom berekent de som van de elementen van een Lijst.
  5. opgave levert een deelpermutatie van de cijfers 1 tot en met 9 met een gegeven Som, kortom een mogelijkheid voor een opgave uit de puzzel, wanneer we voor Lijst de gewenste lengte afdwingen.
  6. orde keurt alleen die Lijsten goed, waarvan de elementen in oplopende volgorde staan. Dit woord passen we toe om het overzicht van mogelijkheden voor een woord in te korten. Het is meestal verwarrend alle permutaties voorgeschoteld te krijgen.
  7. overzicht toont de mogelijkheden voor een opgave met een bepaalde Som. Het woord fail keurt de getoonde oplossing alsnog kunstmatig af, waardoor het woord meteen de volgende oplossing gaat zoeken.
  8. puzzeleinde is een voorbeeld van het oplossen van een laatste hoekje in een bepaalde puzzel. Er waren nog 10 onbekende cijfers (A-J) over, verdeeld over vier horizontale en drie verticale opgaven.
Het liefst zou je natuurlijk de hele puzzel ineens formuleren zoals hier bij puzzeleinde is gedaan. Honderd onbekenden is echter veel te veel. Tien is wel het maximum. Met een computer die tienmaal zo snel is, zou je ook nog niet veel verder komen. De prologwoorden kunnen dus niet meer zijn dan hulp voor de menselijke oplosser die zelf ook nog flink wat werk te verzetten heeft.

De programmeertaal Prolog

Ik draai mijn Prolog nog altijd onder MS-DOS met pdprolog uit 1985. Wanneer de bovenstaande Prologwoorden tot een bestand kakro.pro zijn gemaakt, is binnen pdprolog de eerste opdracht consult(kakro). Vervolgens is het programma te bevragen via opdrachten als: De punt aan het einde van iedere vraag is onmisbaar! Pdprolog is te verlaten met exitsys.

Een Prologprogramma bestaat uit een beschrijving van het probleem, waarmee het Prologsysteem zelf naar een oplossing gaat zoeken. De programmeur hoeft de weg naar de oplossing dus niet te wijzen, zoals in alle gewone programmeertalen. Het zoeken van de oplossing komt voor Prolog neer op het systematisch langslopen van alle takken in een boom van mogelijkheden. Dat kan lang duren. Het is mogelijk het zoekproces een beetje te sturen, maar dat gaat ten koste van de overzichtelijkheid en de flexibiliteit van het programma. Zo probeert ons Prologwoord opgave, wanneer de som 7 moet zijn, ook de cijfers 8 en 9. Zouden we dat willen voorkomen, dan zouden we het woord opgave niet meer elegant kunnen opsplitsen in deelpermutatie en lijstsom. De systematiek en de snelheid van de computer moeten de overbodige probeersels goedmaken.

Inleidende uitleg over Prolog is te vinden in de Wikipedia. Er is een Tsjechische webstek via welke je prologprogramma's via het net kunt draaien. De prologverwerker daar kan echter niet overweg met de optellingen in het kakro-programma.

De beste beschrijving van Prolog is het papieren boek van Henk Schotel: Programmeren in Prolog, Coutinho, Muiderberg, 1987, ISBN 90 6283 696 8. Henk Schotel schreef dit boek in zijn glorieuze Nijmeegse tijd. Daarna moest hij genoegen nemen met een nederig baantje in Maastricht. Een schrijnend voorbeeld van hoe de huidige wereld geniaal talent verspilt. Deze prachtige pdf beschrijft, hoe een Prologverwerker van binnen in elkaar zit.

Tweede versie van het programma

Hier is een tweede versie van het Prologprogramma. Onder andere het woord overzicht is handiger gemaakt. In plaats van overzicht([A,B,C,D,E],25). voer je nu in overzicht(5,25). De 5 is de lengte van de lijst, de 25 de som. Het samenstellen van de lijst en het bepalen van de som zijn nu gecombineerd in een woord ovrzcht, dat de gebruiker niet rechtstreekts hoeft aan te spreken. Het woord puzzeleinde zou hiermee sneller geworden moeten zijn, maar tot mijn verbazing is dat niet het geval. append([],Lijst2,Lijst2). append([Kop|Staart1],Lijst2,[Kop|Staart3]):- append(Staart1,Lijst2,Staart3). pick(Lijst,Element,Overige):- append(Beginstuk,[Element|Staart],Lijst), append(Beginstuk,Staart,Overige). permutatie([],[]). permutatie(Lijst,[Element|Staart]):- pick(Lijst,Element,Overige), deelpermutatie(Overige,Staart). opgv(Lengte,Som,Lijst):- ovrzcht(Lengte,Som,[1,2,3,4,5,6,7,8,9],Lijstuit), permutatie(Lijstuit,Lijst). puzzeleinde([A,B,C,D,E,F,G,H,I,J]):- opgv(4,14,[7,A,B,C]), opgv(5,33,[6,9,D,E,F]), opgv(5,30,[G,H,2,6,8]), opgv(5,22,[2,3,6,I,J]), opgv(3,12,[A,D,7]), opgv(5,23,[B,E,G,I,6]), opgv(4,28,[C,F,H,J]). pak(Lijst,Element,Daarachter):- append(L,[Element|Daarachter],Lijst). ovrzcht(1,Som,Lijstin,[Som]):- Som<10. ovrzcht(Lengte,Som,Lijstin,[Element|Lijstuit]):- Lengte1 is Lengte-1, pak(Lijstin,Element,[Eerste|Overige]), Som1 is Som-Element, Som1>=Eerste, ovrzcht(Lengte1,Som1,[Eerste|Overige],Lijstuit). overzicht(Lengte,Som):- ovrzcht(Lengte,Som,[1,2,3,4,5,6,7,8,9],Lijstuit), write(Lijstuit),nl,fail.

Programma voor Enigma 1317

De basiswoorden uit het eerste Prologprogramma kunnen ook bij allerlei andere puzzels worden toegepast. Hier is een programma voor het raadsel (Enigma) 1317 uit de New Scientist van 27 november 2004, bladzijde 47. Daar gaat het om twee getallen van vijf cijfers. In de twee getallen worden alle tien de cijfers gebruikt. Het tweede getal is acht maal het eerste. De som van de cijfers van het eerste getal is kleiner dan de som van de cijfers van het tweede.

Het eerste getal is kleiner dan 12500. Was het groter, dan besloeg het achtvoud ervan immers niet vijf, maar zes cijfers. Het eerste cijfer is dus zeker een 1. Een Prologprogramma voor deze puzzel komt er dan zo uit te zien:

append([],Lijst2,Lijst2). append([Kop|Staart1],Lijst2,[Kop|Staart3]):- append(Staart1,Lijst2,Staart3). pick(Lijst,Element,Overige):- append(Beginstuk,[Element|Staart],Lijst), append(Beginstuk,Staart,Overige). deelpermutatie([],_). deelpermutatie([Element|Staart],Lijst):- pick(Lijst,Element,Overige), deelpermutatie(Staart,Overige). lijstsom([],0). lijstsom([Element|Staart],Som):- lijstsom(Staart,Staartsom), Som is Staartsom+Element. maalacht([A,B,C,D,E],[F,G,H,I,J]) :- J1 is 8*E, J is J1 mod 10, I1 is J1/10, I2 is 8*D, I is (I1 + I2) mod 10, H1 is (I1 + I2)/10, H2 is 8*C, H is (H1 + H2) mod 10, G1 is (H1 + H2)/10, G2 is 8*B, G is (G1 + G2) mod 10, F1 is (G1 + G2)/10, F2 is 8*A, F is (F1 + F2) mod 10, (F1+F2)/10 < 1. oplossing([B,C,D,E]) :- deelpermutatie([1,B,C,D,E],[0,1,2,3,4,5,6,7,8,9]), maalacht([1,B,C,D,E],[F,G,H,I,J]), deelpermutatie([1,B,C,D,E,F,G,H,I,J], [0,1,2,3,4,5,6,7,8,9]), lijstsom([1,B,C,D,E],Som1), lijstsom([F,G,H,I,J],Som2), Som1 > Som2. Het woord maalacht is een bijzonder geval van een deelprogramma dat je zou kunnen maken om twee getallen in lijstvorm met elkaar te vermenigvuldigen. Het programma levert binnen enkele seconden precies één oplossing.

Programma voor Enigma 1324

Bij raadsel 1324 op bladzijde 47 van de New Scientist van 22 januari 2005 ging het om negen cijfers, die als volgt gerangschikt zijn: GHI DEF ABC De acht getallen die van links naar rechts en van boven naar beneden gelezen kunnen worden, zijn alle kwadraten van gehele getallen. Met drie cijfers is het maximum 312. Deze kwadraten kunnen we dus gewoon opsommen. Het kruisen wordt aangepakt als bij het woord puzzeleinde hierboven. Verder hebben we alleen een woord nodig, dat elementen uit een lijst haalt. Zo komen we tot het volgende prologprogramma: member( Y, [Y|_] ). member( B, [_|C] ) :- member(B,C). oplossing([A,B,C,D,E,F,G,H,I]) :- member([A,B,C],[ [1,0,0],[1,2,1],[1,4,4],[1,6,9],[1,9,6], [4,0,0],[4,4,1],[4,8,4],[9,0,0],[9,6,1] ]), member([D,E,F],[ [1,0,0],[1,2,1],[1,4,4],[1,6,9],[1,9,6], [2,2,5],[2,5,6],[2,8,9],[3,2,4],[3,6,1], [4,0,0],[4,4,1],[4,8,4],[9,0,0],[9,6,1], [5,2,9],[5,7,6],[6,2,5],[6,7,6],[7,2,9], [7,8,4],[8,4,1] ]), member([G,H,I],[ [1,0,0],[1,2,1],[1,4,4], [2,8,9],[3,2,4],[3,6,1], [4,0,0],[4,4,1],[4,8,4],[9,0,0],[9,6,1], [5,2,9],[7,2,9], [7,8,4],[8,4,1] ]), member([G,E,C],[ [1,0,0],[1,2,1],[1,4,4],[1,6,9],[1,9,6], [2,2,5],[2,5,6],[2,8,9],[3,2,4],[3,6,1], [4,0,0],[4,4,1],[4,8,4],[9,0,0],[9,6,1], [5,2,9],[5,7,6],[6,2,5],[6,7,6],[7,2,9], [7,8,4],[8,4,1] ]), member([D,B],[ [1,6],[2,5],[3,6],[4,9],[6,4],[8,1] ]), member([H,F],[ [1,6],[2,5],[3,6],[4,9],[6,4],[8,1] ]). Het programma komt met vier oplossingen. In de puzzel werden nog twee aanvullende eisen gesteld:
  1. De kwadraten zijn allemaal verschillend. Daardoor vallen twee van de oplossingen af.
  2. Het kwadraat 81 komt niet voor. Daardoor valt nog een oplossing af.
Er blijft één oplossing over.

Nonogrammen

De Japanse Puzzels waarmee Intermediair nog steeds iedere twee weken zijn lezers teistert, zijn tussenlandelijk bekend onder de naam nonogram. Op deze Engelse webstek kun je de puzzel meteen vanuit je grasduiner oplossen. Je moet de puzzel op de volgende manier in het invoervak invoeren: width 20 height 20 rows 1 1,1,1,1 2,1,2,1,1 ... zo vul je 20 regels met de getallen links van de puzzel... 4,2,7,2 6,2,5,1,1 columns 2 1,1,2,3 2,1,1,1,2 ... zo vul je 20 regels met de getallen boven de puzzel... 2,1,6,2 1,1,1,4 Druk op Start en na enkele seconden heb je de oplossing. In Nederland zijn twee oplosprogramma's beschikbaar, die je kunt neerladen, een in Java en een in Perl. Ook de roemruchte christen-hacker Frans Faase heeft zich ooit met een dergelijk programma beziggehouden. Deze programma's bootsen allemaal de werkwijze na van de menselijke puzzelaar.

Met hun zware en witte blokjes zien de rijen (en de kolommen) van een nonogram eruit als chromosomen. Het lijkt dan ook voor de hand te liggen ook eens een genetische algoritme als oplossingsmethode te proberen. Dat blijkt al geprobeerd, en wel in deze pdf uit Leiden. Het resultaat valt flink tegen. De oplostijd is nu niet enkele seconden, maar een aantal uren, zo de oplossing al gevonden wordt. De toegepaste genetische algoritme is er niet zomaar een, maar is speciaal op dit probleem toegesneden.

Naar mijn introductiepagina, bijvoorbeeld om in het gastenboek te schrijven.