Sudoku Cracker

Door Martijn Wieringa op 30-09-2006 19:48

453 views

'k ben bezig met een javascript sudoku-cracker ;)

Hij werkt nu nog vrij simpel; het script streept gewoon steeds waarden af, en als een kolom nog maar 1 waarde over heeft wordt deze ingevuld als hoofdwaarde. Zodra er geen waarden meer afgestreept kunnen worden, zoekt de cracker naar waarden die t.o.v. de rij/kolom/vak op nog maar 1 plek ingevuld kunnen worden.

Simpele sudoku puzzels zijn op deze manier via de cracker in no-time opgelost, maar iets moeilijkere puzzels nog niet.

Nu heb ik een poging gewaagd om complexere situaties te kraken, zoals de situatie als 2 velden in een rij beide dezelfde 2 opties bevatten, dat je dan deze opties van de overige velden in de rij kunt schrappen..

maar goed, dit lijkt al snel te complex te worden voor JS.. de browser gaat klagen dat het scripts veels te vee werk heeft, enz..

anyway.. ik zie ff door de bomen het bos niet meer ;) Nu mijn vraag of iemand slimme input heeft om deze tool verder te ontwikkelen.

Over de tool: klik op '(re)load values' om de puzzel op te starten.. de waarden in de textarea komen overeen met rij/kolom/waarde in het veld en worden BOLD weergegeven in de puzzel. Gevonden waarden worden vervolgens UNDERLINED weergegeven. Wanneer een veld meerdere opties overhoud, worden deze in ITALIC, in het rood weergegeven.

Indien de puzzel niet opgelost kan worden, blijven er dus rode waarden zichtbaar. Deze waarden aanklikbaar. Er verschijnt dan een popup waarin je een 'waarde' op kunt geven voor het betreffende veld..

Linkje: http://www.pholeron.nl/javascript/sudoku/

Ik heb de puzzel van http://www.sudokunet.nl/ gejoopt ;)

Martijn Wieringa

01-10-2006 11:32

@Jan koehoorn

Klopt! Het script hanteerd dat ook als de basis van het 'filteren' van mogelijke waarden..

Als het script begint heeft elk veld de waarde 'null', en en mogelijke opties 1 t/m 9.

Bij het invullen van een waarde in een veld, wordt diezelfde waarde weggestreept in alle overige velden in de rij/kolom/vak.

Wanneer er geen waarden meer weggestreet kunnen worden, controleert het script of er een veld bestaat die nog maar 1 optie over heeft. Indien dat het geval is, wordt deze optie voor het veld ingevuld, en wordt wederom de waarde bij alle overige velden wegestreept (t.o.v. rij/kolom/vak).

Als dat ook geen resultaten meer opleverd, doorzoekt het script per rij/kolom/vak of er een veld is die een mogelijke optie bevat, die niet beschikbaar is voor andere velden in dezelfde rij/kolom/vak. Indien een veld de enige in een rij/kolom/vak is die en bepaalde waarde mag bevatten, heef deze die waarde dus ook ;)

Als dan ook geen resultaten opleverd geeft het script het op..

Martijn Wieringa

01-10-2006 11:53

@legolas,

Ik zie dat jij um op basis van een PHP script hebt gebouwd! Kan ook handig zijn, de snelheid is i.i.g. heel wat beter dan via Javascript. Misschien dat ik ut ook maar om ga zetten naar PHP dan ;)

Maar hoe werkt je script? Welke strategie hanteerd het?

Als ik het zelfde voorbeeld invoer als ik in mijn script gebruikte vult jouw script al meer waarden in dan de mijne, maar weet 'ie ze ook niet allemaal te vullen..

Martijn Wieringa

01-10-2006 11:56

Owh, en over de script snelheid..

Wat betreft de snelheid.. het script was in eerste instantie zo bedoeld dat je eerst een veld aan klikt, een waarde invuld, en dat deze dan wordt verwerkt. Als je het script ook op die manier gebruikt gaat het best vlot, en werkt ut prima.

Via het tekstvak blaas ik echter 20+ waarden achter elkaar de puzzel in zodat jullie niet zelf waarden hoeven te verzinnen.. dat vind je browser minder leuk waardoor ie wat begint te 'kreunen' soms ;)

Martijn Wieringa

01-10-2006 11:59

Reageren

Inloggen om te reageren