login  Naam:   Wachtwoord: 
Registreer je!
 Forum
Zoeken  Regels  Help

Sudoko

Offline bart_dm - 30/12/2016 21:44
Avatar van bart_dmNieuw lid Hallo,

Ik ben met een klein scriptje bezig die een sudoku moet oplossen.
Ik ben er bijna maar door een logica probleem zit ik vast.

Ik overloop mijn 9*9 cijferrasters waar geen cijfer is (1 - 9).
Die vakjes heb ik opgevuld met een 0.

Dus als ik een 0 tegenkomen dan loop ik van 1 tot en met 9 of die kan ingevuld worden. Hier wordt gecontroleerd of die reeds in de rij, kolom of 3x3 box aanwezig is. Is dit niet het geval dan wordt het cijfer ingevuld.

Probleem is dat voor sommige vakjes meer dan 1 oplossing mogelijk is.
En als niet direct de juiste waarde ingevuld wordt dan blijven op het einde vakken met een 0 staan omdat daar geen oplossing meer voorhanden is.

Nu heb ik wel op internet gekeken naar algoritmes om dat op te lossen en ik kom steeds op het backtracking algoritme terecht o.a. op Wikipedia.

Maar ik snap dat principe niet....
Hoe implementeer je dat?

1 antwoord

Gesponsorde links
Offline Thomas - 31/12/2016 14:54
Avatar van Thomas Moderator Backtracking? Misschien bedoel je recursie? Of dat is in ieder geval een mogelijkheid denk ik: als je ergens een open vakje hebt met meerdere keuzes, vul alle mogelijke waarden in die weer een nieuwe sudoku vormen die je als invoer aan dezelfde functie kunt voeren... net zolang totdat je de (of een) oplossing hebt (er geen vakjes meer ingevuld kunnen worden).

Een mogelijke optimalisatie is dat je eerst controleert of er vakjes zijn met maar één keuze. Dit kan namelijk in de volgende iteratie tot gevolg hebben dat een ander vakje slechts één keuze heeft. Dit is gewoonlijk de manier waarop je eenvoudige sudoku's oplost. En zo zijn er nog meer regels die je kunt implementeren die het aantal mogelijkheden op voorhand beperkt, die je dan dus ook niet hoeft uit te rekenen.

Wat ik mij wel afvraag is of er, gegeven een initiële (incomplete) sudoku, een soort van wiskundig bewijs opgesteld kan worden dat aantoont dat er maar één oplossing is. Ik kan mij zo voorstellen dat je op een gegeven moment (wanneer je maar genoeg velden blanco laat) ruimte creëert voor meerdere oplossingen. Mogelijk zou je in de implementatie dus ook rekening kunnen houden met meerdere geldige oplossingen.
Gesponsorde links
Je moet ingelogd zijn om een reactie te kunnen posten.
Actieve forumberichten
© 2002-2017 Sitemasters.be - Regels - Gehost door: FireMultimedia - Laadtijd: 0.145s