[LAMBDA] SUDOKU Generator

[maninweb]

Moin,

hat mich aus reiner Neugierde interessiert, ob sich mit einer LAMBDA-Funktion ein Sudoku generieren lässt. Funktioniert.
Die Formel generiert allerdings Sudokus, die mehrere Lösungen haben können, was aber nicht weiter schlimm sein sollte.
In der Formel ist dann einiges drin, was so Lambas bieten: Rekursion, verschachtelte Lambdas, Iterationen :-)

PHP-Code:

=LAMBDA(Size;Solution;LET(
 fnList;LAMBDA(This;Size;LET(A;EINDEUTIG(ZUFALLSMATRIX(Size^4;1;1;Size^2;WAHR));WENN(WENNFEHLER(ZEILEN(A);0)<Size^2;This(This;Size);A)));
 fnInitialize;LAMBDA(Size;LET(A;SEQUENZ(Size^2);M;SEQUENZ(Size^2;Size^2);R;AUFRUNDEN(M/Size^2;0);C;WENN(REST(M;Size^2)>0;REST(M;Size^2);Size^2);
 REST(ABRUNDEN((R-1)/Size;0)+Size*REST(R-1;Size)+C-1;Size^2)+1));
 fnRandomize;LAMBDA(Size;Matrix;LET(A;fnList(fnList;Size);INDEX(A;Matrix;1)));
 fnRandomizeIterator;LAMBDA(This;Size;Matrix;Iterations;WENN(ZEILEN(Iterations)>1;This(This;Size;Matrix;INDEX(Iterations;SEQUENZ(ZEILEN(Iterations)-1)));Matrix));
 fnArgument;LAMBDA(Value;Lower;Upper;Default;LET(X;WENN(ISTLEER(Value);Default;Value);Y;WENN(ZEILEN(X)*SPALTEN(X)>1;WENNFEHLER(--INDEX(X;1;1);Default);
 WENNFEHLER(--X;Default));WENN((Y>Lower-1)*(Y<Upper+1);Y;Default)));
 fnExpand;LAMBDA(Left;Right;LET(N;SPALTEN(Left)+SPALTEN(Right);A;SEQUENZ(ZEILEN(Left);N);R;AUFRUNDEN(A/N;0);C;WENN(REST(A;N)>0;REST(A;N);N);
 WENN(C>SPALTEN(Left);INDEX(Right;R;C-SPALTEN(Left));Left)));
 vnSolution;fnArgument(Solution;0;1;0);
 vnSize;fnArgument(Size;3;9;3);
 vnRemovals;LET(M;ZUFALLSMATRIX(vnSize^2;vnSize^2;0;1;WAHR);WENN(vnSolution>0;fnExpand(M;SEQUENZ(vnSize^2;vnSize^2;1;0));M));
 vnValues;LET(M;fnRandomizeIterator(fnRandomizeIterator;vnSize;fnRandomize(vnSize;fnInitialize(vnSize));SEQUENZ(vnSize+1));WENN(vnSolution>0;fnExpand(M;M);M));
 LET(M;vnValues*vnRemovals;WENN(M>0;M;""))))(3;1) 


Das Argument Size entspricht der Größe des Spielfeldes (zwischen 3 und 9) und das Argument Solution gibt an, ob neben
dem generierten Sudoku mit den leeren Feldern das vollständige Sudoku (also Lösung) angezeigt werden soll. Da nun mal
Formel, wird logischerweise bei jeder Änderung einer Zelle das Sudoku neu berechnet.

   

Wie funktioniert's? Es wird ein Basis-Sudoko bzw. eine Basis-Matrix als Zahlenfolge generiert, wo dann die Zahlen per MOD
und REST-Berechnungen verschoben werden. Danach werden dann die Zahlen per Zufall mehrfach vertauscht. Eigentlich
recht simpel. Am Ende werden dann die leeren Felder ebenfalls per Zufall bestimmt. Werde demnächst mal einen Artikel
dazu publizieren.

Ich versuche mich demnächst mal an einem Algorithmus zur Lösung eines beliebigen Sudokus. Kann aber gut sein, dass das
nicht oder nur unter Randbedingungen umsetzbar ist, da die Anzahl der Iterationen in LAMBDAs limitiert ist. Mal gucken.

Gruß

[LCohen]

Sehr schön! 

Mein 85j Vater löst gern mal Sudoku. Wenn ich ihm von meinem 365 Family eins abgebe, könnte er also endlos lösen.

Der technische Ansatz sieht fortgeschritten aus. Ob ich mir das mal reinziehe?

[maninweb]

Moin,

Danke! Wenn's Opa eine Freude macht, klaro. Würde dann vielleicht noch ein Makro bauen, die die Sudokus immer statisch von A nach B kopieren.
Reinziehen? Warum nicht? Vielleicht kann man's noch optimieren. Problem bei Lambdas ist z.B. bei einer Matrix, dass innerhalb von Iterationen
anscheinend nicht auf komplette Spalten/Zeilen zugegriffen werden kann. Daher übergebe ich dann immer die Matrix als Ganzes.

Übrigens, interessant finde ich, dass um per Zufall die Zahlen 1 bis 9 (3^2) zu generieren eine 3^4 Zufallsliste reicht, also die Rekursion kurz bleibt.

Hatte übrigens einiges zu Sudokus gelesen, wirklich interessant, wofür man die, ausser Spielen, noch verwenden kann. Bemerkenswert, wieviele
Studien usw. es dazu gibt. Die meisten verwenden einen Backtracing Algorithmus zum Generieren von Sudokus mit nur einer Lösung, das ist mit
LAMBDAs aber nicht machbar. Hier mal ein paar Links, allerdings alle in Englisch:

https://medcraveonline.com/BBIJ/BBIJ-07-00251.pdf (brachte mich auf die Idee mit dem Verschieben von Zahlen)
https://sites.math.washington.edu/~morro...am2280.pdf
http://www.afjarvis.staff.shef.ac.uk/sudoku/sudoku.pdf
http://rosettacode.org/wiki/Random_Latin_squares
https://lvngd.com/blog/generating-and-so...es-python/
https://sites.math.washington.edu/~morro...am2280.pdf

Gruß

[LCohen]

Sudoku ist eigentlich die Erziehung par excellence dazu, Dinge in einer bestimmten Reihenfolge zu erledigen. Wobei man diese Reihenfolge dort erst finden muss. Somit ist jedes Sudoku auch eine Art neues Problem.

Das mit den generell in Excel nicht möglichen dynamischen Zwischenergebnissen stört mich bei LAMBDA auch schon öfters:

Gegeben sei ein Datenfeld A1:D5. Jetzt würde ich es gern mit einer einzigen dynamischen Formel in E1:E5: =SUMME(dyn:SEQUENZ(5);ZS[-4]:ZS[-1]) vervollständigen. Das heißt: Die dynamische Dimension ist die andere, bezogen auf den Bezug. Sie wäre in den vorhandenen Funktionen als z.B. erstes Argument zu verwenden.

[LCohen]

  210712 Sudoku maninweb.xlsx (Größe: 14,17 KB / Downloads: 3)

ist ein 9x9-Sudoku, davon gleich 6 Stück auf ein DIN-A4. Linien etwas dicker, da mein Vater meinte, er müsse sie nachzeichnen. Er faltet sie und nimmt sie mit für unterwegs.

Mir fällt auf, dass die Zahlen nicht ganz zufällig scheinen. In (fast) jedem einzelnen SUDOKU gibt es 3 oder 4 horizontale Zahlenpärchen, manchmal auch mehrere. Also müsstest Du noch ein paar Spalten mehr tauschen (geht wiederum mit einer einzigen Anweisung, abgewandelt als =INDEX(A1:I9;SEQUENZ(9);SORTIERENNACH(SEQUENZ(;9);ZUFALLSMATRIX(;9))) von RPP63).

Hier sind die 2 ersten von 12 SUDOKUs in Leserichtung der folgenden Word-Datei genannt:


  210712 Sudoku.docx (Größe: 22,65 KB / Downloads: 3)

Sudoku1
4x 2-leer-6, 3x 6-4

Sudoku2
3x 1-6, 3x leer-7

usw.

[maninweb]

Moin,

vielen Dank!

Ich denke mal, dass ZUFALLSMATRIX in Schleife nicht wirklich Zufallszahlen erzeugt. Eigentlich müsste ein besserer Zufallsgenerator her.
Aktuell tausche ich keine Spalten, sondern Positionen von Zahlen. Zum Beispiel wird aus 3 eine 6 usw. Dies mehrfach hintereinander.
Ich schau' mal, ob ich die Formel von RPP63 eingebaut bekomme.

Gruß

[LCohen]

Mathematisch ist ZUFALLS[ZAHL|BEREICH|MATRIX] sicherlich nicht vollkommen. Du könntest so aber auch mehrere abwechselnde Spalten- und Zeilenmischer am Ende Deiner Berechnungen vorsehen. Das ist dann so wie Rubik's Cube, nur in 2D statt 3D.

[LCohen]

Sinnvoll wäre noch eine Leerspalte zwischen Rätsel und Lösung. Dann kann man letztere besser nach hinten knicken.

Ich habe fast noch nie Sudoku gespielt. Ich wusste daher gar nicht, dass es (bei 9x9) neben Z und S auch noch 3x3 zu beachten gilt. Entsprechend wäre natürlich die Spaltentauscherei anzupassen.

Anbei die Datei mit der etwas abgerückten Lösung von den 3 Sudokus auf einem A4.


  210712 Sudoku maninweb.xlsx (Größe: 23,58 KB / Downloads: 3)

Ich nehme die Markierung (nach F9) und füge sie als Grafik in Word ein.

[maninweb]

Hallo,

das mit der Leerspalte lässt sich recht einfach lösen. Hab's mal umgebaut, sodass jetzt das dritte Argument Margin angibt,
wieviele Spalten Abstand (zwischen 0 und 3) die Lösung zum Spielfeld hat. Das sieht dann so aus:

PHP-Code:

=LAMBDA(Size;Solution;Margin;LET(
 fnList;LAMBDA(This;Size;LET(A;EINDEUTIG(ZUFALLSMATRIX(Size^4;1;1;Size^2;WAHR));WENN(WENNFEHLER(ZEILEN(A);0)<Size^2;This(This;Size);A)));
 fnInitialize;LAMBDA(Size;LET(A;SEQUENZ(Size^2);M;SEQUENZ(Size^2;Size^2);R;AUFRUNDEN(M/Size^2;0);C;WENN(REST(M;Size^2)>0;REST(M;Size^2);Size^2);
 REST(ABRUNDEN((R-1)/Size;0)+Size*REST(R-1;Size)+C-1;Size^2)+1));
 fnRandomize;LAMBDA(Size;Matrix;LET(A;fnList(fnList;Size);INDEX(A;Matrix;1)));
 fnRandomizeIterator;LAMBDA(This;Size;Matrix;Iterations;WENN(ZEILEN(Iterations)>1;This(This;Size;Matrix;INDEX(Iterations;SEQUENZ(ZEILEN(Iterations)-1)));Matrix));
 fnArgument;LAMBDA(Value;Lower;Upper;Default;LET(X;WENN(ISTLEER(Value);Default;Value);Y;WENN(ZEILEN(X)*SPALTEN(X)>1;WENNFEHLER(--INDEX(X;1;1);Default);
 WENNFEHLER(--X;Default));WENN((Y>Lower-1)*(Y<Upper+1);Y;Default)));
 fnExpand;LAMBDA(Left;Right;Margin;LET(N;Margin+SPALTEN(Left)+SPALTEN(Right);A;SEQUENZ(ZEILEN(Left);N);R;AUFRUNDEN(A/N;0);C;WENN(REST(A;N)>0;REST(A;N);N);
 WENN(C>SPALTEN(Left)+Margin;INDEX(Right;R;C-SPALTEN(Left)-Margin);WENN(C>SPALTEN(Left);0;Left))));
 vnSize;fnArgument(Size;3;9;3);
 vnSolution;fnArgument(Solution;0;1;0);
 vnMargin;fnArgument(Margin;0;3;1);
 vnRemovals;LET(M;ZUFALLSMATRIX(vnSize^2;vnSize^2;0;1;WAHR);WENN(vnSolution>0;fnExpand(M;SEQUENZ(vnSize^2;vnSize^2;1;0);vnMargin);M));
 vnValues;LET(M;fnRandomizeIterator(fnRandomizeIterator;vnSize;fnRandomize(vnSize;fnInitialize(vnSize));SEQUENZ(2*vnSize^2+1));WENN(vnSolution>0;fnExpand(M;M;vnMargin);M));
 vnResult;LET(M;vnValues*vnRemovals;WENN(M>0;M;""));vnResult))(3;1;1) 


Ausserdem habe ich mal die Anzahl der Interationen zum Vertauschen von Werten erhöht, die jetzt bei 2*vnSize^2+1 liegt (18+1).
Das scheint das Problem mit den Pärchen zu reduzieren. Die Spalten oder Zeilen per Zufall vertauschen kann ich nicht, denn dann
ergibt das durchaus mal Blöcke (3x3), wo dann Zahlen mehrfach drin vorkommen.

Gruß

[LCohen]

Margin: Schön! Aber 1 Fixspalte hätte sicherlich gereicht, damit es bei 2 Argumenten bliebe.

Spaltensortieren: Das stimmt. Bei 3x3 innerhalb von 9x9 dürften nur 6 Sorts (3!) 

123
132
213
231
312
321

bzw. 216= 3!^3 über das ganze Sudoku erlaubt sein, also je 3 Zeilen sortiert über 9 Spalten oder je 3 Spalten sortiert über 9 Zeilen.

Man würde die Lösung nehmen und das Vorhandensein von Pärchen addieren. Das Minimum (evtl. ein lokales Minimum) gewönne dann.

Code:

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

Deine Lösungen sind in der Ausgangsversion (die neueste habe ich noch nicht geprüft) übrigens völlig vorhersehbar in Zeilen (9 Wdh! Ich hatte die Lösungsmatrix gar nicht angeschaut und das erst jetzt gesehen!). Schau es Dir nochmal genau an. In jeder Zeile gibt es 326487591 in der gleichen Reihenfolge, nur an bestimmten anderen Einspringpunkten (mit Überlappung nach vorn zurück). Es MUSS also sogar permutiert werden.

Mit anderen Worten: Man würde gar nicht ein Sudoku lösen, sondern nur eine 9-Ziffernfolge ab jeweils z.B. der 1 richtig in die nach vorn überlaufende Zeile einsetzen:

Code:

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

In Spalten verhält es sich etwas "tauschmäßiger", aber immer noch unpermutiert im Kleinen: Ein 3er-Zeilenblock einer Spalte kommt also unpermutiert immer auf die Folgen 3-4-5, 4-5-3, 5-3-4 (immer aufsteigend bis Ende, aber keinmal absteigend 5-4-3, 4-3-5 oder 3-5-4).

Das Rezept zum korrekten Mischen lautet also:

Mische Zeilen 1:3 unter sich (und/oder 4:6 und/oder 7:9 unter sich)
Mische Spalten 1:3 unter sich (und/oder 4:6 und/oder 7:9 unter sich)
Beginne wieder bei 1, 2 oder 3 der Zeilenblöcke, usw.

Wiederhole dies einige Male.

S1:Z9: =SUMMENPRODUKT(($J$2:$Q$10=J2)*($K$2:$R$10=K2)) - kopiert in 8x9 und dies dann summiert mit 
AA1: =SUMME(S1:Z9) - sollte "niedrig" oder "minimal" werden.