Ein besserer Weg, um ein 4x4x4 Sudoku Brett zu erstellen?

Question

Wenn ich Zeit habe, programmiere ich zum Spaß gerne Spiele, um zu sehen, wie schwer es ist, oder einfach nur, weil ich sehen will, wie es von innen heraus funktioniert, oder um mich persönlich herauszufordern. Ich programmiere einfach gern. Im Moment habe ich diese .

Also habe ich ein Sudoku-Brett gemacht. Zuerst war es das normale 3x3x3 Brett, aber dann bat mich jemand, ein 4x4x4 Brett zu machen. Ich war erfolgreich, aber mein Algorithmus ist ziemlich langsam.

Die Frage ist, Wie würde man einen schnellen Algorithmus für ein 4x4x4 (oder mehr) Sudoku-Brett erstellen? ?

Mein derzeitiger Algorithmus funktioniert folgendermaßen: Ich fülle Gitter 1 mit einer zufälligen Zahl, wobei ich darauf achte, dass ich nicht wieder dieselbe Zahl eintrage, und wechsle dann zu Gitter 2. Wenn ich an der Position 0,0 oder einer anderen im Gitter bin, entferne ich jede mögliche Zahl aus Gitter 1. So mache ich für jede Zeile/Spalte im Gitter weiter. (Wie Sie sehen, ist Englisch nicht meine Muttersprache, also tut es mir leid, wenn es schwer zu verstehen ist).

---

Aktualisierung:
ein paar Monate später eine kleine Nachbereitung.

Meine aktuelle Lösung finden Sie hier aquí

Als ich mit dieser Frage begann, wurde alle 30-50 Sekunden ein Raster erstellt, jetzt sind es über 300 pro Sekunde.

Answer 1

Betrachten Sie das folgende Raster:

 1  2  3  4 |  5  6  7  8 |  9 10 11 12 | 13 14 15 16
 5  6  7  8 |  9 10 11 12 | 13 14 15 16 |  1  2  3  4
 9 10 11 12 | 13 14 15 16 |  1  2  3  4 |  5  6  7  8
13 14 15 16 |  1  2  3  4 |  5  6  7  8 |  9 10 11 12
------------+-------------+-------------+------------
 2  3  4  1 |  6  7  8  5 | 10 11 12  9 | 14 15 16 13
 6  7  8  5 | 10 11 12  9 | 14 15 16 13 |  2  3  4  1
10 11 12  9 | 14 15 16 13 |  2  3  4  1 |  6  7  8  5
14 15 16 13 |  2  3  4  1 |  6  7  8  5 | 10 11 12  9
------------+-------------+-------------+------------
 3  4  1  2 |  7  8  5  6 | 11 12  9 10 | 15 16 13 14
 7  8  5  6 | 11 12  9 10 | 15 16 13 14 |  3  4  1  2
11 12  9 10 | 15 16 13 14 |  3  4  1  2 |  7  8  5  6
15 16 13 14 |  3  4  1  2 |  7  8  5  6 | 11 12  9 10
------------+-------------+-------------+------------
 4  1  2  3 |  8  5  6  7 | 12  9 10 11 | 16 13 14 15
 8  5  6  7 | 12  9 10 11 | 16 13 14 15 |  4  1  2  3
12  9 10 11 | 16 13 14 15 |  4  1  2  3 |  8  5  6  7
16 13 14 15 |  4  1  2  3 |  8  5  6  7 | 12  9 10 11

Wenn ich davon ausgehe, dass ich keine Tippfehler gemacht habe, sollte es offensichtlich sein (aus dem Muster des Aufbaus), dass dies den Anforderungen eines Sudoku-Layouts entspricht (jeder Wert 1..16 kommt genau einmal in jeder Zeile, Spalte und jedem 4x4-Untergitter vor).

Darüber hinaus sollte es offensichtlich sein, dass jede der folgenden Änderungen die Anforderungen erfüllt (wenn eine 1-Ursprungs-Indexierung angenommen wird):

1. Austausch von Spalten Tauschen Sie den gesamten Inhalt zweier beliebiger Spalten aus, die in demselben Untergitter liegen (z. B. Vertauschen der Spalten 1 und 3, Vertauschen der Spalten 10 und 11, aber no Vertauschen der Spalten 6 und 13).

2. Austausch von Zeilen Tauschen Sie den gesamten Inhalt zweier Spalten aus, die im selben Untergitter liegen (ähnliche Indizierung wie bei #1).

3. Vertauschen von Untergitterspalten Tauschen Sie die entsprechenden Spalten zweier Spalten von Unterrastern aus (z. B. tauschen Sie die Spalten 2 und 4 des Unterrasters, was bedeutet, dass Sie alle Spalten 5 und 13, 6 und 14, 7 und 15 sowie 8 und 16 tauschen).

4. Austausch von Teilgitterzeilen Austausch der korrespondierenden Zeilen zweier Reihen von Teilrastern (ähnliche Indizierung wie bei #3).

Auf der Grundlage der obigen Fakten besteht die Strategie also darin, mit dem oben gezeigten Raster zu beginnen, dann für eine geeignete Anzahl von Iterationen (die Sie durch Experimentieren ermitteln können) eine der vier Transformationen zufällig auszuwählen und sie auf zufällig ausgewählte Indizes anzuwenden, die die für die Transformation angegebenen Anforderungen erfüllen.

Um z. B. Transformation Nr. 1 anzuwenden, wählen Sie eine zufällige Teilgitter-Spaltennummer sgcn im Bereich (1..4), dann wählen Sie zufällig zwei unterschiedliche Spaltennummern cn1 y cn2 im Bereich (1..4). Tausche alle Werte in den Spalten (sgcn - 1) * 4 + cn1 y (sgcn - 1) * 4 + cn2 .

Wenn man von einem (beliebigen) legalen Gitter ausgeht und gesetzeskonforme Transformationen durchführt, ist das Ergebnis garantiert legal. Mit zunehmender Anzahl der angewandten Transformationen wird es jedoch für einen menschlichen Beobachter immer schwieriger, das Muster vom Zufall zu unterscheiden.

Ersetzen von Werten im "verschlüsselten" Raster durch Leerzeichen, um den gewünschten Schwierigkeitsgrad zu erreichen.

Answer 2

Was ist Ihr aktueller Algorithmus?

Ich stelle mir vor, dass die Algorithmen, die auf der Wikipedia-Seite Algorithmik des Sudoku Seite könnte auf 4x4x4 erweitert werden.

Answer 3

A Sudoku-Generator die in Python geschrieben wurde, ist verfügbar. Eine Erklärung (Algorithmus), wie der Autor die Sudoku-Tafeln erzeugt, ist auf dieser Seite zu finden, und der Quellcode wird zur Verfügung gestellt.

Answer 4

Dies ist der Code für den Vorschlag von joel.neely

Pass 3 für 3x3x3, 4 für 4x4x4, usw.

Public Class Class1

Private aSquare(,,) As Integer
Private iSquare As Integer

Sub New(ByVal squareSize As Integer)

    iSquare = squareSize
    ReDim aSquare(iSquare - 1, iSquare - 1, CInt(iSquare ^ 2 - 1))

    createSquare()
    rndSquare()

End Sub

Private Sub createSquare()
    Dim i As Integer, j As Integer, k As Integer

    For i = 0 To aSquare.GetUpperBound(0)
        For j = 0 To aSquare.GetUpperBound(1)
            For k = 0 To aSquare.GetUpperBound(2)
                If i = 0 And j = 0 Then
                    aSquare(i, j, k) = k + 1
                ElseIf j = 0 And i > 0 Then
                    If (k + i) Mod (iSquare) = 0 Then
                        aSquare(i, j, k) = aSquare(i - 1, j, k) - (iSquare - 1)

                    Else
                        aSquare(i, j, k) = aSquare(i - 1, j, k) + 1
                    End If
                Else
                    aSquare(i, j, k) = aSquare(i, j - 1, k) + iSquare
                End If

                If aSquare(i, j, k) > iSquare ^ 2 Then
                    aSquare(i, j, k) = aSquare(i, j, k) - CInt(iSquare ^ 2)
                End If
            Next
        Next
    Next
End Sub

Private Sub rndSquare()
    Dim i As Integer

    Randomize()

    For i = 0 To CInt(iSquare ^ 2)

        Select Case CInt(Rnd() * 3)
            Case 0
                rndBigCol()
            Case 1
                rndBigRow()
            Case 2
                rndLittleCol()
            Case 3
                rndlittleRow()
        End Select

    Next

End Sub

Private Sub rndBigCol()
    Dim square As Integer
    Dim rnd1, rnd2 As Integer
    Dim i As Integer, j As Integer, k As Integer

    Randomize()

    For k = 0 To iSquare
        Do
            rnd1 = CInt(Rnd() * aSquare.GetUpperBound(1))
            rnd2 = CInt(Rnd() * aSquare.GetUpperBound(1))
        Loop Until rnd1 <> rnd2

        For i = 0 To aSquare.GetUpperBound(0)
            For j = 0 To aSquare.GetUpperBound(2)
                square = aSquare(i, rnd1, j)
                aSquare(i, rnd1, j) = aSquare(i, rnd2, j)
                aSquare(i, rnd2, j) = square
            Next
        Next
    Next
End Sub

Private Sub rndBigRow()
    Dim square As Integer
    Dim rnd1, rnd2 As Integer
    Dim i As Integer, j As Integer, k As Integer

    Randomize()

    For k = 0 To iSquare
        Do
            rnd1 = CInt(Rnd() * aSquare.GetUpperBound(0))
            rnd2 = CInt(Rnd() * aSquare.GetUpperBound(0))
        Loop Until rnd1 <> rnd2

        For i = 0 To aSquare.GetUpperBound(1)
            For j = 0 To aSquare.GetUpperBound(2)
                square = aSquare(rnd1, i, j)
                aSquare(rnd1, i, j) = aSquare(rnd2, i, j)
                aSquare(rnd2, i, j) = square
            Next
        Next
    Next
End Sub

Private Sub rndLittleCol()
    Dim square As Integer
    Dim rnd1, rnd2, rnd3 As Integer
    Dim i As Integer, k As Integer, l As Integer

    Randomize()

    For k = 0 To iSquare * 2
        Do
            rnd1 = CInt(Rnd() * aSquare.GetUpperBound(1))
            rnd2 = CInt(Rnd() * (iSquare - 1))
            rnd3 = CInt(Rnd() * (iSquare - 1))
        Loop Until rnd2 <> rnd3

        For i = 0 To aSquare.GetUpperBound(0)
            For l = 0 To (iSquare - 1)
                square = aSquare(i, rnd1, rnd2 + (l * iSquare))
                aSquare(i, rnd1, rnd2 + (l * iSquare)) = aSquare(i, rnd1, rnd3 + (l * iSquare))
                aSquare(i, rnd1, rnd3 + (l * iSquare)) = square
            Next
        Next
    Next
End Sub

Private Sub rndlittleRow()
    Dim square As Integer
    Dim rnd1, rnd2, rnd3 As Integer
    Dim j As Integer, k As Integer, l As Integer

    Randomize()

    For k = 0 To iSquare * 2
        Do
            rnd1 = CInt(Rnd() * aSquare.GetUpperBound(0))
            rnd2 = CInt(Rnd() * (iSquare - 1))
            rnd3 = CInt(Rnd() * (iSquare - 1))
        Loop Until rnd2 <> rnd3

        rnd2 *= iSquare
        rnd3 *= iSquare

        For j = 0 To aSquare.GetUpperBound(1)
            For l = 0 To (iSquare - 1)
                square = aSquare(rnd1, j, rnd2 + l)
                aSquare(rnd1, j, rnd2 + l) = aSquare(rnd1, j, rnd3 + l)
                aSquare(rnd1, j, rnd3 + l) = square
            Next
        Next
    Next
End Sub
End Class

Answer 5

Ok, ich habe herausgefunden, warum es mit einem 3x3x3 so schnell war, aber mit dem 4x4x4 so langsam

es war meine Rückverfolgungslogik, sie war sehr schlecht, jetzt dauert es maximal 20 Sekunden (zumindest bei meinem Computer), die meisten brauchen weniger als 5 Sekunden