Boudewijns blogje

Hoe reageert 'ie als een ingevoerd probleem meerdere oplossingen heeft? Stopt hij bij de eerst gevonden oplossing of laat hij alle mogelijke oplossingen zien?

(yep: ik ben te lui en heb niet de programmeerervaring op het even zelf te proberen...)

Wel leuk om te doen , zelf ben ik op de Uni bezig met het leren van haskell wat backtracking een stuk makkelijker (en minder code ) maakt dan met java . Alleen is de leesbaarheid wat minder

500 regels? Ik heb het wel eens in 1 regel gezien, . Dat was volgens mij Ruby of Python, een van de twee. Een wiki-pagina daarvan werkt helaas niet meer en/of staat vol met spam, maar de code is als volgt:


code:

1 2 3 4

def r(a):i=a.find('0');~i or exit(a);[m in[(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3)or a[j]for j in range(81)]or r(a[:i]+m+a[i+1:])for m in'%d'%5**18] from sys import*;r(argv[1])

Ik meen toch echt dat d'r eentje was die eenvoudiger was, maar het kan zijn dat ik me vergis.

Ik heb sowieso het idee dat je oplosser een stuk korter kan (zie ook backtracking), maar da's niet altijd het belangrijkste.

@Yopy
Tja man, beetje logische dat bruteforce / backtracking in weinig code geklopt kan worden (leuk voorbeeld daarin ). Het kost waarschijnlijk alleen veel meer rekenen. Niet dat we daar echt een probleem mee krijgen.


Ik ben in het verleden zelf bezig geweest met een technisch / tactisch spelende sudoku-software. Niet dat ik alle deducties zelf al kan uitvoeren. De lap code zou groter zijn in ruil voor snelheid.

Voor dit soort dingen is een declaratieve taal zoals in ECLiPSe (http://en.wikipedia.org/wiki/ECLiPSe) ideaal.

Ik heb de voorbeeldsudoku ook even door mijn solver gehaald en die weet hem ook op te lossen in 250 ms (P4 2.8). Mijn solver gebruikt puur strategieën die je normaal op papier ook zou gebruiken. Forken hoort daar niet bij

Ik heb even gekeken naar welke strategieën mijn oplosser gebruikt heeft. Dat zijn er twee geweest.

1. Paired Cell Strategy: Er bestaan op een rij twee cellen waarin alleen de mogelijkheden 6 en 9 nog open zijn. Je kan dan in de andere cellen in die rij de 6 en 9 wegstrepen uit de mogelijkheden. Bijv als volgt:

code:

1	3 1 (6, 9) 4 7 5 2 (6, 9)(6, 8, 9)

Daar kunnen de 6 en 9 dus weg uit de laatste cel, waardoor daar allen nog de 8 staat. Het paar kan ook 'verstopt zijn'. Dat is bijvoorbeeld hieronder het geval:

code:

1	3 1 (6, 9, 7) 4 (7, 8) (7, 5) 2 (6, 9) (5, 7, 8)

Je kan daar in cel 3 de 7 wegstrepen, omdat de 6 en 9 in cel 3 en 8 moeten en nergens anders kunnen. De 7 past daar dus niet.

2. Cell Overlap Strategy: Je maakt gebruik van de opverlap tussen rijen en kwadranten (3x3 vakken). Voorbeeld uit jouw sudoku:

code:

1 2 3

(2, 6, 9)(3, 6, 9)(2, 3, 6, 9) (2, 3, 6) 5 1 4 8 7 (2, 5, 6, 7, 9)(4, 6, 7, 9) 8 (2, 5, 6, 7)(3, 4, 6, 7) 1

Je ziet hier de vierde rij en het vierde kwadrant (linksmidden) volledig weergegeven met alle opties die op dat punt in het oplossen nog beschikbaar waren. Je ziet dat de 9 in de rij alleen in het vierde kwadrant kan liggen. Dat betekent dat je de 9 op de andere plaatsen in dat kwadrant weg kan halen:

code:

1 2 3

(2, 6, 9)(3, 6, 9)(2, 3, 6, 9) (2, 3, 6) 5 1 4 8 7 (2, 5, 6, 7)(4, 6, 7) 8 (2, 5, 6, 7)(3, 4, 6, 7) 1

Misschien heb je er wat aan, misschien hoort het niet bij je opdracht

Ik ben de oplosser begonnen met alleen maar de simpele strategieen (1 optie in een cel of 1 mogelijke plaats in een groep cellen). Daarna heb ik hem puzzels laten oplossen tot zo ver hij kwam. Die uitkomsten ben ik toen met de hand gaan oplossen en ik heb de oplosmethode gegeneraliseerd en geïmplementeerd in mijn oplosser. Vervolgens weer puzzels laten oplossen en weer met de hand aangevuld en geïmplementeerd. Dit alles totdat mijn gebrek aan programmeerskills mij weerhield van het oplossen van 6-sterren puzzels.

Mijn uitdaging is nog steeds om 'Killer Sudokus' op te gaan lossen.

quote: fl!pull

@Yopy
Tja man, beetje logische dat bruteforce / backtracking in weinig code geklopt kan worden (leuk voorbeeld daarin ). Het kost waarschijnlijk alleen veel meer rekenen. Niet dat we daar echt een probleem mee krijgen.

Ik weet, . Die van mij deed er toendertijd een seconde over om de meeste sudoku's (van allerlei moelijkheidsgraden) op te lossen.

Ik was eerst begonnen met eentje die het zoals ik oploste (kijken naar wat zijn de enige mogelijkheden in rij / kolom / vak en nog eenzelfde die alles wat gewoon niet mogelijk was wegkraste). Die kon ook een groot deel van de sudoku's oplossen (tot 'medium', soms 'hard' op een of andere website).

Ik heb hem net even uit mn hoofd opgelost, ik wil niet doen alsof ik 1 of andere sudoku koning ben, maar hij viel opzich best mee, je kan heel veel getallen met de meest basis regels vinden, bijvoorbeeld alle 1 heb je aan het begin als het goed is al.


code:

1 2 3 4 5 6 7 8 9 10 11

693 | 784 | 512 487 | 512 | 936 125 | 963 | 874 ----+-----+---- 932 | 651 | 487 568 | 247 | 391 741 | 398 | 625 ----+-----+---- 319 | 475 | 268 856 | 129 | 743 274 | 836 | 159

Ik ben er geloof ik 20 minuten mee bezig geweest. Ik heb geen lijst met mogelijke nummers gemaakt, dat vind ik altijd zo lame probeer dat altijd in mijn hoofd te doen.

Ik heb niet echt een officiële benaming voor al mijn " regels ". Dingen die ik doe zijn:

- er is maar 1 mogelijkheid, door het blok, door de rijen of de kolommen. daarmee kon ik bijvoorbeeld alle 1en in dit ding al vinden.
- als op 1 of andere manier ergens 2 cijfers in de zelfde kolom / rij alleen maar op die plek kunnen, gebruik ik dat om in de rest van de kolom/ rij de cijfers te elimineren... met dit mooie voorbeeldje moet dat wel duidelijk zijn:

code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14

1-5 | --- | --- 2-- | --- | --- 3-4 | --- | --- ----+-----+---- 5-2 | --- | --- --- | -6- | --- <- geen 6 verder op deze rij 4-3 | --- | --- ----+-----+---- --- | --- | --- --- | --- | --- --- | --- | --- ^ 6 ergens op deze rij in het middelste blok ^ enige plek in de bovenste waar nog een 6 past :)

Waarbij die regel vele vormen kent.
- als een blok bijna vol is, maar 1 hele rij van het blok nog niet, die cijfers mogen niet meer in de rest van de rij.

Klinkt misschien allemaal wat vaag, maar zo heb ik ze uitgevonden, en ze werken prima

is dit een opdracht uit een mastervak? klinkt meer als inleiding programmeren ofzo

Hier nog een leuke sudoku om je solvertje mee te testen

002 | 090 | 107
038 | 600 | 000
400 | 000 | 000
----+-----+----
000 | 005 | 000
009 | 010 | 300
000 | 400 | 000
----+-----+----
000 | 000 | 004
000 | 007 | 920
806 | 030 | 700

Op http://scanraid.com/sudoku.htm vindt je heel veel oplossingsstrategieen. Mijn oplosser heeft volgens mij alleen de eerste 7 en die kan jouw sudoku oplossen.

Ik heb dat ooit eens geprobeerd, maar destijds waren mijn programmeer skills niet voldoende, icm mijn motivatie, om tot iets te komen.

Maar leuk project!

Ik heb me overigens altijd afgevraagd of een sudoku 'analytisch' opgelost kan worden. i.e. een formule oid op te stellen die de complete matrix uitspuugt. De reden daarvoor is dat een sudoku nogal regelgebonden is, met een bekende blok structuur.