 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. |
Wat is jouw favoriete javascript framework? (S: 18, R: 2)
Gesponsorde links
Actiefste leden van de maand
