Lösungen für (4x4) Sudokus mit SQL finden

Der Frühling lässt leider noch auf sich warten. Heute ist Sonntag, draußen ist es bitter kalt und es weht ein eisiger Wind. Da liegt es natürlich nahe, diesen Sonntag größtenteils am PC zu verbringen. :)

Was ich immer schon einmal näher untersuchen wollte, ist die Frage, ob die Lösungen für ein Sudoku Rätsel nicht mittels SQL gefunden werden können. SQL ist ja sehr mächtig, wenn es darum geht, Kombinationen von Tabellenzeilen zu bilden. Könnte man dann nicht einfach alle möglichen Kombinationen für gültige Zeilen in einem Sudoku bilden? Das wäre sozusagen ein Brute-Force Ansatz mit SQL. Theoretisch sollte es funktionieren, auch wenn die Anzahl der möglichen Kombinationen für ein 9x9 Sudoku sehr wahrscheinlich zu groß dafür sein wird, dass unsere heutigen Computer in endlicher Zeit eine Lösung finden.

Aber gut, fangen wir eben mit einem 4x4 Sudoku an, um erst einmal zu sehen, ob es überhaupt funktioniert. Noch einmal zur Wiederholung und für all diejenigen, die es noch nicht wissen: Ein 4x4 Sudoku ist ein Zahlenrätsel aus vier Zeilen und vier Spalten. In jeder Zeile und jeder Spalte muss jede der Ziffern von 1 bis 4 genau einmal vorkommen. Zusätzlich muss auch in jedem der vier Quadranten des Rätsels jede der Ziffern 1 bis 4 genau einmal erscheinen. Eine Beispiellösung für ein 4x4 Sudoku sieht so aus:

Also los. Zu Beginn erzeugen wir eine eigene Datenbank für unsere Experimente. Das erleichtert einfach nur die späteren Aufräumarbeiten. Da wir irgendwann auch mit 9x9 Sudokus experimentieren wollen, legen wir außerdem ein Schema an, das unsere Objekte für die Versuche mit dem 4x4 Sudoku beherbergen wird.

create database Sudoku;
go
use Sudoku;
go
create schema Four;

Wir erzeugen nun eine Tabelle mit vier Spalten. In dieser Tabelle speichern wir alle erlaubten Kombinationen von jeweils vier Ziffern, die in einer Zeile, einer Spalte oder einem Quadranten des Sudoku Rätsels vorkommen dürfen. Eine erlaubte Kombination enthält jede der Ziffern von 1-4 genau einmal. So sieht diese Tabelle aus:

create table Four.ValidSets
 (
  n1    tinyint not null check(n1 between 1 and 4)
 ,n2    tinyint not null check(n2 between 1 and 4)
 ,n3    tinyint not null check(n3 between 1 and 4)
 ,n4    tinyint not null check(n4 between 1 and 4)
 ,val   as (n1*1000+n2*100+n3*10+n4) persisted primary key
 ,constraint chk_DistinctSet_distinct check(n1 != n2 and n1 != n3 and n1 != n4
                                        and n2 != n3 and n2 != n4 and n3 != n4)
 );

Die CHECK Constraints sorgen für das Einhalten der Bedingung, dass jede der Ziffern 1 bis 4 nur jeweils einmal pro Zeile vorhanden sein darf. Die Tabelle bekommt eine Hilfsspalte (val), die wir später für unsere Suche nach gültigen Sudoku-Lösungen benötigen werden. Diese Spalte vereinfacht das Formulieren entsprechender Verknüpfungsbedingungen. Die gültigen Zeilen können wir nun einfach mit dem folgenden Kommando eintragen:

with cols(element) as
 (
  select 1 union select 2 union select 3 union select 4
 )
 insert Four.ValidSets(n1,n2,n3,n4)
  select r1.element
        ,r2.element
        ,r3.element
        ,r4.element
    from cols as r1
         cross join cols as r2
         cross join cols as r3
         cross join cols as r4
   where r1.element <> r2.element
     and r1.element <> r3.element
     and r1.element <> r4.element
     and r2.element <> r3.element
     and r2.element <> r4.element
     and r3.element <> r4.element;

Es gibt insgesamt nur 24 gültige Kombinationen, also Zeilen, in denen jede der Ziffern von 1 bis 4 genau einmal vorkommt. Die Tabelle Four.ValidSets ist nun die Basis für die Suche nach allen möglichen Lösungen eines 4x4 Sudokus. Wir wissen, dass jede Zeile, jede Spalte und jeder Quadrant einer Zeile aus unserer Tabelle Four.ValidSets entsprechen muss. Für die Formulierung entsprechender Verknüpfungsbedingungen verwenden wir die Hilfsspalte val. Um ein wenig Schreibarbeit zu sparen, legen wir noch eine Funktion an, die aus vier beliebigen Ziffern einen Wert berechnet, der dann mit der Spalte val verglichen werden kann. Diese Funktion sieht so aus:

create function Four.GetIndex(@n1 tinyint, @n2 tinyint
                             ,@n3 tinyint, @n4 tinyint)
 returns smallint
  as
 begin
   return (@n1*1000+@n2*100+@n3*10+@n4);
 end;

Jede Lösung des Sudoku hat vier Zeilen. Also werden wir unsere Basistabelle Four.ValidSets drei Mal mit sich selber verknüpfen. Die Verknüpfungsbedingungen werden dabei so formuliert, dass eine Ziffer in jeder Spalte, jeder Zeile und jedem Quadranten des Sudoku genau einmal vorkommt. Und so sieht die entsprechende Abfrage aus:

select s1.n1,s1.n2,s1.n3,s1.n4
      ,s2.n1,s2.n2,s2.n3,s2.n4
      ,s3.n1,s3.n2,s3.n3,s3.n4
      ,s4.n1,s4.n2,s4.n3,s4.n4
  from Four.ValidSets as s1
       inner join Four.ValidSets as s2 on s2.val != s1.val
       inner join Four.ValidSets as s3
               on s3.val != s2.val and s3.val != s1.val
         inner join Four.ValidSets as s4
               on s4.val != s3.val and s4.val != s2.val and s4.val != s1.val
   where -- Vier Spalten
         Four.GetIndex(s1.n1,s2.n1,s3.n1,s4.n1)
                in (select val from Four.ValidSets)
     and Four.GetIndex(s1.n2,s2.n2,s3.n2,s4.n2)
                in (select val from Four.ValidSets)
     and Four.GetIndex(s1.n3,s2.n3,s3.n3,s4.n3)
                in (select val from Four.ValidSets)
     and Four.GetIndex(s1.n4,s2.n4,s3.n4,s4.n4)
                in (select val from Four.ValidSets)
     -- Vier Quadranten
     and Four.GetIndex(s1.n1,s1.n2,s2.n1,s2.n2)
                in (select val from Four.ValidSets)
     and Four.GetIndex(s1.n3,s1.n4,s2.n3,s2.n4)
                in (select val from Four.ValidSets)
     and Four.GetIndex(s3.n1,s3.n2,s4.n1,s4.n2)
                in (select val from Four.ValidSets)
     and Four.GetIndex(s3.n3,s3.n4,s4.n3,s4.n4)
                in (select val from Four.ValidSets);

Das ist auch schon beinahe alles. Was nun noch fehlt ist lediglich ein wenig Kosmetik. Die Abfrage gibt eine Zeile je Lösung zurück, wobei nach jeweils vier Spalten eine neue Zeile im Sudoku begonnen werden muss. Hier ein Auszug aus dem Ergebnis:

 n1  n2  n3  n4  n1  n2  n3  n4  n1  n2  n3  n4  n1  n2  n3  n4
  1   2   3   4   3   4   1   2   4   3   2   1   2   1   4   3
  1   2   3   4   3   4   1   2   4   1   2   3   2   3   4   1
  1   2   3   4   3   4   1   2   2   3   4   1   4   1   2   3
  1   2   3   4   3   4   1   2   2   1   4   3   4   3   2   1
  1   2   3   4   3   4   2   1   4   3   1   2   2   1   4   3
  1   2   3   4   3   4   2   1   2   1   4   3   4   3   1   2
  1   2   3   4   4   3   1   2   3   4   2   1   2   1   4   3
  1   2   3   4   4   3   1   2   2   1   4   3   3   4   2   1
  1   2   3   4   4   3   2   1   3   4   1   2   2   1   4   3
  1   2   3   4   4   3   2   1   3   1   4   2   2   4   1   3

Eleganter wäre natürlich eine Darstellung, bei der der Zeilenumbruch mit dargestellt wird. Das wäre ja dann wohl ein Anwendungsbeispiel für den UNPIVOT-Operator, nicht wahr? Wer den nicht so gerne mag (wie ich), der kommt aber auch mit UNIONs zum Ziel:

with Solutions(puzzle,r1c1,r1c2,r1c3,r1c4
                     ,r2c1,r2c2,r2c3,r2c4
                     ,r3c1,r3c2,r3c3,r3c4
                     ,r4c1,r4c2,r4c3,r4c4) as
 (
  select row_number() over(order by s1.val,s2.val,s3.val,s4.val)
        ,s1.n1,s1.n2,s1.n3,s1.n4
        ,s2.n1,s2.n2,s2.n3,s2.n4
        ,s3.n1,s3.n2,s3.n3,s3.n4
        ,s4.n1,s4.n2,s4.n3,s4.n4
    from Four.ValidSets as s1
         inner join Four.ValidSets as s2 on s2.val != s1.val
         inner join Four.ValidSets as s3 on s3.val != s2.val and s3.val != s1.val
         inner join Four.ValidSets as s4 on s4.val != s3.val and s4.val != s2.val and s4.val != s1.val
   where -- Vier Spalten
         Four.GetIndex(s1.n1,s2.n1,s3.n1,s4.n1) in (select val from Four.ValidSets)
     and Four.GetIndex(s1.n2,s2.n2,s3.n2,s4.n2) in (select val from Four.ValidSets)
     and Four.GetIndex(s1.n3,s2.n3,s3.n3,s4.n3) in (select val from Four.ValidSets)
     and Four.GetIndex(s1.n4,s2.n4,s3.n4,s4.n4) in (select val from Four.ValidSets)
     -- Vier Quadranten
     and Four.GetIndex(s1.n1,s1.n2,s2.n1,s2.n2) in (select val from Four.ValidSets)
     and Four.GetIndex(s1.n3,s1.n4,s2.n3,s2.n4) in (select val from Four.ValidSets)
     and Four.GetIndex(s3.n1,s3.n2,s4.n1,s4.n2) in (select val from Four.ValidSets)
     and Four.GetIndex(s3.n3,s3.n4,s4.n3,s4.n4) in (select val from Four.ValidSets)
 )
  select puzzle,1 as row,r1c1 as c1,r1c2 as c2,r1c3 as c3,r1c4 as c4 from Solutions
   union all
  select puzzle,2,r2c1,r2c2,r2c3,r2c4 from Solutions
   union all
  select puzzle,3,r3c1,r3c2,r3c3,r3c4 from Solutions
   union all
  select puzzle,4,r4c1,r4c2,r4c3,r4c4 from Solutions
   order by puzzle,row;

Hier wieder ein Auszug aus dem Ergebnis:

puzzle  row  c1  c2  c3  c4
     1    1   1   2   3   4
     1    2   3   4   1   2
     1    3   2   1   4   3
     1    4   4   3   2   1
     2    1   1   2   3   4
     2    2   3   4   1   2
     2    3   2   3   4   1
     2    4   4   1   2   3
     3    1   1   2   3   4
     3    2   3   4   1   2
     3    3   4   1   2   3
     3    4   2   3   4   1

War gar nicht so kompliziert, oder? Mein bereits etwas in die Jahre gekommenes Notebook hat insgesamt ca. zwei Sekunden benötigt, um alle 288 gültigen Lösungen zu finden. In einem kommenden Post werden wir dann einmal 9x9 Sudokus untersuchen, wobei ich jetzt bereits ziemlich sicher bin, dass der Brute Force Ansatz dann nicht zum Erfolg führen wird, weil er einfach zu lange dauert.