Mittwoch, 23. Dezember 2015

Akka.NET Adventskalender – Tür 23

Hab was vergessen

Leider hat unsere gestrige Variante es nicht geschafft, das schwierige Sudoku zu lösen. Natürlich sind wir selbst daran schuld, denn wir haben eine Sudoku Regel schlicht vergessen zu implementieren. "Jede Ziffer darf pro Zeile, Spalte oder Block nur einmal auftreten." Dass das einfache Sudoku geklappt hat, war purer Zufall (ehrlich gesagt musste ich ein wenig suchen, um ein geeignetes einfaches Sodoku zu finden...). Wir brauchen also noch ein paar weitere Dinge, damit wir auch schwierige Sudoku Aufgaben lösen können.

Als erstes müssen wir uns darum kümmern, dass jemand die Häufigkeit der potentiell platzierbaren Ziffern pro Zeile, Spalte und Block für uns mit verfolgt. Jedesmal wenn eine Zelle eine Ziffer gesetzt bekommt, oder eine Ziffer als mögliche Lösung für eine Zelle ausschließt, müssen wir die passende Statistik dazu anpassen. Stellen wir dabei fest, dass eine Ziffer irgendwo exakt einmal auftritt, dann können wir daraus kombinieren, dass diese Ziffer in der jeweiligen Zeile, Spalte oder Block gesetzt werden darf – sie ist ja die einzige ihrer Art.

Grundsätzlich benötigen wir also 3 Typen (Zeile, Spalte, Block) mal 9 (für jede Ziffer) Aktoren für unsere Statistik nach diesem Muster. Aufgrund der einfacheren Lesbarkeit verzichten wir hier auf die Erzeugung einer Basisklasse und wiederholen den doch recht einfachen Code anstelle ihn zu generalisieren.

using System;
using Akka.Actor;
using SudokuSolver.Messages;
using System.Collections.Generic;
using System.Linq;

namespace SudokuSolver.Actors
{
    public class SudokuCol : SudokuActor
    {
        private readonly int col;

        private List<int> statistics;

        public SudokuCol(int col)
        {
            this.col = col;

            statistics = Enumerable.Range(1, 9).Select(_ => 9).ToList();

            Receive<SetDigit>(SetStatistics, s => s.Col == col);
            Receive<StrikeDigit>(UpdateStatistics, s => s.Col == col);
        }

        private void SetStatistics(SetDigit setDigit)
        {
            var digit = setDigit.Digit;

            statistics[digit - 1] = 1;
        }

        private void UpdateStatistics(StrikeDigit strikeDigit)
        {
            var digit = strikeDigit.Digit;

            if (--statistics[digit-1] == 1)
                Publish(new FindColDigit(col, digit));
        }
    }
}

Und wir müssen unsere Aktoren für die einzelnen Zellen dahingend schlauer machen, dass sie dann wenn Ziffern als potentielle Lösungen ausscheiden, jeweils die passende StrikeDigit Nachricht aussenden sowie auf FindXxxDigit Nachrichten reagieren.

Unsere Sudoku Aktoren für die einzelnen Zellen verarbeiten also diese 3 weiteren Nachrichten:

Receive<FindRowDigit>(FindDigitHandler, f => f.Row == row);
Receive<FindColDigit>(FindDigitHandler, f => f.Col == col);
Receive<FindBlockDigit>(FindDigitHandler, f => f.Block == block);

und reagieren darauf wie folgt:

private void FindDigitHandler(FindDigit findDigit)
{
    var digit = findDigit.Digit;

    if (possibleDigits.Contains(digit))
        Publish(new SetDigit(row, col, digit));
}


Damit haben wir auch die gestern vergessene letzte Sudoku Regel mit implementiert und zählen nun 108 Aktoren, die gemeinsam und allein durch wirres Hin- und Herschreien ein Sudoku lösen. Irgendwo faszinierend, dass das funktionert.

Wiederum ist für den fertigen Code ein github Repository vorhanden.

Keine Kommentare:

Kommentar veröffentlichen