[LAMBDA] SUDOKU Generator

[maninweb]

Hallo,

kommt noch - muss es ja erst selbst zusammenbauen ;-)

Gruß

[maninweb]

Hallo,

hier dann der aktuelle Zwischenstand in vollständiger Form als Formel hier unten und in der Datei im Anhang.
Es fehlen noch die Permutationen als solches, die in fnSudokuPermutation vorgesehen sind, aber noch nichts machen.

PHP-Code:

=LAMBDA(Size;Solution;Margin;LET(
 fnArgument;LAMBDA(Value;Min;Max;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>Min-1)*(Y<Max+1);Y;Default)));
 fnRow;LAMBDA(Value;Height;AUFRUNDEN(Value/Height;0));
 fnColumn;LAMBDA(Value;Width;WENN(REST(Value;Width)>0;REST(Value;Width);Width));
 fnExpand;LAMBDA(Left;Right;Margin;LET(N;Margin+SPALTEN(Left)+SPALTEN(Right);M;SEQUENZ(ZEILEN(Left);N);R;fnRow(M;N);C;fnColumn(M;N);
 WENN(C>SPALTEN(Left)+Margin;INDEX(Right;R;C-SPALTEN(Left)-Margin);WENN(C>SPALTEN(Left);0;Left))));
 fnPairsGet;LAMBDA(Matrix;LET(S;SEQUENZ(ZEILEN(Matrix);SPALTEN(Matrix)-1);R;fnRow(S;SPALTEN(Matrix)-1);C;fnColumn(S;SPALTEN(Matrix)-1);M;INDEX(Matrix;R;C)&INDEX(Matrix;R;C+1);--M));
 fnPairs;LAMBDA(This;Pairs;Matrix;Iteration;WENN(Iteration>0;This(This;Pairs;Matrix*LET(M;SEQUENZ(ZEILEN(Matrix);SPALTEN(Matrix));R;fnRow(M;SPALTEN(M));C;fnColumn(M;SPALTEN(M));
 T;"."&TEXTVERKETTEN(".";1;Pairs)&".";V;"."&INDEX(Pairs;R;C)&".";WENN(M=Iteration;(LÄNGE(T)-LÄNGE(WECHSELN(T;V;"")))/LÄNGE(V);1));Iteration-1);Matrix));
 fnRandomList;LAMBDA(This;Min;Max;LET(A;EINDEUTIG(ZUFALLSMATRIX((Max-Min+1)^2;1;Min;Max;WAHR));WENN(WENNFEHLER(ZEILEN(A);0)<Max-Min+1;This(This;Min;Max);A)));
 fnRandomListEx;LAMBDA(This;Matrix;Size;Iteration;WENN(Iteration>0;This(This;LET(S;SEQUENZ(Size^2);N;Size*Iteration;A;fnRandomList(fnRandomList;N-Size+1;N);
 Matrix+WENN((S>N-Size)*(S<N+1);INDEX(A;S-N+Size;1);0));Size;Iteration-1);Matrix));
 fnSudokuInitialize;LAMBDA(Size;LET(M;SEQUENZ(Size^2;Size^2);R;fnRow(M;Size^2);C;fnColumn(M;Size^2);REST(ABRUNDEN((R-1)/Size;0)+Size*REST(R-1;Size)+C-1;Size^2)+1));
 fnSudokuBase;LAMBDA(This;Size;Matrix;Iteration;WENN(Iteration>0;This(This;Size;LET(A;fnRandomList(fnRandomList;1;Size^2);INDEX(A;Matrix;1));Iteration-1);Matrix));
 fnSudokuPermutation;LAMBDA(Matrix;LET(M;Matrix;M));
 fnSudokuResult;LAMBDA(This;Matrix;Size;Iteration;LET(S;SUMME(fnPairs(fnPairs;fnPairsGet(Matrix);SEQUENZ(ZEILEN(Matrix);SPALTEN(Matrix)-1;1;0);ZEILEN(Matrix)*SPALTEN(Matrix)));
 WENN(ODER(Iteration>Size^2;S<2*(Size^4-Size^2));Matrix;This(This;fnSudokuPermutation(Matrix);Size;Iteration+1))));
 vnSize;fnArgument(Size;3;9;3);
 vnSolution;fnArgument(Solution;0;1;0);
 vnMargin;fnArgument(Margin;0;3;0);
 vnSudoku;LET(M;fnSudokuResult(fnSudokuResult;fnSudokuBase(fnSudokuBase;vnSize;fnSudokuInitialize(vnSize); vnSize);vnSize;1);WENN(vnSolution>0;fnExpand(M;M;vnMargin);M));
 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));
 LET(M;vnSudoku*vnRemovals;WENN(M>0;M;""))))(3;1;0) 


Gruß

[maninweb]

Servus,

die Formel ist jetzt vollständig. Als Abbruchbedingung für die Permutation ist dann so gesetzt, dass kein Pärchen mehr als 2 mal auftreten darf.
Es kann durchaus (selten) vorkommen, dass #KALK! als Ergebnis zurückgegeben wird. Dann einfach F9 drücken. Wenn die Abbruchbedingung
auf 1 gesetzt wird, steigt die Formel aus. Wobei ich nicht weiss, ob das überhaupt geht; also keine Pärchen.

PHP-Code:

=LAMBDA(Size;Solution;Margin;LET(
 fnArgument;LAMBDA(Value;Min;Max;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>Min-1)*(Y<Max+1);Y;Default)));
 fnRow;LAMBDA(Value;Height;AUFRUNDEN(Value/Height;0));
 fnColumn;LAMBDA(Value;Width;WENN(REST(Value;Width)>0;REST(Value;Width);Width));
 fnExpand;LAMBDA(Left;Right;Margin;LET(n;Margin+SPALTEN(Left)+SPALTEN(Right);M;SEQUENZ(ZEILEN(Left);n);R;fnRow(M;n);C;fnColumn(M;n);
 WENN(C>SPALTEN(Left)+Margin;INDEX(Right;R;C-SPALTEN(Left)-Margin);WENN(C>SPALTEN(Left);0;Left))));
 fnPairsGet;LAMBDA(Matrix;LET(S;SEQUENZ(ZEILEN(Matrix);SPALTEN(Matrix)-1);R;fnRow(S;SPALTEN(Matrix)-1);C;fnColumn(S;SPALTEN(Matrix)-1);M;INDEX(Matrix;R;C)&INDEX(Matrix;R;C+1);--M));
 fnPairs;LAMBDA(This;Pairs;Matrix;Iteration;WENN(Iteration>0;This(This;Pairs;Matrix*LET(M;SEQUENZ(ZEILEN(Matrix);SPALTEN(Matrix));R;fnRow(M;SPALTEN(M));C;fnColumn(M;SPALTEN(M));T;"."&
 TEXTVERKETTEN(".";1;Pairs)&".";V;"."&INDEX(Pairs;R;C)&".";WENN(M=Iteration;(LÄNGE(T)-LÄNGE(WECHSELN(T;V;"")))/LÄNGE(V);1));Iteration-1);Matrix));
 fnRandomList;LAMBDA(This;Min;Max;LET(A;EINDEUTIG(ZUFALLSMATRIX((Max-Min+1)^2;1;Min;Max;WAHR));WENN(WENNFEHLER(ZEILEN(A);0)<Max-Min+1;This(This;Min;Max);A)));
 fnRandomListEx;LAMBDA(This;Matrix;Size;Iteration;WENN(Iteration>0;This(This;LET(S;SEQUENZ(Size^2);n;Size*Iteration;A;fnRandomList(fnRandomList;n-Size+1;n);
 Matrix+WENN((S>n-Size)*(S<n+1);INDEX(A;S-n+Size;1);0));Size;Iteration-1);Matrix));
 fnSudokuInitialize;LAMBDA(Size;LET(M;SEQUENZ(Size^2;Size^2);R;fnRow(M;Size^2);C;fnColumn(M;Size^2);REST(ABRUNDEN((R-1)/Size;0)+Size*REST(R-1;Size)+C-1;Size^2)+1));
 fnSudokuBase;LAMBDA(This;Size;Matrix;Iteration;WENN(Iteration>0;This(This;Size;LET(A;fnRandomList(fnRandomList;1;Size^2);INDEX(A;Matrix;1));Iteration-1);Matrix));
 fnSudokuPermutation;LAMBDA(Matrix;Size;Direction;LET(A;fnRandomListEx(fnRandomListEx;SEQUENZ(9;1;0;0);3;3);S;SEQUENZ(Size^2;Size^2);R;fnRow(S;Size^2);C;fnColumn(S;Size^2);
 WENN(Direction<1;INDEX(Matrix;R;INDEX(A;C;1));INDEX(Matrix;INDEX(A;R;1);C))));
 fnSudokuResult;LAMBDA(This;Matrix;Size;Iteration;LET(P;fnPairs(fnPairs;fnPairsGet(Matrix);SEQUENZ(ZEILEN(Matrix);SPALTEN(Matrix)-1;1;0);ZEILEN(Matrix)*SPALTEN(Matrix));
 WENN(SUMMENPRODUKT(--(P>2))<1;Matrix;This(This;fnSudokuPermutation(Matrix;Size;REST(Iteration;2));Size;Iteration+1))));
 vnSize;fnArgument(Size;3;9;3);
 vnSolution;fnArgument(Solution;0;1;0);
 vnMargin;fnArgument(Margin;0;3;0);
 vnSudoku;LET(M;fnSudokuResult(fnSudokuResult;fnSudokuBase(fnSudokuBase;vnSize;fnSudokuInitialize(vnSize); vnSize);vnSize;1);WENN(vnSolution>0;fnExpand(M;M;vnMargin);M));
 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));
 LET(M;vnSudoku*vnRemovals;WENN(M>0;M;""))))(3;1;1) 


Anbei dann die aktuellste Datei.

Gruß

[LCohen]

Hallo maninweb,

soweit war ich ja auch schon. Es ist kein Sudoku. 

Du bleibst jetzt dort stehen, wo in jedem 3er-Spaltenfeld immer die Inhalte konstant bleiben und nur in der Reihenfolge wechseln. Wenn also in einem der 27 3er-Spaltenfelder die Zahlen 1,8,9 auftauchen, dann tun sie das in anderer Reihenfolge in allen 8 weiteren auch (in denen eine 1 oder eine 8 oder eine 9 steht). Mit diesem Wissen ist die Lösung des Schein-Sudoku dann "über-einfach", und es kann definitiv auf sehr viele jetzt schon belegte Felder in der Rätselmatrix zusätzlich verzichtet werden.

Code:

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

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

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

Oben siehst Du, dass es ausschließlich 1-8-9 vertikal gibt. Aber z.B. nie 1-2-3, oder 1-4-6.

Die Rekursion von Kompf lässt sich also per LAMBDA vermutlich nicht nachbilden, weil LAMBDA dafür keine Kontrollstrukturen hat.

Kompf: https://www.kompf.de/sudoku/generator.html (dort "Generator", dann "lösen")

[maninweb]

Hallo,

ok, dann bringt das Permutieren letztlich nicht viel. Ich denke mal, dann bleibt nur das Verwenden eines bereits gelösten Sudokus
als Basis und nicht die in der Formel definierte Ausgangsreihenfolge der Zahlen. Das pflanzt sich so oder so fort. Ein gelöstes
Sudoku könnte ja insoweit durch Vertauschen von Zahlen, Zufallsleerstellen usw. modifiziert werden.

Ein Algo wie z.B. ein Backtracing-Algo ist mit LAMBDAs meines Erachtens nicht machbar, auch schon wegen der Begrenzung an
möglichen Iterationen. Das hatte ich schon probiert.

Gruß

[LCohen]

Vielleicht hast Du diesen Sudoku-Algo ja schon mal in VBA erfolgreich probiert? 

Dann würde sich die Gemeinde sicherlich über den Code freuen.

Oder man googelt nach einem Sudoku-VBA-Code. Manchmal kommen dabei Ideen, und dann kann man es über besondere Klimmzüge doch noch mit LAMBDA schaffen.

Den Laien (wie ich es einer bin) dürfte vermutlich folgendes interessieren:

1) Vermutlich muss zuerst die Lösung gebaut werden, oder?
2) Dann werden für die Rätselstellung aus der Lösung soviele Informationen entfernt, dass sie gerade noch eindeutig erstellbar ist. Oder noch mehr: Dann ist sie mehrdeutig.

Ist das richtig? Und nach welchem Algorithmus entfernt man verzichtbare Information?

[maninweb]

Hallo,

ich hatte ja relativ weit zu Beginn des Threads einige englische Links gepostet. Es gibt verschiedene Algorithmen, um Sudokus zu bauen, die aber letztlich alle rekursiv sind.
Die Rekursionen basieren wohl auch darauf, sich Zustände zu merken, das geht mit LAMBDAs eben halt wohl nicht. Manche Algos brauchen schon was länger, um Sudokus zu finden.
Manche nehmen auch dann den Ansatz aus einem bestehenden Sudokus ein neues zu bauen. Ich fand den Ansatz mit einer Zahlenreihe attraktiv, aber wie wir ja sehen, optimal ist das nicht.
Man könnte noch vielleicht diesen Algo hier versuchen. Wenn man in Excel eine Funktion hätte, die dynamisch neue Matrizen zur Laufzeit generieren könnte, wäre es einfacher.

Zu 1 & 2 von Dir: ja.

In VBA habe ich selber keins gemacht; sind aber welche im Netz zu finden, wobei eher welche, die ein Sudoku lösen.

Gruß