Springen naar inhoud

Sudoku


  • Log in om te kunnen reageren

#1

Jaimy11

    Jaimy11


  • >250 berichten
  • 614 berichten
  • Ervaren gebruiker

Geplaatst op 15 januari 2012 - 19:35

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

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

Drieske

    Drieske


  • >5k berichten
  • 10217 berichten
  • Moderator

Geplaatst op 15 januari 2012 - 19:59

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.

#3

Landro

    Landro


  • 0 - 25 berichten
  • 18 berichten
  • Gebruiker

Geplaatst op 15 januari 2012 - 20:00

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

Veranderd door Landro, 15 januari 2012 - 20:00


#4

jhnbk

    jhnbk


  • >5k berichten
  • 6905 berichten
  • VIP

Geplaatst op 15 januari 2012 - 20:04

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.

#5

Jaimy11

    Jaimy11


  • >250 berichten
  • 614 berichten
  • Ervaren gebruiker

Geplaatst op 15 januari 2012 - 21:46

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

Veranderd door Jaimy11, 15 januari 2012 - 21:47


#6

Landro

    Landro


  • 0 - 25 berichten
  • 18 berichten
  • Gebruiker

Geplaatst op 15 januari 2012 - 22:58

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.

#7

Xenion

    Xenion


  • >1k berichten
  • 2606 berichten
  • Moderator

Geplaatst op 16 januari 2012 - 14:25

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.

#8

jhnbk

    jhnbk


  • >5k berichten
  • 6905 berichten
  • VIP

Geplaatst op 16 januari 2012 - 17:26

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.

#9

Jaimy11

    Jaimy11


  • >250 berichten
  • 614 berichten
  • Ervaren gebruiker

Geplaatst op 16 januari 2012 - 21:04

backtracking


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

#10

Typhoner

    Typhoner


  • >1k berichten
  • 2446 berichten
  • VIP

Geplaatst op 16 januari 2012 - 22:29

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.

#11

317070

    317070


  • >5k berichten
  • 5567 berichten
  • Moderator

Geplaatst op 16 januari 2012 - 23:26

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-

#12

Typhoner

    Typhoner


  • >1k berichten
  • 2446 berichten
  • VIP

Geplaatst op 17 januari 2012 - 12:20

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.

#13

Jaimy11

    Jaimy11


  • >250 berichten
  • 614 berichten
  • Ervaren gebruiker

Geplaatst op 24 februari 2012 - 11:16

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

#14

Jaimy11

    Jaimy11


  • >250 berichten
  • 614 berichten
  • Ervaren gebruiker

Geplaatst op 26 februari 2012 - 16:33

Mijn code geeft deze foutmelding:

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?

#15

Xenion

    Xenion


  • >1k berichten
  • 2606 berichten
  • Moderator

Geplaatst op 26 februari 2012 - 17:35

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.





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures