[AS Monthly] sudokuSolver

[Mr. Black]

AS Monthly - sudokuSolver

Sudoku (http://nl.wikipedia.org/wiki/Sudoku), het verslavende puzzeltje met 9 cijfers heeft inmiddels een belangrijke plek in ons leven ingenomen. Er zijn tientallen uitgevers met boekjes op verschillende niveau's, iedere krant heeft er tegenwoordig ook een. En zelfs een wereldkampioenschap Sudoku heeft al plaatsgevonden.

Maar wij als luie ActionScript-geeks hebben natuurlijk helemáál geen zin in al dat gedoe met die cijfertjes. Wij schrijven liever ons eigen programmatje hiervoor. Het zal voornamelijk om snelheid gaan. Als je alle opties gaat proberen zal je er uiteindelijk wel komen, maar niet erg snel: er immers zijn 6 670 903 752 021 072 936 960 verschillende opties mogelijk. Tweede probleem: krijg je dit in één maand ingevoerd :)?

Opdracht
Maak een applicatie die sudoku's op kan lossen van alle niveau's: dit betekent van een hele simpele tot 's werelds moeilijkste sudoku (http://frontpage.fok.nl/nieuws/70266). Ook geldt natuurlijk: hoe sneller, hoe beter. Alle applicaties worden na de deadline getest op 8 sudoku's. Deze sudoku's worden op deze manier aangeleverd (en worden van de website http://websudoku.com/ geplukt: 2 van elke categorie):

var sudoku:Array = [
[1, 2, 0, 4, 5, 6, 0, 8, 9],
[2, 3, 0, 5, 6, 7, 0, 9, 1],
[3, 4, 0, 6, 7, 8, 0, 1, 2],
[4, 5, 0, 7, 8, 9, 0, 2, 3],
[5, 6, 0, 8, 9, 1, 0, 3, 4],
[6, 7, 0, 9, 1, 2, 0, 4, 5],
[7, 8, 0, 1, 2, 3, 0, 5, 6],
[8, 9, 0, 2, 3, 4, 0, 6, 7],
[9, 1, 0, 3, 4, 5, 0, 7, 8]
];

Spreekt wel voorzich denk ik, 0 staat dus voor een leeg vakje (en moet dus gevuld worden).

Criteria

Alleen zelf gemaakte scripts mogen ingestuurd worden (en ga dus ook niet een sudokuSolver van internet halen en vervolgens overschrijven in ActionScript 3: kom echt met iets wat je zélf heb bedacht).
Alle ingezonden scripts zijn ActionScript 3.0.
De scripts worden na de deadline zeker vrij gegeven. Als je wilt mag dit natuurlijk vroeger.
(Ook vroege schetsen, UML diagrammen, en API's zijn leerrijk en dus zeker welkom, maar absoluut geen verplichting)
Er staat geen limiet op het aantal deelnames per persoon. Er zijn geen prijzen verbonden aan het al dan niet winnen, dus van extra deelnames kunnen we alleen bijleren. Maak dus gerust een tweede inzending, als je er tenminste de tijd ervoor hebt.
Samen aan een inzending werken mag, maar vermeld wel met wie je hebt samen gewerkt.
Na het verstrijken van de deadline kunnen alle leden stemmen op de inzending die zij het beste vinden. Wel vragen we om vooral te letten op de code en de creativiteit, en in mindere mate op het grafische gedeelte. Het is immers een AS monthly.


Duwtje in de goede richting
http://www.sudokusolver.co.uk/nl_index.html
http://nl.wikipedia.org/wiki/Oplossingsschema_Sudoku

Inzendingen
BernardV (http://www.debit.nl/sudoku/)
GBest (http://geert.utopiatemple.org/flash.php)

Deadline
Month betekent "maand" in het Engels dus:

23:59:59 op 28 september 2007


Happy Scripting! 8D

- Mr. Black

[Als iemand dit zelfde topic nog een keer opnieuw wil starten in het ActionScript 1 & 2 Forum kan dat gewoon: let wel even op dat je alle drieën in tweeën verandert]

[matzo]

Ik ben benieuwd om te zien hoe sommigen second tier logic gaan invoegen. :)
Je solver op verschillende niveau's testen, kun je door de dagelijkse sudoku van:
http://websudoku.com/(Hiermee worden ze getest na de deadline),
http://www.daily-sudoku-puzzle.com
of http://www.dailysudoku.co.uk/sudoku/
in het 2D array formaat in te voeren.

[BernardV]

Zal proberen vanavond nog een prototype te hebben draaien..

[BernardV]

Begin is er:
-------------
|504|080|009|
|080|000|003|
|001|902|008|
-------------
|000|500|900|
|000|324|000|
|005|008|000|
-------------
|100|709|300|
|900|000|020|
|400|060|701|
-------------
Found in (122 ms):
-------------
|524|683|179|
|689|417|253|
|371|952|468|
-------------
|813|576|942|
|796|324|815|
|245|198|637|
-------------
|152|749|386|
|967|831|524|
|438|265|791|
-------------

Voorbeeld array:
-------------
|120|456|089|
|230|567|091|
|340|678|012|
-------------
|450|789|023|
|560|891|034|
|670|912|045|
-------------
|780|123|056|
|890|234|067|
|910|345|078|
-------------
Found in (2 ms):
-------------
|127|456|389|
|238|567|491|
|349|678|512|
-------------
|451|789|623|
|562|891|734|
|673|912|845|
-------------
|784|123|956|
|895|234|167|
|916|345|278|
-------------

[fleasy]

Shit, nu al een werkend iets!? Ik ben nu bezig de flashCS3 trial te downloaden, voor AS3 :D Kan iemand mij vertellen of AS3 veel anders is als AS2? Ik zit nu namelijk wel allemaal dingen in m'n hoofd te bedenken, maar die zijn allemaal in AS2..:(

[BernardV]

AS2 en AS3 verschillen wel, maar alles wat je bedenkt voor AS2 kun je ook prima in AS3 uitvoeren.

[Mr. Black]

Shit, nu al een werkend iets!?
Nou nou, zo moeilijk is dat nou ook weer niet. Op de 2 sites staat nét niet hoe je het in ActionScript 3 moet zetten.
De uitdaging bij deze Monthly is om een manier te bedenken die in Flash/Flex minder tijd kost dan deze (de wegstreepmethode, die ik denk dat BernardV ook heeft gebruikt). Eentje die zo'n sudoku dus oplost in minder dat 122 ms.

@Fleasy: dat je met ActionScript 3 begint, goed! Maar om nou meteen met zo'n sudokuSolver te beginnen: pittig. Maar ja, niet geschoten is altijd mis hè.

@BernardV: vraagje: hoelang doet die van jou nou over 's werelds moeilijkste? Heb ik een beetje een idee van wat reeël is. :D

[M0L]

Begin is er:

Voorbeeld array:
-------------
|120|456|089|
|230|567|091|
|340|678|012|
-------------
|450|789|023|
|560|891|034|
|670|912|045|
-------------
|780|123|056|
|890|234|067|
|910|345|078|
-------------
Found in (2 ms):
-------------
|127|456|389|
|238|567|491|
|349|678|512|
-------------
|451|789|623|
|562|891|734|
|673|912|845|
-------------
|784|123|956|
|895|234|167|
|916|345|278|
-------------
Ik wil niet flauw doen maar die voorbeeld array klopt helemaal niks van!!! (Die kan sowieso niet!!)

[Flash Monk-ey!]

Ik wil niet flauw doen maar die voorbeeld array klopt helemaal niks van!!! (Die kan sowieso niet!!)
Inderdaad, er staan bijv. 2 negens en 2 enen in het block rechtsboven

Dit klinkt als een goed excuus om mn halfwerkende sudoku package ns af te stoffen :)

[BernardV]

Inderdaad, er staan bijv. 2 negens en 2 enen in het block rechtsboven

Dit klinkt als een goed excuus om mn halfwerkende sudoku package ns af te stoffen :)

Hehe, had ik niet gezien :)

[M0L]

Ik ben nu ook bezig, heb alleen strategie 1 toegepast en hij kan nu al simpele sudoku's oplossen in 5 ms. Maar moelijke doet ie nog niet, want daar heb je strategie 2 voor nodig

[BernardV]

http://www.debit.nl/sudoku/

Wereld moeilijkste in 1028ms.

Gewoon op een vak klikken en dan een getal invoeren, zodra je klaar bent op "SOLVE"
Bij het invoeren zit al een check of het mag, mag het niet wordt het getal niet geplaatst.

[BernardV]

Heb de code die ik heb gebruikt in de swf ook even omgezet naar een javascript.
Met dit script kun je makkelijk puzzels oplossen van: http://www.websudoku.com/
Het enige is dat je dan even naar http://show.websudoku.com/ moet gaan, anders wordt de puzzel in een frame geladen.

JS code (ook even als bijlage ivm eventuele spaties):
javascript:var sAr = [[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0]];for(var i=0;i<9;i++){for(var j=0;j<9;j++){var item = document.getElementById("f" + i + "" + j);sAr[i][j] = item.value==""?0:parseInt(item.value);}}if(solve(sAr,0,0)){for(v ar i=0;i<81;i++){var x = i%9;var y = Math.floor(i/9);var item = document.getElementById("f" + y + "" + x);item.value = sAr[y][x];}}function solve(items, i, j){if(i==9 && j==8) return true;if(i==9){i = 0;j++;}if(items[i][j] != 0){return solve(items, i+1, j);}for(var newValue = 10; newValue-- > 1 ;){if(itemCorrect(i, j, items, newValue)){items[i][j] = newValue;if(solve(items, i+1, j))return true;}}items[i][j] = 0;return false;}function itemCorrect(i, j, items, newValue){for(var k = 9 ; k-- > 0 ;){if(items[k][j] == newValue)return false;}for(var k = 9 ; k-- > 0 ;){if(items[i][k] == newValue)return false;}var r = Math.floor(i/3) * 3;var c = Math.floor(j/3) * 3;for(var k = 3+r; k-- > r ; ){for(var l = 3+c ; l-- > c ;){if(items[k][l] == newValue)return false;}}return true;} void(0);

Werkwijze (Alleen firefox getest, dus kan zijn dat andere browsers het niet doen):
1. Ga naar http://show.websudoku.com/
2. plak de javascriptcode in je adresbalk en druk op enter

Klaar ben je :)

[M0L]

Heb de code die ik heb gebruikt in de swf ook even omgezet naar een javascript.
Met dit script kun je makkelijk puzzels oplossen van: http://www.websudoku.com/
Het enige is dat je dan even naar http://show.websudoku.com/ moet gaan, anders wordt de puzzel in een frame geladen.

JS code (ook even als bijlage ivm eventuele spaties):
javascript:var sAr = [[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0]];for(var i=0;i<9;i++){for(var j=0;j<9;j++){var item = document.getElementById("f" + i + "" + j);sAr[i][j] = item.value==""?0:parseInt(item.value);}}if(solve(sAr,0,0)){for(v ar i=0;i<81;i++){var x = i%9;var y = Math.floor(i/9);var item = document.getElementById("f" + y + "" + x);item.value = sAr[y][x];}}function solve(items, i, j){if(i==9 && j==8) return true;if(i==9){i = 0;j++;}if(items[i][j] != 0){return solve(items, i+1, j);}for(var newValue = 10; newValue-- > 1 ;){if(itemCorrect(i, j, items, newValue)){items[i][j] = newValue;if(solve(items, i+1, j))return true;}}items[i][j] = 0;return false;}function itemCorrect(i, j, items, newValue){for(var k = 9 ; k-- > 0 ;){if(items[k][j] == newValue)return false;}for(var k = 9 ; k-- > 0 ;){if(items[i][k] == newValue)return false;}var r = Math.floor(i/3) * 3;var c = Math.floor(j/3) * 3;for(var k = 3+r; k-- > r ; ){for(var l = 3+c ; l-- > c ;){if(items[k][l] == newValue)return false;}}return true;} void(0);

Werkwijze (Alleen firefox getest, dus kan zijn dat andere browsers het niet doen):
1. Ga naar http://show.websudoku.com/
2. plak de javascriptcode in je adresbalk en druk op enter

Klaar ben je :)
Dat is wel leuk, tegen iemand zeggen dat je heel snel sudoku kan maken, als hij ff niet kijkt die code kopieren en klaar :D. Maar ik zie dat mijn methode echt achterhaald is :( , ik heb veel meer code. Ik heb gewoon de 2 oplostartegieen gebruikt. Maar werkt die van jou altijd?? Want hij vult gewoon een getal in die kan, als je dat zelf doet bij een sudoku komt het in de meeste gevallen toch niet uit, anders is een sudoku oplossen echt makkelijk toch???

EDIT: Ik heb er al één gevonden die niet werkt: Linkje (http://show.websudoku.com/?level=4&set_id=5337064484)

[BernardV]

Die doet het wel, alleen duurt wat langer ;)
Als je wilt kan ik wel een screenshot maken :)

Wat ik doe is backtracking, dus alle mogelijke getallen proberen totdat er een oplossing is.

//EDIT: Simpele uitleg van backtracking.

Ik plaats getal 2 in vak 0,0 dan plaats ik getal 3 in 0,1, die mag niet, dus ik plaats 4 die mag ook niet... 9 mag ook niet, dus 2 was niet goed. Ik hoog 2 op naar 3, dus op dat moment heeft 0,0 getal 3 als waarde en probeer ik weer 0,1 te vullen, lukt dat ga ik door naar 0,2 anders weer terug naar 0,0.
Dus zo probeer je alle mogelijkheden, maar niet door alles gelijk in te vullen. Je reageert dus op reacties van de volgende stap.

//EDIT2:
De AS code:
package nl.debit.sudoku
{

public class SudokuSolver
{

public function SudokuSolver()
{

}

public static function solve(items:Array, i:uint=0, j:uint=0):Boolean
{
if(i==9 && j==8) return true; //Alle items zijn doorlopen, dus aan het einde

if(i==9){ //Kolom is doorlopen, dus kolom counter weer op 0 en 1 bij de rij op
i = 0;
j++;
}

if(items[i][j] != 0) // Sla bestaande items over
{
return solve(items, i+1, j);
}

for(var newValue:uint = 10; newValue-- > 1 ;) // Probeer alle mogelijke waardes 9 t/m 1
{
if(itemCorrect(i, j, items, newValue)) //Check of de nieuwe waarde geplaatst mag worden
{
items[i][j] = newValue;
if(solve(items, i+1, j)) //Ga verder met oplossen vanaf de net geplaatste waarde
return true;
}
}
//Geen mogelijkheid gevonden, dus we zetten de waarde weer op 0 en laten de vorige aanroep weten dat het niet gelukt is
items[i][j] = 0;
return false;
}

private static function itemCorrect(i:uint, j:uint, items:Array, newValue:uint):Boolean
{
var k:uint, l:uint;

for(k = 9 ; k-- > 0 ;) //Staat de waarde al in de kolom, dan false
{
if(items[k][j] == newValue)
return false;
}

for(k = 9 ; k-- > 0 ;) //Staat de waarde al in de rij, dan false
{
if(items[i][k] == newValue)
return false;
}

var c:uint = Math.floor(i/3) * 3;// bv item 8 wordt 8/3 -> 2 * 3 = 6
var r:uint = Math.floor(j/3) * 3;

//Hier gaan we de groep bekijken 3*3
for(k = 3+c; k-- > c ; )
{

for(l = 3+r ; l-- > r ;)
{
if(items[k][l] == newValue) //Waarde staat in de groep, dus false
return false;
}
}

return true; //Geen kolom, rij of groep waar de waarde bestaat, dus het mag
}
}
}

Gebruik zo:
SudokuSolver.solve(__sudokuArray);
Waarbij de array de opmaak heeft zoals hier is aangegeven.

[matzo]

Knap werk BernardV, het wordt moeilijk om dat te overtreffen vrees ik? :)

[Ruben!]

Jemig, wat is die Bernard slim!
Zo weinig en overzichtelijke code, met zo'n goed resultaat:) ++
"Bernard heeft gewonnen, volgende monthly! (daily)"

[fleasy]

Ik ben er ook nog ( niet dat mij het zal lukken, heb nog nooit met AS3 gewerkt.. maar toch :D )

[M0L]

Maar wat ik niet snap is het volgende:
Als hij in elke vakje een willekeurig getal invoert (die wel voldoet aan de regels). Dat kan het toch zijn dat je niet uitkomt, toch? Wat doet je code dan? Want vaak is er maar één oplossing mogelijk terwijl op het begin meerdere waardes mogelijk zijn om in te vullen.

[BernardV]

Maar wat ik niet snap is het volgende:
Als hij in elke vakje een willekeurig getal invoert (die wel voldoet aan de regels). Dat kan het toch zijn dat je niet uitkomt, toch? Wat doet je code dan? Want vaak is er maar één oplossing mogelijk terwijl op het begin meerdere waardes mogelijk zijn om in te vullen.

Dat klopt, alleen deze code werkt zo:
Als er in alle vakjes een getal staat en het laatste vakje kan niet gevult worden, dan gaat de code 1 vakje terug en en probeert daar de volgende waarde en gaat dan weer verder..

Simpele illustratie:

1->2->3->4->5->6->7 (als 7 niet kan):
1->2->3->4->5->6->8 (als 8 niet kan):
1->2->3->4->5->6->9 (als 9 niet kan):
1->2->3->4->5->7->6 ....

Deze code is alleen dan nog zo dat het ook alle getallen 1-9 probeert.. ipv de rest van de rij, dit ook omdat het opslaan en bijhouden van rijen meer tijd kost dan het proberen van slechts 10 getallen.

[M0L]

Maar is deze techniek is dan toch alleen sneller bij simpel sudoku's, want bij moeilijker zal die heel vaak en getal terug moet gaan of zelfs meerdere.
Volgens mij is er dan nog hoop voor mijn techniek (hoop ik)

Maar deze techniek is iig veel simpeler en werkt altijd. Het is eigenlijk een soort Brute-force

En 's werelds moeilijkste sudoku, welke is dat precies en hoe lang doet die van jou daarover? Dan heb ik ook wat vergelijkijngs materiaal

[BernardV]

Wereld moeilijkste ongeveer 1 seconde op mijn PC.
Je kunt het wel testen in de online versie door het in te voeren.
Deze werkt inderdaad altijd, maar maakt weinig verschil tussen moeilijk en makkelijk het is net hoe de getallen verdeelt zijn. Deze begint altijd bij 9 t/m 1, dus als de eerste getallen hoog zijn is het resultaat snel, maar als getal 1 wat de code plaatst ook 1 moet zijn betekend dat dat het dus 9 t/m 1 gaat proberen voor alle andere vakken.

//EDIT:
Heb het ook wel geprobeerd met linked lists en de mogelijke waardes wegstrepen e.d.
Alleen toen bedacht ik me dat dit veel sneller te programmeren is.
Het is wel zo dat het wegstrepen van mogelijke waardes ervoor zocht dat er minder itteraties nodig zijn.
Je zou ook een combinatie kunnen maken met ipv de for loop een newValue = item[i][j].getNextPossibleValue() of iets dergelijks. Of dat sneller is, denk het niet, maar wie weet...

[M0L]

Je hebt gelijk dat zou idd niet veel uitmaken er van uitgaande dat ze allebei 1 oplossing hebben. Alleen zij bij de makkeijke meestal meer getallen gegeven. Maar is de techniek, die ik gebruik (dus gebruik van strategieen, die je normaal gebruikt om hem oplossen) per definitie langzamer?

Ik ga iig mijn script afmaken en daarna optimaliseren en dan zien we het wel.

[matzo]

De moeilijkste sudoku in 2d formaat:

var sudoku:Array = [
[1,0,0,0,0,7,0,9,0],
[0,3,0,0,2,0,0,0,8],
[0,0,9,6,0,0,5,0,0],
[0,0,5,3,0,0,9,0,0],
[0,1,0,0,8,0,0,0,2],
[6,0,0,0,0,4,0,0,0],
[3,0,0,0,0,0,0,1,0],
[0,4,0,0,0,0,0,0,7],
[0,0,7,0,0,0,3,0,0]
];

[BernardV]

Je hebt gelijk dat zou idd niet veel uitmaken er van uitgaande dat ze allebei 1 oplossing hebben. Alleen zij bij de makkeijke meestal meer getallen gegeven. Maar is de techniek, die ik gebruik (dus gebruik van strategieen, die je normaal gebruikt om hem oplossen) per definitie langzamer?

Ik ga iig mijn script afmaken en daarna optimaliseren en dan zien we het wel.

Ik zeg niet dat het per definitie langzamer is, dat hoeft helemaal niet eigenlijk!
Het is wel zo dat je bij die benadering veel meer berekeningen doet voordat je een getal plaatst, maar daar in tegen plaats ik veel onnodige getallen.

Ik denk eigenlijk dat een combinatie van die 2 het beste werkt, want alles met regels doen is bijna onmogelijk, aangezien er dan ook een punt is waar je moet gaan gokken, of je moet al 10 stappen vooruit gaan rekenen.

Dus misschien invullen volgens de regels en wat er dan nog openstaat in deze code gooien, immers slaat deze code alle bestaande getallen over, dus vult het de rest.
Ik denk dat je op die manier het optimale resultaat kunt halen.

[BernardV]

Heb wereld moeilijkste (Array van Matzo) even als default waarde ingevoerd op http://www.debit.nl/sudoku/

[matzo]

Bij mij blijft hij het doen in slechts 667 ms, dus bedoel jij in 1 seconde of binnen de seconde BernardV?
Er zijn btw meer oplossingen mogelijk voor die sudoku volgens FOK:). (wat er eigenlijk voor zorgt dat het geen sudoku meer zou zijn, al wil ik eerst zien en dan geloven. En ik heb nog niet de oplossingen in de fok comments nagekeken:))

[BernardV]

Bij mij blijft hij het doen in slechts 667 ms, dus bedoel jij in 1 seconde of binnen de seconde BernardV?
Er zijn btw meer oplossingen mogelijk voor die sudoku:). (wat er eigenlijk voor zorgt dat het geen sudoku is:))

1 in seconde ;) Denk dat je PC sneller is :P Hier heb ik een P4 3.2 HT met FireFox, IE doet het in 835ms.

Klopt dat er meerdere mogelijkheden zijn (wat ik heb gelezen), zou ze wel allemaal kunnen uitrekenen maar waarom zou je... Om dat te doen is het bij de if(i==9 && j==8 ) even de items array op te slaan en een return false te doen. Dan gaat de code weer terug opzoek naar een volgende oplossing ipv te stoppen.

[matzo]

Nou, de 'andere' oplossingen in fok zijn in ieder geval FOUT!:)
Alleen degene die jou ook geeft is precies niet fout:);)B

BTW: intel centrino duo T2400 hier.

[Mr. Black]

Toch brute force BernardV? Gaat nog verassend snel dan (of is die op http://www.sudokusolver.co.uk nou zo langzaam?)

Ook moeten strakt alle solvers vanaf één computer allemaal onder dezelfde omstandigheden worden getest: anders is het natuurlijk niet eerlijk. Als het nu al 200 ms kan schelen... ;)

[M0L]

Ik heb ook al iets, zal het wel een keer laten zien.
Hij kan nu de makkelijke en normale oplossen in ongeveer 8 ms, de moeilijke nog helemaal niet :P

Ik doe geen brute-force, maar gewoon de strategieën toepassen die je zelf ook gebruikt.
Zo zou je dus ook een knop hint kun maken en als je daar dan op klikt dat het vakje, die je kunt invullen, begint te knipperen. En dat kan bij brute-force niet, marja dat is de opdracht ook niet :P

Wat ook leuk was geweest als contest, een sudoku-generator, die op niveau sudoku's kan genereren. ;)

[matzo]

Behalve dan dat er geen echte manier is om het 'niveau' van een sudoku te bepalen, tenzij héél je heel subjectief wilt gaan spelen:P

Ik heb al een paar redelijk concrete ideeën, maar nog geen regel code:P. Nu ja, deadline is nog ver genoeg:)

[Mr. Black]

Zelf ben ik op een héle andere manier bezig dan de wegstreepmethode. Geen brute force, gewoon met kennis.
Als ik een code schrijf over iets dat een mens normaal oplost, ga ik het ook doen zoals de mens denkt (alleen dan sneller). De hersenen zijn immers altijd (nog?) beter en complexer dan zo'n computer. Ja, een computer kan sneller rekenen. Maar dat laat ik dan ook aan de computer over.

Ik weet niet of het ook uiteindelijk snel zal zijn, dat zien we dan wel weer :D.

[BernardV]

Backtracking is niet echt brute force, je elimineert een groot deel van de mogelijkheden.
Het is een gevorderde brute force om het maar zo te zeggen.
Wat meer info: http://en.wikipedia.org/wiki/Backtracking

[Mr. Black]

Interessant :)! Ik dacht dat je dat woordje gewoon zelf had verzonnen.

De eerste proefversie van mij is ook klaar, misschien dat ik 'em morgen wel online zet zodat jullie kunnen testen etc.

[BernardV]

Heb even een kleine update gedaan op http://www.debit.nl/sudoku/

De update is dat ik nu een array maak met mogelijke waardes voor elke positie door de regel toe te passen of het ook in de rij, kolom of het blok voorkomt.

Bij mij scheelt deze update ongeveer 400ms op wereld moeilijkste, nu : "Found in 587 ms"

[GBest]

Ik heb ook even mijn kennis erop losgelaten. Ik gebruik een semi slimme oplosser die slechts 1 zet vooruit kan denken en een domme gok doet (namelijk het eerste element het laagst mogelijke getal). Verder crashed ie als er geen oplossing is, maar hij is vooral snel. In de Compile mode krijg ik de volgende resultaten:

// een andere sudoku geleverd door BernardV
final!
5 2 4 6 8 3 1 7 9
6 8 9 4 1 7 2 5 3
3 7 1 9 5 2 4 6 8
8 1 3 5 7 6 9 4 2
7 9 6 3 2 4 8 1 5
2 4 5 1 9 8 6 3 7
1 5 2 7 4 9 3 8 6
9 6 7 8 3 1 5 2 4
4 3 8 2 6 5 7 9 1
no. of guesses: 3
it took 19ms

// Eerste sudoku die ook in de main page staat (hij heeft eigenlijk geen oplossing, maar goed...
final!
1 2 7 4 5 6 3 8 9
2 3 8 5 6 7 4 9 1
3 4 9 6 7 8 5 1 2
4 5 1 7 8 9 6 2 3
5 6 2 8 9 1 7 3 4
6 7 3 9 1 2 8 4 5
7 8 4 1 2 3 9 5 6
8 9 5 2 3 4 1 6 7
9 1 6 3 4 5 2 7 8
no. of guesses: 2
it took 3ms

// Zogenaamd de moeilijkste sudoku ter wereld...
final!
1 6 2 8 5 7 4 9 3
5 3 4 1 2 9 6 7 8
7 8 9 6 4 3 5 2 1
4 7 5 3 1 2 9 8 6
9 1 3 5 8 6 7 4 2
6 2 8 7 9 4 1 3 5
3 5 6 4 7 8 2 1 9
2 4 1 9 3 5 8 6 7
8 9 7 2 6 1 3 5 4
no. of guesses: 86
it took 316ms

Ter referentie: bij mij doet de sudoku oplosser van BernardV in de FF browser er 490 ms over om de 'zogenaamd moeilijkste sudoku ter wereld' op te lossen.

Binnenkort kun je een web versie verwachten ;)

Groeten,

Geert

[BernardV]

Netjes Geert! Ben benieuwd naar de code :)

[GBest]

Ik heb net wat andere moeilijke sudokus gevonden: van dezelfde finse man:

http://www.usatoday.com/news/offbeat/2006-11-06-sudoku_x.htm

of in 2d array formaat:
var puzzle7:Array = [
[8,5,0,0,0,2,4,0,0],
[7,2,0,0,0,0,0,0,9],
[0,0,4,0,0,0,0,0,0],
[0,0,0,1,0,7,0,0,2],
[3,0,5,0,0,0,9,0,0],
[0,4,0,0,0,0,0,0,0],
[0,0,0,0,8,0,0,7,0],
[0,1,7,0,0,0,0,0,0],
[0,0,0,0,3,6,0,4,0]];

ik deed er 10174ms ter referentie: bernardV deed er slechts 473 ms over... :( Andere techiek leidt tot andere resultaten ;)

[BernardV]

Ik neem eigenlijk ook een wilde gok door voor het eerste item de meest hoge waarde (9) te nemen als dat niet kan 8 etc.. ik denk ook dat er weinig sudokus te vinden zijn die boven de 500ms komen (op jouw pc dan), immers duurt het alleen langer als er minder velden zijn ingevuld en de eerste velden laag zijn.
Maar toch ben ik nog steeds benieuwd naar je code :) Want ik denk dat een combinatie van code altijd nog de beste oplossing levert, net als de eerste check die ik heb toegevoegd wat op mijn PC toch 400ms scheelt.

//EDIT:
Mocht je een webversie maken, ik doe de timing op de berekeningen niet op het weergeven van de items. een getTimer() zodra ik op solve klik en als de functie klaar is weer.. dan pas plaats ik de items in het veld. Dit omdat het toch om de berekening gaat. Daar kan natuurlijk ook nog een verschil zitten.

[GBest]

Zo, ik heb ook een omhulsel geplaatst rondom de solver. Je kan hem alhier testen:
http://geert.utopiatemple.org/flash.php

Moet ik de code nu al kenbaar maken? Ik wil toch wel graag de code geheim houden... :$.

Een sudoku die de jouwe niet kon oplossen, maar de mijne wel:

[0,0,7,6,0,0,0,0,0],
[0,0,0,0,0,0,1,0,0],
[0,0,0,1,0,3,0,0,6],
[0,8,0,3,9,0,0,7,5],
[0,7,3,0,1,0,0,2,0],
[5,0,0,4,0,0,0,1,0],
[3,0,0,0,0,4,0,0,7],
[0,0,0,5,0,0,2,0,0],
[8,9,0,0,0,0,0,0,3]

De solver zal wel hangen als het niet mogelijk is om een sudoku op te lossen btw... ;)

En de tijd wordt berekend alleen overde solve en dan ook het echte solven. Ik zet de 2d array om in een 1d array, ook die omzetting zit bij de tijd. Het schrijven van en naar de textveldjes zijn niet meegeteld

Veel plezier ermee!

Gr.

Geert

[BernardV]

Kun je me eens de oplossing sturen of hier poste van die sudoku? Ik kan best een fout hebben gemaakt, maar aangezien deze code alle mogelijke combinaties test ben ik wel benieuwd :)

[BernardV]

Ik heb even een update doorgevoerd in de online versie (http://www.debit.nl/sudoku/) geen echt code wijzigingen, alleen de uint's vervangen door int's en dat scheelt een hoop!

int's zijn sneller dan uint's. Nu op mijn PC ongeveer 300ms voor wereld moeilijkste.

//EDIT: Iets andere insteek (http://www.debit.nl/sudoku2/)
- 1D Array
- bitwise functies voor het checken van rijen, kolommen en blokken

[GBest]

grapjas, zijn uints langzamer dan ints, Ik probeer het meteen!

BTW, ik heb wat problemen met mijn nieuwste solver. Als ik klaar ben zal ik wel delen van de broncode vrijgeven.

[GBest]

zo, ik heb mijn sudoku Solver versie 2 af. Je kan hem alweer hier vinden:

http://geert.utopiatemple.org/flash.php

De methode: Men begint met een 1D array met 81 elementen. Elk element komt overeen met een vakje in de Sudoku. In elk element wordt een array toegevoegd die uit 9 velden bestaat die allen op true staan (dit zijn de mogelijkheden). Verder wordt er een omrekentabel gemaakt van element => rij, kolom, block en rij[i], kolom[i], block[i] => element.

Als de puzzle geladen wordt, worden de juiste elementen in de 1D array gevuld met een volledige false array, en vervolgens wordt het juiste getal op true gezet. Dit is de initialisatie

Daarna Begint het echte solven. We gaan van element 1 => 81 en kijken voor elk element of er maar 1 oplossing in zit. Zo ja, streep alle getallen in weg in de rij, kolom en block. En doe dit recursief.

Na 1x van 1=>81 te hebben gelopen hebben we alle mogleijkheden weggestreept (want recursief) en wordt er gekeken of alle elementen 1 waarde hebben. Zo niet, dan doen we een gok (Een goede gok is erg belangrijk voor de snelheid van je sovler!!). En rekenen we verder. Als de gok fout was, gaan we een stapje terug en zetten we de gok op false. Dit herhaald zich totdat het antwoord is gevonden.

Echte snelheidswinst heb ik behaald met het recursief vegen van mijn 1D array (30% sneller). Door de juiste gok te doen kan 60% een snellere oplossing vinden.
Verder is het samenvoegen van loops ook vrij effectief en leverd een 10% snelheidswinst op.

Het veranderen van alle uints => ints had niet erg veel invloed... hoogstens 1 ms op elke berekening. Ik heb dit dan ook niet gedaan.

Even wat voorbeelden:

FF 's werelds moeilijkste
[1,0,0,0,0,7,0,9,0],
[0,3,0,0,2,0,0,0,8],
[0,0,9,6,0,0,5,0,0],
[0,0,5,3,0,0,9,0,0],
[0,1,0,0,8,0,0,0,2],
[6,0,0,0,0,4,0,0,0],
[3,0,0,0,0,0,0,1,0],
[0,4,0,0,0,0,0,0,7],
[0,0,7,0,0,0,3,0,0]
Versie staat voor solver versie
versie 0: 316 ms
versie 1: 47 ms
versie 2: 16 ms

Maar daar had ik natuurlijk al vanaf het begin geluk mee

Dan die andere ontzettend lastige
[8,5,0,0,0,2,4,0,0],
[7,2,0,0,0,0,0,0,9],
[0,0,4,0,0,0,0,0,0],
[0,0,0,1,0,7,0,0,2],
[3,0,5,0,0,0,9,0,0],
[0,4,0,0,0,0,0,0,0],
[0,0,0,0,8,0,0,7,0],
[0,1,7,0,0,0,0,0,0],
[0,0,0,0,3,6,0,4,0]
Versie staat voor solver versie
versie 0: 10174 ms
versie 1: 766 ms
versie 2: 150 ms


Nog een tricky puzzle:
[0,0,7,6,0,0,0,0,0],
[0,0,0,0,0,0,1,0,0],
[0,0,0,1,0,3,0,0,6],
[0,8,0,3,9,0,0,7,5],
[0,7,3,0,1,0,0,2,0],
[5,0,0,4,0,0,0,1,0],
[3,0,0,0,0,4,0,0,7],
[0,0,0,5,0,0,2,0,0],
[8,9,0,0,0,0,0,0,3]
Versie staat voor solver versie
versie 0: ? ms
versie 1: 138 ms
versie 2: 9 ms

Dat was het. Ik zal te zijner tijd, als ik me daar gelukkig mee voel, de broncode vrijgeven, maar jullie moeten nog eventjes wachten :P

[BernardV]

Code van de nieuwe versie.
Aanroep SudokuSolver.solve(2dArray); en dan krijg je als returnwaarde een 1d array met de oplossing of null als er geen oplossing is.

package nl.debit.sudoku
{
public class SudokuSolver
{
private static var __items:Array;
private static var __row:Array;
private static var __col:Array;
private static var __block:Array;

private static var __possibleValues:Array;

public static function reset():void
{
__items = new Array(81);
for(var i:int=0;i<81;i++)
__items[i]=0

__row = [0,0,0,0,0,0,0,0,0];
__col = [0,0,0,0,0,0,0,0,0];
__block = [0,0,0,0,0,0,0,0,0];
__possibleValues = [];
}

private static function generatePossibleValues():void
{
for(var i:int=0;i<81;i++)
if(__items[i]==0)
for(var k:int=1;k<10;k++)
if(itemCorrect(i,k))
__possibleValues[i] |= (1<<k);
}

public static function solve(ar:Array):Array
{
reset();

ar = ar.toString().split(",");

for(var i:int=0;i<81;i++)
if(ar[i]!=0)
setValue(i,ar[i]);

generatePossibleValues();

if(_solve())
return __items;
else
return null;
}

private static function setValue(i:int, newValue:int):Boolean
{
var r:int = i%9;
if((__row[r] & (1<<newValue))) return false;
var c:int = i/9;
if((__col[c] & (1<<newValue))) return false;
var b:int = int(r / 3) * 3 + int(c / 3);
if((__block[b] & (1<<newValue))) return false;

__row[r] |= (1<<newValue);
__col[c] |= (1<<newValue);
__block[b] |= (1<<newValue);
__items[i] = newValue;

return true;

}

private static function removeValue(i:int):void
{
var oldValue:int = __items[i];

var r:int = i%9;
var c:int = i/9;
var b:int = int(r / 3) * 3 + int(c / 3);

__row[r] ^= (1<<oldValue);
__col[c] ^= (1<<oldValue);
__block[b] ^= (1<<oldValue);
__items[i] = 0;
}

private static function _solve(i:int=0):Boolean
{
if(i==81) return true;

if(__items[i] != 0)
return _solve(i+1);

var k:int = 10;

for(;k-->1;)
if((__possibleValues[i] & (1<<k)))
if(setValue(i, k))
{
if(_solve(i+1))
return true;

removeValue(i);
}
return false;
}

private static function itemCorrect(i:int, newValue:int):Boolean
{
var r:int = i%9;
if((__row[r] & (1<<newValue))) return false;
var c:int = i/9;
if((__col[c] & (1<<newValue))) return false;
var b:int = int(r / 3) * 3 + int(c / 3);
if((__block[b] & (1<<newValue))) return false;

return true;
}
}
}

//EDIT: Moet er wel bij zeggen dat ik enige inspiratie heb gehad van een C versie van een sudoku solver die met linked lists werkte en ook bits gebruikte voor de mogelijke waardes.

[GBest]

Je behaalt nette resultaten met die solver. Bitwise werken is idd een goed idee. btw, is het niet 'sneller' om van tevoren een array te maken die dient als koppeltabel tussen elementen en rijen/kolommen/blokken.

var r:int = i%9;
if((__row[r] & (1<<newValue))) return false;
var c:int = i/9;
if((__col[c] & (1<<newValue))) return false;
var b:int = int(r / 3) * 3 + int(c / 3);


Mijn nieuwste solver (versie 3) lijkt uitgeoptimaliseerd. je kan hem vindien alhier: http://geert.utopiatemple.org/flash.php . Je hebt nu twee opties in de onderste checkbox. In principe zoek ik een slimme gok, maar ik kan de eerste pakken, of de laatste. Met "alternate solving" uit pak je simpelweg het eerste veld wat je tegenkomt. Met "alternate zolving" aan pak je om en om de eerste of laatste element om mee te solven. Ik weet nog niet wat 'slimmer' is, dus staan ze er beiden in.

Broncode wacht ik nog even lekker mee :P

BTW, de prestatie van de verschillende solvers zijn nogal afhankelijk van de puzzels die gebruikt worden. Ik stel dan ook voor om wat meer gewicht te leggen op de moeilijkere puzzels. Misschien kan het volgende worden gebruikt:
easy: 1 puzzle (<= hierop krijg je hoogstens 1 of 2 ms verschil)
medium: 2 puzzles (<= verschillen lopen op tot 5 ms)
hard: 3 puzzles (<= soms een heavy 20 ms verschil)
evil: 4 puzzles (<= hier heb je de echte leuke puzzels, verschillen tot 200 ms+)

[BernardV]

Die koppeltabel is geen gek idee, immers is deze al van te voren aan te maken.
Daarbij is het verschil in oplossen ook erg afhankelijk van het genereren van de mogelijke waardes (bij mij dan).
Stel je vervangt in de functie generatePossibleValues de loop (k) door een loop die van 9 naar 1 loopt zijn er puzzels die er langer over doen, maar anderen los je weer sneller op.

[GBest]

Het gaat hard vooruit met alle tijden. Toen ik zag dat bitwise operatoren zo goed werken heb ik dit ook toegepast in mijn solver. Dat scheelt een factor 3. De nieuwste versie is te vinden op http://geert.utopiatemple.org/flash.php , net zoals vorige versies. Vooral als je de de puzzle "2006 Hardest" laad is het mooi om te zien dat de tijden zo hard terug lopen.

Bernard, heb je veel tijdswinst behaald met het gebruiken van een koppeltabel?

[BernardV]

Het gaat hard vooruit met alle tijden. Toen ik zag dat bitwise operatoren zo goed werken heb ik dit ook toegepast in mijn solver. Dat scheelt een factor 3. De nieuwste versie is te vinden op http://geert.utopiatemple.org/flash.php , net zoals vorige versies. Vooral als je de de puzzle "2006 Hardest" laad is het mooi om te zien dat de tijden zo hard terug lopen.

Bernard, heb je veel tijdswinst behaald met het gebruiken van een koppeltabel?

Nice! :)
Met de koppeltabel heb ik nog niet geprobeerd, komt nog wel...

[Mr. Black]

Wat dood hier. Nog 4 dagen tot de deadline!

Heeft er (naast BernardV en GBest) nog iemand iets af? Anders wordt het niet echt spannend...

[GBest]

Hoi Flashfocussers,

Bij deze lever ik mijn oplossing in voor de FF AS Monthly. Ik heb er niet veel meer aan veranderd sinds de laatste keer, maar hoop toch dat hij de concurentie aankan.

Groeten,

Geert

PS: De code wordt dan nu toch maar uiteindelijk gepost, er zit wat rudimentaire data tussen...:


package sudoku
{
import flash.utils.getTimer;

public class SudokuPuzzle4
{
// the sudoku is declared
private var __puzzle:Array = new Array(9);
private var puzzleReal:Array = new Array(81);
private var puzzleSolve:Array = new Array();

private var puzzleStart:Array = new Array(81);


// the next are just reference arrays
private var rows:Array = new Array(9);
private var cols:Array = new Array(9);
private var blocks:Array = new Array(9);
private var koppelTabel:Array = new Array();

private var guess:uint;
private var guessed:Array = new Array(); // this array holds what has been guessed
private var possibleGuesses:int;//Array;
private var possibleGuessEl:int;
private var possibleGuessPoss:uint;
private var totalGuess:uint;

private var solved:Boolean;
private var stopIt:Boolean;

private var elStack:Array;






// constructor
public function SudokuPuzzle4():void
{
// initialize the sudoku constants
init();
}

private function init():void
{
guess = 0;
puzzleSolve[guess] = new Array(81);

// initialize the rows, cols and blocks array. These arrays contain the coordinates of the several blocks, rows, etc.
for (var i:uint=0; i<9; i++)
{
rows[i] = new Array(9);
cols[i] = new Array(9);
blocks[i] = new Array(9);
__puzzle[i] = new Array(9);
for (var j:uint = 0; j<9; j++)
{
rows[i][j] = i*9+j
cols[i][j] = j*9+i;
blocks[i][j] = (Math.floor(i/3)*3+Math.floor(j/3))*9+((i%3)*3+j%3);
puzzleStart[i*9+j] = 511;
puzzleSolve[guess][i*9+j] = 0;
}
}

for (i=0;i<81;i++)
{
koppelTabel[i] = [Math.floor(i/9),i%9, Math.floor(i/27)*3+Math.floor((i%9)/3)];
}
}


internal function solve(puzzleF:Array):uint
{
// start with timing
var startTime:uint = getTimer();
var endTime:uint;

// declaring
var getal:int;
var getalGuess:int;
var el:uint;
var didAGuess:Boolean;
var refElStack:Array = new Array();

var i:uint;
var j:uint;



/********************************************/
/* */
/* Initialisation */
/* */
/********************************************/
solved = false;
stopIt = false;

guess = 0;
totalGuess = 0;
guessed = new Array();
puzzleSolve = new Array();

__puzzle = new Array(9);
for (i = 0; i<9; i++) __puzzle[i] = puzzleF[i].slice(0,9);


puzzleSolve[0] = puzzleStart.slice(0,81);
elStack = new Array(1);
elStack[0] = new Array();


// and lets fill in the starting array in a way WE like.
for (i = 0; i<9; i++)
{
for (j=0; j<9; j++)
{

// first initialize the puzzle we had in a first run
if (__puzzle[i][j] !== 0)
{
el = 9*i+j;
getal = __puzzle[i][j];
puzzleSolve[0][el] = 0;
puzzleSolve[0][el] = 1<<(getal-1);
// remember what elements are set
refElStack.push(el);
}
}
}


/********************************************/
/* */
/* First Run */
/* */
/********************************************/
// first try to solve it with rows and columns elimination
possibleGuessPoss = 10;
possibleGuessEl = 81;
for (i=0; i< refElStack.length;i++) checkCrissCross(refElStack[i]);


/********************************************/
/* */
/* Guessing parts */
/* */
/********************************************/
while (!solved)
{




/********************************************/
/* */
/* Undo a guess */
/* */
/********************************************/
if (stopIt)
{
// oops, wrong guess, restore the last guess
do
{
// find the element and number we guessed
el = guessed[guessed.length - 1][0];
getal = guessed[guessed.length - 1][1];

guessed.pop();
puzzleSolve.pop();
elStack.pop();
guess--;

// trek 'getal' van puzzleSolve[guess][el] af.
puzzleSolve[guess][el] &= ~getal;
} while (puzzleSolve[guess][el] == 0);
stopIt = false;
}


/********************************************/
/* */
/* Make a 'smart' guess */
/* */
/********************************************/
// next try to solve it by an educated guess
else
{

guess++;
totalGuess++;
elStack[guess] = elStack[guess-1].slice();
puzzleSolve[guess] = puzzleSolve[guess - 1].slice(0,81);


el = possibleGuessEl;
getal = puzzleSolve[guess][el];
if (possibleGuessPoss == 10)
{
// aaargh!, we need to find a stupid element fast! Luckily this does not happen so much
didAGuess = false;
for (i = 0; i<81 && !didAGuess; i++)
{
getal = puzzleSolve[guess][i];
if (getal > 0 && (getal & (getal - 1)) > 0)
{
el = i;
didAGuess = true;
}
}
}
// find the next power of two (starting from 0)
for(i=0;i<9 && (getal & 1<<i) == 0;i++);
getal = Math.pow(2,i);

// this is the one we're going to try!
guessed.push([el,getal]);
puzzleSolve[guess][el] = getal;
}


/********************************************/
/* */
/* Solve it the criss cross way! */
/* */
/********************************************/
possibleGuessPoss = 10;
checkCrissCross(el);
}
// We cheat here a little bit by placing the end right after the solving, but we haven't converted yet to a 2D array.... There was no rule on this... It saves us 1 ms!
endTime = getTimer();

/********************************************/
/* */
/* We did it again! */
/* */
/********************************************/
trace("final!");
displayPuzzle(puzzleSolve);
trace("could be done in "+guess+" guesses");
trace("no. of guesses: "+totalGuess);
// end timing

trace("Time: "+(endTime - startTime)+"ms");
// check if it really worked, because sometimes it isn't
solved = checkPuzzle();
trace(solved);




return (endTime - startTime);
}



private function checkCrissCross(el:uint):void
{
// check if we have encountered a new element, if so change all numbers in the row and column
var getal:uint = puzzleSolve[guess][el];
// now it is time to check if the element still exists
// noooo! stop!
if (getal == 0) {stopIt = true;solved = false;}
// a key member, look if we can add it to our arrays
else if ((getal & (getal-1)) == 0)
{
// aha, a new element! how cool!
// is it really unknown to us?
if (elStack[guess].indexOf(el) == -1)
{
elStack[guess].push(el);
if (elStack[guess].length == 81) solved = true;
changeCrissCross(el,getal);
}

// look if the element was not a guessing element
if (possibleGuessEl == el) possibleGuessPoss = 10;
}
else
{
var poss:uint = 2;
var getal1:int = -1;
var getal2:int = -1;
// find the first set bit and last set bit, might find a faster algorithm
for(var j:uint=0;j<9;j++)
{
if ((getal & 1<<j) > 0)
{
getal2 = j;
if (getal1 == -1) getal1 = j;
}
}

// count the number of true values
for (j=getal1+1;j<getal2 && poss < possibleGuessPoss;j++)
{
if (puzzleSolve[guess][el] & Math.pow(2,j)) poss++;
}
if (poss < possibleGuessPoss)
{
// a very good element to guess, so use it
possibleGuessPoss = poss;
possibleGuessEl = el;
}

}
}

private function changeCrissCross(el:uint, getal:int):void
{
var newEl:uint;
var rowNumber:uint = koppelTabel[el][0];
var colNumber:uint = koppelTabel[el][1];
var blockNumber:uint = koppelTabel[el][2];

for (var i:uint = 0; i<9 && !stopIt;i++)
{
// look in the rows/cols/blocks element and set the element to false
newEl = rows[rowNumber][i];
if ((puzzleSolve[guess][newEl] & getal) > 0 && newEl != el && !stopIt)
{
// not set to false, so do set it!
puzzleSolve[guess][newEl] &= ~getal;

// now check if things have changed
checkCrissCross(newEl);
}
newEl = cols[colNumber][i];
if ((puzzleSolve[guess][newEl] & getal) > 0 && newEl != el && !stopIt)
{
// not set to false, so do set it!
puzzleSolve[guess][newEl] &= ~getal;

// now check if things have changed
checkCrissCross(newEl);
}
newEl = blocks[blockNumber][i];
if ((puzzleSolve[guess][newEl] & getal) > 0 && newEl != el && !stopIt)
{
// not set to false, so do set it!
puzzleSolve[guess][newEl] &= ~getal;

// now check if things have changed
checkCrissCross(newEl);
}
}
}




// Just to look if the solution found is a doable solution
private function checkPuzzle():Boolean
{
var solvedIt:Boolean = true;
var i:uint;
var j:uint;
var k:uint;
var getal:int;
var getal1:int;
var getal2:int;
var newEl:uint;
var theRow:uint
var theCol:uint
var theBlock:uint
for (i = 0; i<81 && solvedIt;i++)
{

getal = puzzleSolve[guess][i];
getal1 = -1;
getal2 = -1;
for(j=0;j<9;j++)
{
if ((getal & (1<<j)) > 0)
{
getal2 = j;
if (getal1 == -1) getal1 = j;
}
}

if ((getal & (getal-1)) > 0) solvedIt = false;

theRow = koppelTabel[i][0];
theCol = koppelTabel[i][1];
theBlock = koppelTabel[i][2];

// check in the rows, cols and blocks

for (k = 0; k<9 && solvedIt;k++)
{
for (j=0;j<3 && solvedIt;j++)
{

switch (j)
{
case (0):
newEl = rows[theRow][k];
break;
case (1):
newEl = cols[theCol][k];
break;
case (2):
newEl = blocks[theBlock][k];
break;
}
if ((puzzleSolve[guess][newEl] & getal) && newEl !== i) solvedIt = false;
}
}
}
return solvedIt;
}


// This converts back teh puzzle in a 2D array, reayd to be read by SudokuIndex4
private function displayPuzzle(theArr:Array):void
{
var getal:int;
for (var j:uint=0;j<81;j++)
{
getal = theArr[guess][j];
if ((getal & (getal-1)) == 0)
{
for(var i:uint =0;i<9 && (getal & 1<<i) == 0;i++);
__puzzle[Math.floor(j/9)][j%9] = i + 1;
}
else
{
__puzzle[Math.floor(j/9)][j%9] = 0;
}
if (j%9 == 8) trace(__puzzle[Math.floor(j/9)].join(" "));
}
}
public function get puzzle():Array
{

return __puzzle;
}
public function get timesGuessed():uint
{

return totalGuess;
}

public function get isItSolved():Boolean
{
return solved;
}
}
}

[BernardV]

Zal vanavond later ook even een volledig werkende versie posten.

[GBest]

Vanochtend was ik even lekker bezig met het 'optimaliseren' van de oplosser. Na het logischer plaatsen van sommige stukken code heb ik ook nog een 'domme' fout opgespoort die op de grotere puzzles zelfs 2 ms! winst oplevert. Programma is te vinden in de attachment en het belangrijke deel van de code wordt hieronder gepost:

internal function solve(puzzleF:Array):uint
{
// start with timing
var startTime:uint = getTimer();
var endTime:uint;

// declaring
var getal:int;
var getalGuess:int;
var el:uint;
var didAGuess:Boolean;

var i:uint;
var j:uint;
var poss:uint;



/********************************************/
/* */
/* Initialisation */
/* */
/********************************************/
solved = false;
stopIt = false;

guess = 0;
totalGuess = 0;
guessed = new Array();
puzzleSolve = new Array();


puzzleSolve[0] = puzzleStart.slice(0,81);
elStack = new Array(1);
elStack[0] = new Array();



/********************************************/
/* */
/* First Run */
/* */
/********************************************/
// first try to solve it with rows and columns elimination
possibleGuessPoss = 10;
possibleGuessEl = 81;
for (i = 0; i<9; i++)
{
for (j=0; j<9; j++)
{

// first initialize the puzzle we had in a first run
if (puzzleF[i][j] !== 0)
{
el = 9*i + j;
getal = puzzleF[i][j];
puzzleSolve[0][el] = 0;
puzzleSolve[0][el] = 1<<(getal-1);

checkCrissCross(el);
}
}
}





/********************************************/
/* */
/* Guessing parts */
/* */
/********************************************/
while (!solved)
{




/********************************************/
/* */
/* Undo a guess */
/* */
/********************************************/
if (stopIt)
{
// oops, wrong guess, restore the last guess
do
{
// find the element and number we guessed
el = guessed[guessed.length - 1][0];
getal = guessed[guessed.length - 1][1];

guessed.pop();
puzzleSolve.pop();
elStack.pop();
guess--;

// trek 'getal' van puzzleSolve[guess][el] af.
puzzleSolve[guess][el] &= ~getal;
} while (puzzleSolve[guess][el] == 0);
stopIt = false;
}


/********************************************/
/* */
/* Make a 'smart' guess */
/* */
/********************************************/
// next try to solve it by an educated guess
else
{

guess++;
totalGuess++;
elStack[guess] = elStack[guess-1].slice();
puzzleSolve[guess] = puzzleSolve[guess - 1].slice(0,81);

if (possibleGuessPoss == 10)
{
// aaargh! we need to find a stupid element fast! Luckily this does not happen so much (i.e. never)
//trace("aargh");
for (i = 0; i<81 && possibleGuessPoss > 2; i++)
{
getal = puzzleSolve[guess][i];
if (getal > 0 && (getal & (getal - 1)) > 0)
{
poss = 0;
for (j=0;j<9 && poss < possibleGuessPoss;j++)
{
if ((getal & 1<<j) > 0) poss++;
}
if (poss < possibleGuessPoss)
{
// a very good element to guess, so use it
possibleGuessPoss = poss;
possibleGuessEl = i;
}
}
}
}
el = possibleGuessEl;
getal = puzzleSolve[guess][el];

// find the next power of two (starting from 0)
for(i=0;i<9 && (getal & 1<<i) == 0;i++);
getal = Math.pow(2,i);

// this is the one we're going to try!
guessed.push([el,getal]);
puzzleSolve[guess][el] = getal;
}


/********************************************/
/* */
/* Solve it the criss cross way! */
/* */
/********************************************/
possibleGuessPoss = 10;
checkCrissCross(el);
}
// We cheat here a little bit by placing the end right after the solving, but we haven't converted yet to a 2D array.... There was no rule on this... It saves us 1 ms!
endTime = getTimer();

/********************************************/
/* */
/* We did it again! */
/* */
/********************************************/
trace("final!");
displayPuzzle(puzzleSolve);
trace("could be done in "+guess+" guesses");
trace("no. of guesses: "+totalGuess);
// end timing

trace("Time: "+(endTime - startTime)+"ms");
// check if it really worked, because sometimes it isn't
solved = checkPuzzle();
//solved = true;
trace(solved);




return (endTime - startTime);
}



private function checkCrissCross(el:uint):void
{
// check if we have encountered a new element, if so change all numbers in the row and column
var getal:uint = puzzleSolve[guess][el];
// now it is time to check if the element still exists
// noooo! stop!
if (getal == 0) {stopIt = true;solved = false;}
// a key member, look if we can add it to our arrays
else if ((getal & (getal-1)) == 0)
{
// aha, a new element! how cool!
// is it really unknown to us?
if (elStack[guess].indexOf(el) == -1)
{
elStack[guess].push(el);
if (elStack[guess].length == 81) solved = true;
changeCrissCross(el,getal);
}

// look if the element was not a guessing element
if (possibleGuessEl == el) possibleGuessPoss = 10;
}
else
{
var poss:uint = 0;

for (var j:uint=0;j<9 && poss < possibleGuessPoss;j++)
{
if ((getal & 1<<j) > 0) poss++;
}
if (poss < possibleGuessPoss)
{
// a very good element to guess, so use it
possibleGuessPoss = poss;
possibleGuessEl = el;
}

}
}

private function changeCrissCross(el:uint, getal:int):void
{
var newEl:uint;
var rowNumber:uint = koppelTabel[el][0];
var colNumber:uint = koppelTabel[el][1];
var blockNumber:uint = koppelTabel[el][2];

for (var i:uint = 0; i<9 && !stopIt;i++)
{
// look in the rows/cols/blocks element and set the element to false
newEl = rows[rowNumber][i];
if ((puzzleSolve[guess][newEl] & getal) > 0 && newEl != el && !stopIt)
{
// not set to false, so do set it!
puzzleSolve[guess][newEl] &= ~getal;

// now check if things have changed
checkCrissCross(newEl);
}
newEl = cols[colNumber][i];
if ((puzzleSolve[guess][newEl] & getal) > 0 && newEl != el && !stopIt)
{
// not set to false, so do set it!
puzzleSolve[guess][newEl] &= ~getal;

// now check if things have changed
checkCrissCross(newEl);
}
newEl = blocks[blockNumber][i];
if ((puzzleSolve[guess][newEl] & getal) > 0 && newEl != el && !stopIt)
{
// not set to false, so do set it!
puzzleSolve[guess][newEl] &= ~getal;

// now check if things have changed
checkCrissCross(newEl);
}
}
}

[SaphuA]

Dag mensen, hoewel ik niet erg actief meer ben op het forum kijk ik nog regelmatig even rond. Ook deze post was mij opgevallen, en ik moet zetten dat beide kandidaten een mooi stukje werk geleverd hebben.

Ik heb echter een opmerking; jammer dat het brute force is.

Hoewel brute force natuurlijk goed (en blijkbaar ook erg snel, netjes hoor) werkt zitten er ook enkele nadelen aan vast. Met een logische solver (de puzzle oplossen via logische technieken ipv ´simpelweg gokken´) heb je een hoop meer informatie en mogelijkheden beschikbaar.

- Zo weet je bijvoorbeeld welke technieken er nodig zouden zijn om een puzzle op te lossen en dus of een puzzle uberhaupt op te lossen is zonder te gokken.
- Tevens kun je via deze weg zelf een puzzle laten genereren, omdat je over informatie beschikt of de puzzle logisch is op te lossen ja of nee. Dan kun je zorgen dat je random velden invoert (of verwijderd uit een volledig grid) en controleren of hij oplosbaar is terwijl je zo min mogelijk velden gebruikt.
- Ook heb je informatie over de moeilijkheidsgraad van puzzles, aangezien de technieken of combinaties ervan in te delen zijn in een bepaald niveau.

Edit:
Ben overigens weer begonnen met mijn eigen solver in C# en heb al redelijk wat. Hij gebruikt nog eenvoudige technieken maar kan onderstaande puzzle eenvoudig en in 1ms oplossen.

http://www.saphua.com/temp/puzzle.jpghttp://www.saphua.com/temp/gui.jpg

[M0L]

Dag mensen, hoewel ik niet erg actief meer ben op het forum kijk ik nog regelmatig even rond. Ook deze post was mij opgevallen, en ik moet zetten dat beide kandidaten een mooi stukje werk geleverd hebben.

Ik heb echter een opmerking; jammer dat het brute force is.

Hoewel brute force natuurlijk goed (en blijkbaar ook erg snel, netjes hoor) werkt zitten er ook enkele nadelen aan vast. Met een logische solver (de puzzle oplossen via logische technieken ipv ´simpelweg gokken´) heb je een hoop meer informatie en mogelijkheden beschikbaar.

- Zo weet je bijvoorbeeld welke technieken er nodig zouden zijn om een puzzle op te lossen en dus of een puzzle uberhaupt op te lossen is zonder te gokken.

- Tevens kun je via deze weg zelf een puzzle laten genereren, omdat je over informatie beschikt of de puzzle logisch is op te lossen ja of nee. Dan kun je zorgen dat je random velden invoert (of verwijderd uit een volledig grid) en controleren of hij oplosbaar is terwijl je zo min mogelijk velden gebruikt.

- Ook heb je informatie over de moeilijkheidsgraad van puzzles, aangezien de technieken of combinaties ervan in te delen zijn in een bepaald niveau.
Ik was bezig met een niet brute-force oplossing, door gewoon de technieken toe te passen die je zelf ook toepast als je zelf een puzzel oplost.
De eerste 2 technieken had ik al toegepast en daarmee kun je alle makkelijke sudoku's oplossen,
maar de andere techniek kreeg ik niet toegepast waardoor ik geen zin meer kreeg om het project af te maken.

Deze 2 technieken kreeg ik niet goed toegepast:
http://upload.wikimedia.org/wikipedia/en/thumb/3/37/Sudoko-Row_contingency.svg/330px-Sudoko-Row_contingency.svg.pnghttp://upload.wikimedia.org/wikipedia/en/d/d0/Sudoku_Analysis.gif

[SaphuA]

Ha die Mol ;)

Kun je ze wat nader uitleggen?

Bij de eerste zie ik niet echt wat er moeilijk aan is. Je kunt eenvoudig de groene al invullen, dis is gewoon 4. Je weet dat de 3e van de rode lijn een 6 moet zijn, want de 3 en de 5 kunnen niet. De middelste wordt dan een 3 en de eerste een 5.

De tweede is inderdaad moeilijker om te implementeren. Dan zul je technieken moeten toepassen die mogelijke waardes wegstreept. Dus dat de 8 geheel rechts niet mogelijk is, omdat hij dan niet meer opgelost kan worden.

[GBest]

Logisch oplossen is inderdaad een mooie methode om je puzzles op te lossen, maar niet elke puzzle is logisch op te lossen. Bijvoorbeeld deze: http://zonkedyak.blogspot.com/2006/11/worlds-hardest-sudoku-puzzle-al.html (The chain of deduction (if this is the correct term) is maximum of eight.) of deze http://www.usatoday.com/news/offbeat/2006-11-06-sudoku_x.htm (Escargot demands those tackling it to consider eight casual relationships simultaneously while the most complicated variants attempted by the general public only require people to think of one or two combinations at any one time) en als er gekeken wordt naar de website waar de post naar refereerd dan vinden we ook sudokus die niet 'logisch' zijn op te lossen (http://www.sudokusolver.co.uk/nl_grids_nologic.html)

Vooral die laatste link laat duidelijk zien dat niet alles logisch op te lossen is, mits de site het bij het rechte eind heeft.

[M0L]

Ha die Mol ;)

Kun je ze wat nader uitleggen?

Bij de eerste zie ik niet echt wat er moeilijk aan is. Je kunt eenvoudig de groene al invullen, dis is gewoon 4. Je weet dat de 3e van de rode lijn een 6 moet zijn, want de 3 en de 5 kunnen niet. De middelste wordt dan een 3 en de eerste een 5.

De tweede is inderdaad moeilijker om te implementeren. Dan zul je technieken moeten toepassen die mogelijke waardes wegstreept. Dus dat de 8 geheel rechts niet mogelijk is, omdat hij dan niet meer opgelost kan worden.
Die eerste is opzich niet moeilijk maar kan met dezelfde techniek opgelost worden als de 2e dus ik wilde ze tegelijk implementeren.
Bij elk vakje heb ik een lijst met welke waardes er nog mogelijk zijn, maar hoe zou je dan kunnen controleren dat bijv. 3 hokjes samen maar 3 oplossingen kunnen hebben (plaatje 2).

[SaphuA]

Momenteel doe ik het op onderstaande manier, daarmee is het mogelijk jouw probleem ook op te lossen.

Voor elke cel houd ik 3 vormen van informatie bij:
- De huidige waarde: Dit lijkt me duidelijk, een getal van 0-9
- Het aantal pointers: Voor elke cel houd ik bij hoe vaak een bepaald getal erop gericht staat. Dit is erg handig voor performance redenen. (Waneer een getal er niet op gericht staat is het dus een mogelijke kandidaat).
- Eliminaties: Dit is interesant voor jouw probleem. Met eliminatie technieken kun je voor verschillende cellen bijhouden welke waarde absoluut niet mogelijk is. Ik houd dus voor elke cel bij welk cijfer is geëlimineerd. Dit doe op apart, zodat de telling van het aantal pointers niet in de soep loopt.

[GBest]

Hoe zit het met de einduitslag?

Groeten, Geert

[Mr. Black]

Hoe zit het met de einduitslag?

Nouja, "einduitslag", er zijn in totaal 2 inzendingen binnengekomen. Van mij mogen jullie je allebei als winnaar zien.

Ik hoop dat in de volgende Monthly weer wat meer mensen meedoen. Want dit begon leuk, maar na 1 weekje lag het helemaal DOOD.

[BernardV]

Ik ben voor GBest, immers is zijn oplosser sneller :)

[GBest]

Jippie, daar ben ik blij om. Helaas is er niet heel veel eer aan te behalen.

Wat betreft de oplossing. De oplossing is ten dele Brute Force, maar voor computers zijn Brute Force vaak nog sneller dan logische oplossingen. Zo was er laatst een man die bij ons een Robot Workshop gaf. Hij vertelde dat er in het begin computers bedacht werden die konden schaken. Uiteindleijk hebben deze computers ook de grootmeetsres kunnen verslaan. Daarna was men toe aan een nieuwe uitdaging en moesten robots ook fysaieke actie ondernemen: Dus ze moesten een parcours afleggen tussen 10 paaltjes die kriskras door elkaar stonden. Verscheidene teams deden mee die allemaal gingen uitrekenen waar die palen stonden, paden gingen verzinnen, etc. ER was ook een vader met zijn zoontje die een robot had die gewoon overal tegenaanliep, totdat hij de juiste volgorde had. Die laatste was verschillende malen sneller dan de andere computers (bron zoek ik op).

Dus Brute Force is voor computers vaak sneller dan logisch

[BernardV]

Helemaal een logische brute force die je kunt bereiken met backtracking.
Want als 1,2,3,4,6 niet kan, waarom zou je dan checken op 1,2,3,4,6,5 :)

Maar je hebt het verdient! Vind je oplossing een mooie :)

Het is wel zo dat ik meet van klik op de "solve" knop tot resultaat, maar dat verschil is zo klein dat het nog niet de snelheden haalt die jij haalt.

[Mr. Black]

Nou, het lijkt me wel duidelijk dat deze Monthly al lang aan zijn einde is gekomen. Lijkt het ons leuk voor weer een nieuwe? In Zuid-Nederland is het carnavalsvakantie, dus misschien kunnen er nu wél wat meer mensen meedoen (of iedereen moet hard werken, kan natuurlijk ook :)).

Als je dus zin hebt, laat het even weten! Of als je een goed idee hebt, want er moet natuurlijk ook weer een thema zijn. Paar ideetjes van mezelf:

5k (maximaal 5 kilobyte om een spel / reader / etc. te maken)
Iets met Bitmaps (pixel per pixel lezen, foto-, cijfer- of letterherkenning)
Experimentele experimentjes met PV3D 2


Laat wat van je horen (of niet...)!

[nee, geen nieuw topic, vond ik weer zo zonde. :)]

[M0L]

Ik ben morgen op vakantie :) mar daarna zal ik wel meedoen ;)
Vooral iets met bitmaps lijkt wel leuk.

[Mediamonkey]

Vandaag stond er een sudoku op de BNN scheurkalender, en na 3 biertjes had ik 'm opgelost. Ik was wel benieuwd of hij klopte, dus ik heb BernardV z'n solver er bij gepakt en 'm gecheckt. Mooi dat ie klopte! :)

Maar aangezien een array zo moeilijk leest heb ik er even een kleine conversie voor geschreven. Misschien een leuk voorbeeld voor mensen die niet veel met modulo werken.

Greetz

import SudokuSolver;

var sudokuArray:Array = [
[4,0,0, 9,3,0, 0,0,0],
[0,0,9, 2,0,0, 8,7,0],
[1,0,0, 0,4,5, 0,0,0],

[0,0,0, 1,0,0, 0,3,0],
[2,0,0, 0,0,9, 0,0,0],
[0,4,0, 0,8,0, 0,0,0],

[8,1,2, 0,0,4, 0,0,9],
[0,0,5, 0,7,0, 6,0,0],
[0,6,0, 0,0,0, 0,0,3]
]

var result:Array = SudokuSolver.solve(sudokuArray);
trace(toReadableResult(result));

function toReadableResult(value:Array):String {
var result:String = "";
var mod:uint;

for (var i:uint=0; i<value.length; i++) {
mod = i%9;
result += value[i]+",";

if (mod == 0) result += "";
else if (mod == 2 || mod == 5) result += " ";
else if (mod == 8) result += "\n";

if (i%27 == 26) result += "\n";
}

return result;
}

Dit geeft:
4,2,7, 9,3,8, 5,1,6,
3,5,9, 2,1,6, 8,7,4,
1,8,6, 7,4,5, 3,9,2,

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

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