Sudoku

[Jaimy11]

Hallo,

Ik weet niet of er hier mensen met ervaring met magma, maar ik zit met een probleempje.

We krijgen telkens oefenopdrachten die iets moeilijker zouden moeten zijn dan de stof t.v.v. het tentamen.

Nu vond ik dingen als matrices inverteren e.d. geen probleem.

Nu is gevraagd een algoritme te schrijven voor het oplossen van een sudoku.......

Ik heb iets dergelijks nog niet eerder hoeven doen en weet dus ook niet hoe zo'n algoritme er uberhaupt uitziet....

Iemand die een voorbeeldcode heeft, of een duidelijke uitleg?

Alvast bedankt

Jaimy

[Drieske]

Ik snap niet wat nu juist de bedoeling is... Krijg je een lege (9 x 9)-matrix en moet je een oplossing genereren? Je vermeldt 'magma', past dit dan in het kader van de geziene theorie daaromtrent?

[Landro]

Er zijn vershillende manieren om dit aan te pakken.

1. Brute force. Laat het algoritme alle mogelijkheden uitproberen totdat je een match hebt.

2. Gebruik dezelfde logica die een mens zou toepassen.

Begin met voor ieder veld te bepalen welke getallen toegestaan zijn voor dat veld

[jhnbk]

Doe eerst 2, en dan depth first search (1) waarbij je ook de logica van 2 gebruikt.

[Jaimy11]

Aha...

Dit zegt mij vrijwel nix allemaal.

Ja goed ik weet wat brute force is, maar hoe pas je dat toe in een magma-script?

Er stond als hint bij om een recursieformule op te stellen.

Maar ook dan heb ik geen idee hoe een recursieformule mijn probleem oplost.

En Drieske;

Nee het is geen lege 9x9 matrix.

We hebben 5 testvoorbeelden gekregen (dus sudoku met een aantal getallen ingevuld).

Deze kan ik nu niet hier posten helaas, het is een .m bestand welke ik niet vanuit hier kan openen...

En nee, het past niet bij wat we hebben besproken tot nog toe...

[Landro]

1. Maak eerst een matrix/tabel/array aan van 9x9 en vul dan de waardes in die je hebt.

2. Vervolgens ga je dan voor ieder veld na welke waardes er niet meer mogelijk zijn omdat deze al in dezelfde rij, kolom of vierkant voorkomen. Dit levert waarschijnlijk een aantal velden op waar slechts 1 waarde mogelijk is. Doorloop deze stap net zolang tot je geen nieuwe waardes meer vind. Afhankelijk van hoe moeilijk de sudoku is, kan het mogelijk zijn dat je hem nu compleet opgelost hebt.

3. Zoniet, dan zul je een brute force attack moeten doen waarbij je een voor een alle waardes in alle nog niet opgeloste velden uitprobeert.

[Xenion]

Er stond als hint bij om een recursieformule op te stellen.

Maar ook dan heb ik geen idee hoe een recursieformule mijn probleem oplost.

Dit lijkt mij een vrij moeilijke opgave als je niet bekend bent met algemene zoekproblemen.

Zoek op google eens naar 'sudoku recursion', van wat ik zo op het eerste zicht zie komt er bijna altijd backtracking aan te pas.

Idee van backtracking:

Als je vast zit: maak de laatste zet ongedaan, kies daar iets anders en kijk of je daarmee verder kan.

[jhnbk]

Hier staan alvast de principes uitgelegd die van toepassing zijn: http://norvig.com/sudoku.html (Programeertaal is wel Python)

[Jaimy11]

backtracking

Ik zal dit eens nader bekijken, lijkt me de eenvoudigste optie...

[Typhoner]

ik heb zelf ooit zoiets geschreven: het werkte in ieder geval met alle sudoku's uit de krant

Hierbij wordt voor elke kolom, rij en vak bepaalt wat er nog mist - en dus nog mogelijk is qua invullen. Vervolgens wordt de hele sudoku doorlopen, en de mogelijkheden van de rij, kolom en vak voor elke lege cel "opgeteld" (alleen de getallen die in allen aanwezig zijn worden weerhouden). Als er maar één waarde overblijft wordt deze ingevuld. Hierna beginnen we van vooraf aan.

Verrassend genoeg is dit voldoende voor de meeste sudoku's. Ik heb nog iets geavanceerdere methoden bedacht, maar die heb ik nooit getest.

[317070]

ik heb zelf ooit zoiets geschreven: het werkte in ieder geval met alle sudoku's uit de krant

Hierbij wordt voor elke kolom, rij en vak bepaalt wat er nog mist - en dus nog mogelijk is qua invullen. Vervolgens wordt de hele sudoku doorlopen, en de mogelijkheden van de rij, kolom en vak voor elke lege cel "opgeteld" (alleen de getallen die in allen aanwezig zijn worden weerhouden). Als er maar één waarde overblijft wordt deze ingevuld. Hierna beginnen we van vooraf aan.

Verrassend genoeg is dit voldoende voor de meeste sudoku's. Ik heb nog iets geavanceerdere methoden bedacht, maar die heb ik nooit getest.

Yup, ik heb ooit nog hetzelfde geschreven. Het werkt niet voor alle sudoku's.

Ik heb daarom als stap 2 een backtracking-algoritme. Als er geen enkel vakje is met 1 mogelijkheid: gok. Iedere keer als je vast zit keer je terug naar je laatste gok en kun je die mogelijkheid ook schrappen. Op die manier vind je altijd een oplossing.

Dit was trouwens ook als recursie geïmplementeerd! Die recursie lijkt me de eenvoudigste methode, omdat je erg eenvoudig kunt starten en het algoritme stap voor stap kunt verbeteren.

[Typhoner]

de "geavanceerde" aanpak die ik nog had bedacht, was om per rij/kolom/vak de mogelijkheden van elke lege cel te bekijken: als er ergens één cel met een unieke waarde qua mogelijkheden was, moest uiteraard deze worden ingevuld. Maar dat heb ik nooit geïmplementeerd. Zou ik eigenlijk eens toch moeten doen.

[Jaimy11]

Weet iemand of er ook een site is waar alle codes staan?

De commando's bedoel ik dan, want of ik zoek slecht of ik vind niks.....

[Jaimy11]

Mijn code geeft deze foutmelding:

Code: Selecteer alles

sudoku_oplossing(

A: [0 2 3 0 0 1 7 0 0] [0 0 8 4 6 0 0 1 0] [9 0 0 0 5 0 0 4 8] ...

)

>> eliminate_rij(A, cand_rij);

^

Runtime error in procedure call: Number of arguments (2) does not equal expected

number of arguments (3)

Ik begrijp niet wat er mis gaat...

Heeft iemand een idee?

[Xenion]

Je gebruikt een procedure eliminate_rij en je geeft daar 2 argumenten mee (de dingen tussen de haakjes). De procedure die je geschreven hebt verwacht echter 3 argumenten, je gebruikt ze dus niet juist.