[c++] stelsel van vergelijking

[elgringo]

Ik heb mezelf op de hals gehaald om het spel sudoku (of hoe je het ook mag spellen) op te laten lossen door een pc.

het spel:
Het het een vlak van 9x9 elke rij en elke kolom moet een soms van 45 hebben (9+8..+2+1) en elk cijfer van 1...9 mag er maar 1 keer in voorkomen.
Verder is per blok van 3x3 dezelfe voorwaarde, dus ook cijfer 1...9 en som van 45.

Als je begint met een spel, zijn sommige vakken al ingevuld. Om het op te lossen krijg je dus per vakje 3 vergelijking (rij, kolom en blok restricties). Dus in totaal 3*81 vergelijking met + en -, simpel dus.

Maar ik krijg het niet voor elkaar om dit met een programmeertaal, logisch op te lossen. De vraag is of het mogelijk is met C++ (borland C++ builder 6) om hier stesel van vergelijking op te lossen.

Het komt vaak zat voor dat er meerder oplossingen zijn, je variabelen zijn dus niet vast. Oftewel bijvoorbeeld:
x=6-y-z
y=6-x-z
z=6-x-y

Hier moet je eerst x,y of z als waarde kiezen voordat je een oplossing kan geven. Als ie zo is:
x=6-y-z
y=5-x
z=-y

heeft ie wel een oplossing.
En ik snap niet hoe je zoiets met c++ op kunt lossen.

[Henk007]

Het oplossen van een Sudoku grid is meer dan het oplossen van een stelsel lineaire vergelijkingen. Zie bijvoorbeeld deze link of deze
Voorbeelden van oplos software vind je o.a. hier of hier

[ Voor 19% gewijzigd door Henk007 op 02-10-2005 14:19 ]

[Mick]

Het makkelijkst is om een package te pakken dat stelsels (lineare) vergelijkingen m.b.v. matrixen oplost. Zie bijvoorbeeld http://math.nist.gov/lapack++/ of http://www.robertnz.net/nm_intro.htm

-edit- Ah, m'n bovenbuurman zegt iets soortgelijks.

[ Voor 18% gewijzigd door Mick op 02-10-2005 14:26 ]

[Zoijar]

Geheeltallige stelsels van vergelijkingen oplossen is ook niet zo'n simpel probleem iha Voor 9x9 is het goed te doen door het zelf gewoon op te lossen, en dan in te vullen. Je kan het niet rechtstreeks in C++ invoeren oid.

Zo'n vierkant kan je altijd maken door onder in het midden te beginnen, en dan steeds naar rechtsonder te stappen. Als je bij een rand komt doe je alsof de randen wrappen, dus van onder ga je naar boven, en rechter rand naar linker etc. Als er al een getal staat in het vakje, dan stap je naar het vakje boven het getal voor je vandaan komt getal. Deze procedure werkt altijd voor elk vierkant van oneven afmetingen, en de som van alle horizontale, verticale en diagonale lijnen zal hetzelfde zijn.

. . . . . 2 . . 2 4 . 2 4 . 2 4 . 2 4 . 2 4 . 2 4 9 2
. . . . . . 3 . . 3 . . 3 5 . 3 5 . 3 5 7 3 5 7 3 5 7
. 1 . . 1 . . 1 . . 1 . . 1 . . 1 6 . 1 6 8 1 6 8 1 6

[Creepy]

Je kan ook beginnen met het gewoon domweg invullen van de cijfers die je nog niet hebt in een 9x9 grid die je al hebt en controleren of het grid klopt. Zo niet, de cijfers op een andere manier invullen net zolang totdat het klopt (oko wel brute-force genoemd). Als je dat lukt zou je eens kunnen gaan kijken naar eventuele optimalisaties.

Overigens is er de laatste tijd redelijk wat informatie te vinden over de Sudoku puzzels. Als je "C++ sudoku" intikt in google dan vliegen de links je om de oren. Daar moet toch wel genoeg informatie uit te halen zijn lijkt me?

[Mick]

-edit- Foutje

[ Voor 107% gewijzigd door Mick op 02-10-2005 14:33 ]

[Ivo]

Ik heb zelf een programma in Pascal geschreven dat Sudoku's oplost. De gebruikte techniek is redelijk simpel. Je houdt per open vak bij wat de plaatsingsmogelijkheden zijn. Je kijkt dus per vak naar de rij, kolom en sector of je mogelijkheden weg kan halen, Als je nog 1 mogelijkheid over hebt dan weet je dat dat de juiste is en kun je hem plaatsen, waardoor je opnieuw kunt elimineren. Komt de eliminatieprocedure niet meer verder (hij vindt geen nieuwe waardes), dan gok je een vak waar je een minimaal aantal mogelijkheden hebt en dan elimineer je verder. Komt de puzzel niet uit dan ga je backtracken.

Edit: Ik heb de versie online staan, maar die klopt niet. Bij het porten van Delphi naar Pascal is er iets misgegaan, maar als je de code wil zien als voorbeeld dan kun je hem op mijn site vinden.

[ Voor 15% gewijzigd door Ivo op 02-10-2005 15:06 ]

[MSalters]

Lijkt me dat dit niets met C++ te maken heeft? TS heeft geen algoritme, en talen met de Just-Do-It-Dammit instructie zijn wat zeldzaam

[Soultaker]

Sudoku is een instantie van het puntkleuren van een graaf. Dat probleem is wel bekend uit de atlas: stel dat je een wereldkaart hebt, hoe kun je dan met zo min mogelijk kleuren elk land kleuren, maar wel zo dat twee aangrenzende landen niet dezelfde kleuren hebben.

Bij Sudoku zijn de negen 'kleuren' gegeven (de negen cijfers/symbolen/whatever) en de buren van elke cel zijn de cellen die in dezelfde rij, kolom of blok zitten. Efficiënte oplossingen zijn er in het algemeen niet, maar met een combinatie van back-tracking en enkele simpele afleidingsregels (zoals die Ivo al noemt) kun je elke bestaande Sudoku wel heel snel oplossen.

Verder: Sudoku Programmers.

[Robtimus]

Zoijar schreef op zondag 02 oktober 2005 @ 14:21:
Zo'n vierkant kan je altijd maken door onder in het midden te beginnen, en dan steeds naar rechtsonder te stappen. Als je bij een rand komt doe je alsof de randen wrappen, dus van onder ga je naar boven, en rechter rand naar linker etc. Als er al een getal staat in het vakje, dan stap je naar het vakje boven het getal voor je vandaan komt getal. Deze procedure werkt altijd voor elk vierkant van oneven afmetingen, en de som van alle horizontale, verticale en diagonale lijnen zal hetzelfde zijn.

Dat zijn magische vierkanten, waarbij in een vierkant van oneven afmetingen alle getallen van 1 t/m (rand*rand) eenmaal voorkomen en de sommaties over alle rijen en kolommen gelijk zijn.

Een Sudoku is GEEN magisch vierkant, want binnen elk vierkantje van 3x3 hoeven de sommaties over de rijen en kolommen niet gelijk te zijn. Voor een 3x3 vierkant zijn er nml maar 8 oplossingen: 1 initiele, 3 daarvan afgeleid door het een kwartslag te draaien, en deze 4 dan gespiegeld (over de horizontale, verticale of diagonale as maakt niet uit, door draaien krijg je dan toch dezelfde). Zou dan wel relatief gemakkelijk zijn, je hoeft alleen maar uit te vinden welke van de 8 je moet gebruiken. Zelfs brute force is voor Sudoku's dan "slechts" 8^9 pogingen.

[Paul]

Ivo schreef op zondag 02 oktober 2005 @ 15:04:
Ik heb zelf een programma in Pascal geschreven dat Sudoku's oplost. De gebruikte techniek is redelijk simpel. Je houdt per open vak bij wat de plaatsingsmogelijkheden zijn. Je kijkt dus per vak naar de rij, kolom en sector of je mogelijkheden weg kan halen, Als je nog 1 mogelijkheid over hebt dan weet je dat dat de juiste is en kun je hem plaatsen, waardoor je opnieuw kunt elimineren. Komt de eliminatieprocedure niet meer verder (hij vindt geen nieuwe waardes), dan gok je een vak waar je een minimaal aantal mogelijkheden hebt en dan elimineer je verder. Komt de puzzel niet uit dan ga je backtracken.

Edit: Ik heb de versie online staan, maar die klopt niet. Bij het porten van Delphi naar Pascal is er iets misgegaan, maar als je de code wil zien als voorbeeld dan kun je hem op mijn site vinden.

Elimineren van opties in 1 vakje is niet genoeg Je moet ook controleren of dat vakje het enige in de rij/kolom/sector is die $optie nog heeft

Of ja, moet, het kan iig, maar met gokken zal het ook wel lukken

Ik moet nu een soortgelijk ding (geen sudoka) maken voor school en ik heb (zonder te googlen, wil het zelf doen ) inderdaad al dat soort regeltjes verzonnen, nu nog even in C++ gieten...

[LinuX-TUX]

Ja, het is mogelijk om in C(++) op te lossen, want ik heb hem zelfs werkend gekregen in Excel

[Robtimus]

LinuX-TUX schreef op zondag 02 oktober 2005 @ 19:30:
Ja, het is mogelijk om in C(++) op te lossen, want ik heb hem zelfs werkend gekregen in Excel

offtopic:
Met zo'n naam nog met Excel werken? Dat kan niet hoor

Maar het is eerst zaak om een algemeen algoritme te vinden, dan kun je het daarna in vrijwel elke taal programmeren.

[elgringo]

Het oplossen heb ik aan de kant gelegd, daarvoor moet ik teveel berekening gaan doen die uiteindelijk niet veel sneller zijn.

Ik heb nu een bcb proggie die try en error doet, werk effiecient, maar ik vind hem persoonlijk wat traag. Duurt max 2 seconden (worst case senario, eigenlijk lost ie niets op, maar loopt ie alleen alle oplossingen af) voordat er een oplossing komt op mij athlon 3200+. Ik moet die code nog ff optimaliseren zodat ie wat rapper wordt, maar hij werkt wel.

[Grijze Vos]

IceManX schreef op zondag 02 oktober 2005 @ 19:55:
Maar het is eerst zaak om een algemeen algoritme te vinden, dan kun je het daarna in vrijwel elke taal programmeren.

[MSalters]

Zelf ook al over nagedacht, en in wezen is het vrij simpel. Je hebt 81 variabelen en 27 constraints. Elke variabele implementeer je als een int (intieel 0)+bitmask van 9 bits - zeker/mischien wel of zeker niet. Initieel heb je een paar begingetallen. Elk begingetal is dus een zeker-wel. Tegelijkertijd is het dus een zeker-niet voor de andere 8 bits van die variabele, en een enkele zeker-niet voor de variabelen die via een constraint zijn gekoppeld.

Vervolgens ga je recursief kijken of je een variabele hebt met momenteel oplossing 0, maar 8 bits zeker-niet. Je hebt dan een zeker-wel bit, en kunt de oplossing invullen. Net zoals met de begingetallen leidt dat tot meer zeker-niet bitten, die weer leiden tot een zeker-wel bit.

Pas als dit vastloopt kies je voor backtracking. Je kiest dan de variabele uit met het laagste aantal mogelijk-wel bits, en je probeert ze 1 voor 1. Eventueel kun je ook complexere (conditionele) constraints afleiden, maar dat is vergelijkbaar met het kiezen van een variabele met een laag aantal mogelijk-wel bits. Beide vinden snel tegenstrijdigheden.

[hammerhead]

MSalters schreef op woensdag 12 oktober 2005 @ 22:54:
Zelf ook al over nagedacht, en in wezen is het vrij simpel. Je hebt 81 variabelen en 27 constraints. Elke variabele implementeer je als een int (intieel 0)+bitmask van 9 bits - zeker/mischien wel of zeker niet. Initieel heb je een paar begingetallen. Elk begingetal is dus een zeker-wel. Tegelijkertijd is het dus een zeker-niet voor de andere 8 bits van die variabele, en een enkele zeker-niet voor de variabelen die via een constraint zijn gekoppeld.

Vervolgens ga je recursief kijken of je een variabele hebt met momenteel oplossing 0, maar 8 bits zeker-niet. Je hebt dan een zeker-wel bit, en kunt de oplossing invullen. Net zoals met de begingetallen leidt dat tot meer zeker-niet bitten, die weer leiden tot een zeker-wel bit.

Pas als dit vastloopt kies je voor backtracking. Je kiest dan de variabele uit met het laagste aantal mogelijk-wel bits, en je probeert ze 1 voor 1. Eventueel kun je ook complexere (conditionele) constraints afleiden, maar dat is vergelijkbaar met het kiezen van een variabele met een laag aantal mogelijk-wel bits. Beide vinden snel tegenstrijdigheden.

Ben er zelf ook mee bezig geweest. Is mijn eerste C++ programma geworden (hiervoor altijd in Java gewerkt). Het laatste wat jij zegt klopt helaas niet helemaal, het vinden van tegenstrijdigheden kan relatief best lang duren (het is en blijft gokken, en je kunt natuurlijk altijd verkeerd gokken).

Ik moet zeggen dat het toepassen van de logica van de sudoku's over het algemeen sneller werkt bij mij dan dat ik hem laat branchen op verschillende opties (overigens branch ik dan wel op het vakje met het kleinst overgebleven domein). Maar met mijn huidige regels hoef ik voor de standaard sudokus nooit te branchen. Er zijn er een aantal lastige waar ik wel voor moet branchen.

Heb van een colega een bestand gekregen van 24620 sudokus waar slechts 17 getallen zijn ingevuld (17 is het minimum bekend wat nodig is om een unieke oplossing te garanderen). Op computer hier (P4 3.2 GHz) doe ik daar 12.25 10.40 8.40 ( aantal van logische regels veranderd) seconden over. Misschien is er nog wat ruimte voor verbetering, maar dat moet ik nog even uitzoeken.

Maar in weze gebruikt mijn programma wel ongeveer dezelfde aanpak, alleen werk ik niet met recursie. Ik voer gewoon achter elkaar een set van logische regels uit, loop ik daarmee vast, branch ik en ga daarna weer door met logische regels op de subproblemen.

edit:
Tijden aangepast. Bleek dat het nog wat sneller kon

[ Voor 4% gewijzigd door hammerhead op 13-10-2005 11:19 ]

[Verwijderd]

Zelf ben ik hier ook mee bezig. Echter heb ik gekozen voor een hele andere taalkeuze.
Want wat is er nu handiger voor dit soort problemen dan het uiterst krachtige backwards chaining van PROLOG.

Een paar simpele definities maken en de rest doet PROLOG zelf.

Nog niet het feit meegerekend dat de lijst gevormd door het platslaan van de 3x3 vakjes ook een permutatie van de lijst 1-9 is, kom je in PROLOG met zoiets als dit al een heel eind

Prolog:

line(A) :- permutation([1, 2, 3, 4, 5, 6, 7, 8, 9], A).

field([]).
field([A | As]) :- line(A), field(As).

solve(A) :- field(A), transpose(A, B), field(B).

De rest van de vereiste eigenschappen zijn natuurlijk op een overeenkomstige manier te defineren. Het grote voordeel is dat PROLOG ook nog alle mogelijk puzzels voor je wil berekenen. (als je dat zou willen).

[schoene]

Hammerhead, zou je eens die file willen doormailen naar mij? Ik heb ook zo'n programma gemaakt in C++, en zou dat wel eens willen testen. mijn adres is schoene_rules AT yahoo.com thanks!

[hammerhead]

schoene schreef op donderdag 13 oktober 2005 @ 16:23:
Hammerhead, zou je eens die file willen doormailen naar mij? Ik heb ook zo'n programma gemaakt in C++, en zou dat wel eens willen testen. mijn adres is schoene_rules AT yahoo.com thanks!

Check je mail. Overigens heb ik de uitvoer van de oplossingen even uitgezet in mijn programma en dan los ik ze alle 24620 op in 7.8 seconden. Ben benieuwd of je eronder komt

[MSalters]

Ben ook benieuwd naar die file, msalters()xs4all.nl

[hammerhead]

Ik had hem van een collega van me gekregen. Ik wist niet waar hij hem vandaan had. Even gezocht op internet en het bestand is te vinden op http://www.csse.uwa.edu.au/~gordon/sudoku17.

[Verwijderd]

Hmm die file heeft alleen maar heel erg simpele puzzels, allemaal met het verwerken van naked en hidden singles op te lossen...

edit:
Niet dus, zat een foutje in de IsSolved functie

[ Voor 22% gewijzigd door Verwijderd op 16-10-2005 04:08 ]

[Verwijderd]

Populair ding, maar computationeel zijn ze helaas niet erg complex heb ik gemerkt. Een paar weken geleden heb ik me er ook aan gewaagd, zonder extra info van internet ofzo. Ik kwam op vrijwel hetzelfde uit als wat MSalters voorstelt:

MSalters schreef op woensdag 12 oktober 2005 @ 22:54:
Zelf ook al over nagedacht, en in wezen is het vrij simpel. Je hebt 81 variabelen en 27 constraints. Elke variabele implementeer je als een int (intieel 0)+bitmask van 9 bits - zeker/mischien wel of zeker niet. Initieel heb je een paar begingetallen. Elk begingetal is dus een zeker-wel.

Alleen heb ik gewoon de bitmask en de int samengevoegd, elke bitmask met 1 bit set heeft een bekende oplossing, een bitmask met 0 bits set betekent een tegenstrijdigheid, en dat je een bepaalde tak kunt afkappen. Mijn programma gaat dus iteratief "bits wegstrepen" totdat hij niet verder kan, en dan gaat hij recursief de mogelijkheid met het minst aantal "open bits" proberen. De implementatie is mogelijk niet zo efficient (hij zou iets eerder kunnen afkappen, en ik geloof dat het checken van een paar dingen efficienter moet kunnen), maar hij vindt de oplossing snel genoeg.

broncode voor de geinteresseerde: http://www.vizzzion.org/~luite/SudokuSolver.java.txt
(hopelijk min of meer bugvrij, ik heb het niet erg uitgebreid getest)