Weekendje Sudoku Fun

Door Kaw op woensdag 25 januari 2012 15:16 - Reacties (12)
Categorie: -, Views: 4.193

Van het weekend besloot ik dat het wel leuk zou zijn om een klein project te starten om de computer Sudoku puzzels op te laten lossen.

De Sudoku puzzel
Er bestaan verschillende varianten van de Sudoku puzzel. Ik heb gekozen voor de meest voorkomende. 9x9 vakjes waarin de getallen 1-9 in voorkomen en waarbij op de X- en Y-as de nummers 1-9 slechts 1 keer per getalswaarde mogen voorkomen. De extra regel is dat het veld van 9x9 vakjes opgedeeld is in 3x3 compartimenten van 3x3 velden waar ook de getallen 1-9 slechts 1 keer per getalswaarde mogen voorkomen.

Start
Een array van 9 bij 9 velden waarin we de gegevens van de velden bijhouden lijkt me wel een goede start.

C#:
1
private readonly SudoBoardField[,] _board;


Waarbij de class SudoBoardField de volgende eigenschappen heeft:

C#:
1
2
3
4
5
6
7
8
public int Value;
            public readonly int X;
            public readonly int Y;
            public int Count;
            public int Bits;
            public int Index;
            public int[] CountPerValue;
            public SudoBoardField[] Mutations;

  • Value : De waarde van het veld: 0-8
  • X : De positie van het veld op de X-as van het speelbord: 0-8
  • Y : De positie van het veld op de Y-as van het speelbord: 0-8
  • Count : Het aantal getalwaarden die voor dit veld nog mogelijk zijn 0-9
  • Bits : (Op zijn goed Nederlands) bitflags voor elke bitpositie (0-8) van getalwaarden die reeds gebruikt zijn in de omgeving van het veld en die het veld dus zelf niet meer mag gebruiken. 1 = gebruikt, 0 = vrij
  • Index : De index in de reeks van mogelijke getalwaarden van het veld. Dit wordt gebruikt tijdens de backtracking. (-1 > Index < Count) (Meer uitleg volgt)
  • CountPerValue : Een array van 9 integers (voor elke getalwaarde 1) waar het aantal voorkomens per getalwaarde in de omgeving wordt bijgehouden.
  • Mutations : De broers en zusjes van dit veld die door dit veld worden beÔnvloed als het veld van waarde veranderd.
Bij het initialiseren van de class SudokuFinder wordt het spelbord aangemaakt en worden de SudoBoardFields gevuld met de juiste waarden.
SudoBoardField[] Mutations horen daar ook bij.


C#:
1
2
private static int[] _possibleCount;
        private static int[][] _possibleValues;


Dit is een slimmigheidje om de SudoBoardField.Bits bitflags handig en snel te gebruiken.
Bits bevat maximaal 512 verschillende waarden (0-511 = 9 bits). _possibleCount als array bevat het aantal vrije velden per mogelijke combinatie van bitflags.
_possibleValues doet hetzelfde, maar heeft een subarray waar elk mogelijke getalswaarde in staat die bij de bitflags horen.

Deze twee arrays worden tijdens het initialiseren gevuld.


C#:
1
2
private int _score;
        private int _solutions;


Score geeft grofweg de moeilijkheid van de puzzel aan. Deze bereken ik door _score += n - 1, waarbij n het aantal mogelijke zetten zijn van het veld waar het minst aantal zetten mogelijk zijn. Dat is ook het principe achter de backtracking. Eerst het veld waar de minst mogelijke combinaties kunnen worden gemaakt en dan het volgende veld met het minst aantal mogelijke combinaties, totdat er een veld wordt aangetroffen zonder mogelijkheden of dat alle velden gevuld zijn. In het eerste geval wordt het huidige veld gereset en wordt de volgende mogelijke getalwaarde van het vorige veld gebruikt om verder te itereren. In het geval van dat alle velden een waarde hebben gekregen, is er een oplossing gevonden voor de Sudoku en wordt _solutions met 1 verhoogt. Een typisch recursief proces die ik voor de gein niet recursief heb opgepakt.


C#:
1
2
3
private int _stackIndex;
        private SudoBoardField _currentField;
        private readonly SudoBoardField[] _fields;



_fields is een array die alle 81 velden bevat. _stackIndex is een integer die de eerste locatie aanwijst van velden die nog geen waarde hebben gekregen. 0 < _stackIndex bevat dus de reeds gevulde velden en _stackIndex < 81 bevat de nog te vullen velden.
_currentField is in feite een shortcut voor _fields[_stackIndex];


C#:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public void GetBest()
        {
            _currentField = _fields[_stackIndex];
            if (_currentField.Count > 1)
            {
                int best = _stackIndex;
                for (int i = _stackIndex + 1; i < 81; i++)
                {
                    SudoBoardField tryField = _fields[i];
                    if (tryField.Count < _currentField.Count)
                    {
                        best = i;
                        _currentField = tryField;
                        if (_currentField.Count == 1)
                            break;
                    }
                }
                Push(best);
                _score += _currentField.Count - 1;
            }
        }


Met deze functie wordt het veld gezocht met het laagste aantal mogelijke getalwaarden.
Deze functie wordt aangeroepen wanneer _stackIndex met 1 verhoogt of verlaagd is.
Vermeldingswaardig is nog dat wanneer er een veld gevonden is waar geldt (Count = 1) het proces vroegtijdig afgebroken kan worden, omdat dit de best mogelijke score is.
Alleen de velden die nog geen waarden bevatten worden doorzocht.

De functie Push zorgt voor het plaatsen van het best gevonden veld in de _fields array op de locatie van de _stackIndex.

C#:
1
2
3
4
5
6
public void Push(int index)
        {
            SudoBoardField field = _fields[index];
            _fields[index] = _fields[_stackIndex];
            _fields[_stackIndex] = field;
        }


Al deze moeite heeft twee voordelen. 1. We hebben de gevulde velden apart van de nog te vullen velden, waardoor we die gevulde velden niet meer door hoeven om de laagste Count te vinden. 2. In de praktijk groeperen zich de velden met de laagste Count vooraan in de array waardoor je al snel het veld vind met Count = 1. Alle velden doorzoeken en geen intelligente plaatsing maakt het algoritme als geheel ruim 2 keer zo traag. Een List<int> gebruiken in plaats van deze toch wat ingewikkelde methode maakt het algoritme meer dan 3 keer zo traag. List<int>.Add & .Remove & List<int>[] zijn methodes die je aanroept en het aanroepen van methodes is duur m.b.o. performance.

We moeten natuurlijk wel velden kunnen vullen. Dat doen we met de functie Add.
Deze functie geeft true als het toevoegen lukte en false als dit niet het geval is.

C#:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public bool Add(int value)
        {
            _currentField.Value = value;
            int v = 1 << value;

            int i = 0;
            while (i < 20)
            {
                SudoBoardField field = _currentField.Mutations[i++];
                if(field.CountPerValue[value]++==0)
                {
                    field.Count--;
                    field.Bits += v;
                    if (field.Count == 0)
                    {
                        Remove(i);
                        return false;
                    }
                }
            }
            return true;
        }


_currentField hebben we reeds aangewezen met de functie GetBest(). Die geven we de veldwaarde die we opgegeven hebben met de parameter value.
Vervolgens stappen we door de velden heen die door dit veld worden beÔnvloed.
Dat zijn de velden die op dezelfde X- en Y-as zitten of in hetzelfde compartiment vallen als het huidige veld.
Als field.CountPerValue bij aanvang nog 0 is, dan betekent dat dit veld voor het eerst de waarde van 'value' voor zichzelf niet kan gebruiken. De Count kan daarom verlaagt worden en Bits kan worden aangevuld met de bitflag 'v' van 'value'. Indien Count == 0, dan kan het proces meteen worden afgebroken. Het betekent dat met de huidige situatie het veld 'field' geen mogelijkheden zal kennen wanneer deze aan de beurt is binnen de iteratie. We kunnen daarom de oude situatie herstellen (Remove(i), zie verder op) en false retourneren. Dit geeft een flinke performanceboost.
Als alle 20 mutatievelden gemuteerd zijn, dan is de functie Add geslaagd en retourneert het true.

Naast Add hebben we Remove nodig.

C#:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void Remove(int to)
        {
            int value = _currentField.Value;
            int v = 1 << value;
            _currentField.Value = -1;

            int i = 0;
            while (i < to)
            {
                SudoBoardField field = _currentField.Mutations[i++];
                if (--field.CountPerValue[value] == 0)
                {
                    field.Count++;
                    field.Bits -= v;
                }
            }
        }


Remove is de inverse van Add. De parameter 'to' kan gevuld worden met de waarde 20 om alle velden te resetten, of lager en dat laatste is nuttig wanneer in de functie Add het proces voortijdig is afgebroken. Dan worden alleen de velden gereset die door Add zijn gemuteerd.

Alle hulpfuncties zijn besproken en we kunnen nu daadwerkelijk op zoek naar de oplossing van de Sudoku.

De ingang is als volgt:

C#:
1
2
3
4
5
6
7
8
public int GetSolutions()
        {
            _score = 0;
            _solutions = 0;

            GetSolutionsFlat();
            return _solutions;
        }



De 'intelligentie' zit in deze functie:

C#:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
private void GetSolutionsFlat()
        {
            int stopIndex = _stackIndex;

            GetBest();
            while (true)
            {
                if (Add(_possibleValues[_currentField.Bits][++_currentField.Index]))
                {
                    if (_stackIndex != 79)
                    {
                        _stackIndex++;
                        GetBest();
                        continue;
                    }

                    if (++_solutions > 1)
                        return;
                    Remove(20);
                }

                while (_currentField.Index == _currentField.Count - 1)
                {
                    _currentField.Index = -1;
                    if (_stackIndex-- == stopIndex)
                        return;
                    _currentField = _fields[_stackIndex];
                    Remove(20);
                }
            }
        }


Eerst wordt de stopIndex gezet. Wanneer _stackIndex weer terugkomt op deze index, dan is het zoeken voltooid.

De tweede stap is een begin te maken en het beste veld op de _currentField = _fields[_stackIndex] te plaatsen. Dit doen we met GetBest();

Als het toevoegen (Add) van de eerste getalwaarde mogelijkheid van het huidige veld is gelukt, dan zijn er twee mogelijkheden.
1. We zijn klaar. We verhogen het aantal oplossingen (hier zou je een functie kunnen zetten die de huidige veldwaarden in een array zet, zodat je naderhand de oplossing kunt nakijken, maar daar was ik niet in geÔnteresseerd.) Als het aantal oplossingen meer dan 1 is, dan stoppen we met zoeken, want het is een ongeldige Sudoku. In het andere geval backtracken we een stapje terug met Remove(20).
2. We zijn nog niet klaar. We verhogen de _stackIndex, zoeken het nieuwe beste veld en we gaan weer richting de functie Add.

Binnen de functieaanroep van Add zien we trouwens het nut van de bitflags en _possibleValues. In 1 aanroep hebben we de getalswaarde die we anders zouden moeten zoeken. Met de Index (die meteen met 1 wordt opgehoogd) van het veld bepalen we welke getalwaarde er aan de beurt is.

Als laatste, wanneer de index van het huidige veld door zijn mogelijkheden heen is, dan nemen we een stapje terug in het backtrackingproces en we testen of het nieuwe huidige veld ook niet door zijn mogelijkheden heen is. Indien dat het geval is, dan doen we het gewoon nog een keer. Net zo lang totdat er een veld wordt gevonden met mogelijkheden, of dat we weer terug zijn op het oude startpunt. Dan zijn we klaar.

Nu zijn er nog meer hulpfuncties te bedenken, maar de volgende wil ik nog laten zien:

C#:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void Open(string filename)
        {
            string[] lines = File.ReadAllLines(filename);
            for (int y = 0; y < 9; y++)
                for (int x = 0; x < lines.Length; x++)
                {
                    int v = int.Parse(new string(new[] {lines[y][x]}));
                    if (v == 0) continue;
                    _currentField = _board[x, y];
                    Add(v - 1);
                    for (int i = 0; i < 81; i++)
                        if (_fields[i].X == x && _fields[i].Y == y)
                        {
                            Push(i);
                            break;
                        }
                    _stackIndex++;
                }
        }


Met deze functie kan een Sudoku uit een tekstbestand worden ingelezen.
Deze ziet er dan bijvoorbeeld zo uit:
000080050
120000400
600700000
000600001
800000060
050040000
080050200
009030007
000000006
Deze Sudoku is gevonden tijdens 24 uur lang genereren van willekeurige Sudoku's en het controleren of de Sudoku slechts 1 mogelijke uitkomst kent. Deze Sudoku heeft een score meegekregen van 5196 en bevat 61 lege velden.
De volgende Sudoku heeft een score van 65 en bevat 59 lege velden:
100007090
030020008
009600500
005300900
010080002
600004000
300000010
040000007
007000300
Deze heb ik overgenomen van het volgende bericht: World's hardest sudoku: Can you solve Dr Arto Inkala's puzzle?
Heb ik dan een wereldrecord? :+
Om die vraag te beantwoorden heb ik dokter Arto Inkala een mailtje gestuurd om de Sudoku te laten evalueren.

Reacties


Door Tweakers user karstnl, woensdag 25 januari 2012 15:41

[qOm die vraag te beantwoorden heb ik dokter Arto Inkala een mailtje gestuurd om de Sudoku te laten evalueren.[/q]

Goede grap;) Wel cool gedaan.

Door Tweakers user The Mole, woensdag 25 januari 2012 16:18

Interresant project! :)

Ik weet niet of het helemaal klopt, maar die moeilijkste sudoku ter wereld, lost Google Goggles in een aantal seconde op :D
Maar zoals ik al zei, ik weet niet of alles klopt :p

Door Tweakers user Kaw, woensdag 25 januari 2012 16:31

karstnl schreef op woensdag 25 januari 2012 @ 15:41:
[qOm die vraag te beantwoorden heb ik dokter Arto Inkala een mailtje gestuurd om de Sudoku te laten evalueren.[/q]

Goede grap;) Wel cool gedaan.
Is geen grap. Heb ik echt gedaan. Heb alleen nog geen reactie.

Edit: dit is de email:
quote: Verzonden: Tue 1/24/2012 4:16 PM
Hello Arto Inkala,

Would you please review the following Sudoku?
000080050
120000400
600700000
000600001
800000060
050040000
080050200
009030007
000000006
(Where 0 is an empty field)

My algorithm indicates that it is a hard puzzle to solve. Even harder than AI Escargot.
It’s a fast heavily optimized algorithm so there is always a chance of a bug in the software. Therefor I hope you want to review the Sudoku and confirm to me it’s a correct (1 solution) Sudoku and tell me it’s score according to your algorithm.

Already thanks for your time,
Kind regards,
Kaw

[Reactie gewijzigd op vrijdag 22 juni 2012 14:22]


Door Tweakers user RobIII, woensdag 25 januari 2012 17:13

Already thanks for your time,
Your dunglish is a little brak :P :+

Door Tweakers user Kaw, woensdag 25 januari 2012 17:25

He's from Finland so I hope he has Finlish and he doesn't notice it. ;)

[Reactie gewijzigd op woensdag 25 januari 2012 18:03]


Door Tweakers user Kefding, woensdag 25 januari 2012 18:53

Als het goed is is hier de oplossing van deze sudoku.
http://goo.gl/P2gHM
Ik dacht even dat het hem niet lukte om op te lossen :P

Door Tweakers user Kaw, woensdag 25 januari 2012 19:02

Bedankt Kefding!
Hoe lang duurde het voordat je de oplossing kreeg?

Door Tweakers user tikimotel, woensdag 25 januari 2012 21:32

http://www.sudoku-solutions.com/
Deze site beoordeelde de ge-mailde sudoku als "easy" met maar ťťn oplossing...

Door Tweakers user Kaw, donderdag 26 januari 2012 08:42

Hoi Tikimotel,

Ik heb geen idee waarom die site dat zo beoordeelt. Iets verderop op de site:
As a rule of thumb, 24 initial numbers constitute a very difficult puzzle, whereas 48 numbers constitute a simple puzzle.
Met 20 initial numbers zou je geen easy verwachten.

Door Tweakers user Ram0n, donderdag 26 januari 2012 11:40

De moeilijkheidsgraad van een Sudoku-puzzel is op vele manieren te bepalen, en de meeste implementaties in dit soort algoritmes kijken daar op een geheel andere manier naar dan menselijke spelers.

Als wij dit soort puzzels proberen op te lossen passen we een andere variant van backtracking toe, meer lokaal gericht en meer rekening houdend met ons geheugen. Dit maakt het lastig om systematisch de moeilijkheidsgraad in te schatten.

Door Tweakers user fub, donderdag 26 januari 2012 13:20

Ha! Dit soort logische puzzels kan je het beste gewoon laten oplossen door Prolog -- dat is immers gemaakt om predicaat-logica los te laten op problemen. Zie een mooie oplossing hier

Door Tweakers user Kaw, donderdag 26 januari 2012 13:35

Vond nog een mooie link: http://en.wikipedia.org/wiki/Sudoku_algorithms
Had dat moeten lezen voordat ik begon ;)

Reageren is niet meer mogelijk