Sudoku

Moderators: jkien, Xilvo

Reageer

Bericht 15-01-'12, 19:35

Jaimy11

Gebruikersavatar
Berichten: 614

Sudoku

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
Omhoog

Bericht 15-01-'12, 19:59

Drieske

Gebruikersavatar
Berichten: 10.179

Re: Sudoku

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?
Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.
Omhoog

Bericht 15-01-'12, 20:00

Landro

Berichten: 18

Re: Sudoku

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
Omhoog

Bericht 15-01-'12, 20:04

jhnbk

Gebruikersavatar
Berichten: 6.905

Re: Sudoku

Doe eerst 2, en dan depth first search (1) waarbij je ook de logica van 2 gebruikt.
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.
Omhoog

Bericht 15-01-'12, 21:46

Jaimy11

Gebruikersavatar
Berichten: 614

Re: Sudoku

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...
Omhoog

Bericht 15-01-'12, 22:58

Landro

Berichten: 18

Re: Sudoku

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.
Omhoog

Bericht 16-01-'12, 14:25

Xenion

Gebruikersavatar
Berichten: 2.609

Re: Sudoku

Jaimy11 schreef: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.
Omhoog

Bericht 16-01-'12, 17:26

jhnbk

Gebruikersavatar
Berichten: 6.905

Re: Sudoku

Hier staan alvast de principes uitgelegd die van toepassing zijn: http://norvig.com/sudoku.html (Programeertaal is wel Python)
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.
Omhoog

Bericht 16-01-'12, 21:04

Jaimy11

Gebruikersavatar
Berichten: 614

Re: Sudoku

backtracking


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

Bericht 16-01-'12, 22:29

Typhoner

Gebruikersavatar
Berichten: 2.455

Re: Sudoku

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.
This is weird as hell. I approve.
Omhoog

Bericht 16-01-'12, 23:26

317070

Gebruikersavatar
Berichten: 5.609

Re: Sudoku

Typhoner schreef: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.
What it all comes down to, is that I haven't got it all figured out just yet

And I've got one hand in my pocket and the other one is giving the peace sign

-Alanis Morisette-
Omhoog

Bericht 17-01-'12, 12:20

Typhoner

Gebruikersavatar
Berichten: 2.455

Re: Sudoku

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.
This is weird as hell. I approve.
Omhoog

Bericht 24-02-'12, 11:16

Jaimy11

Gebruikersavatar
Berichten: 614

Re: Sudoku

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.....
Omhoog

Bericht 26-02-'12, 16:33

Jaimy11

Gebruikersavatar
Berichten: 614

Re: Sudoku

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?
Omhoog

Bericht 26-02-'12, 17:35

Xenion

Gebruikersavatar
Berichten: 2.609

Re: Sudoku

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.
Omhoog
Reageer

Terug naar “Informatica en programmeren”