Weekendje Sudoku Fun

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

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.