A better/good way to generate 4x4x4 Sudoku board?

Question

For fun when I have time, I like to code games to see how hard it is or just because I want to see how it works from the inside or just for personal challenge. I just like coding. For now, I made these ones.

So I made a Sudoku board. First it was the normal 3x3x3 board but then someone asked me to do a 4x4x4 board. I was successful but my algorithm is pretty slow.

The question is, how would you do a fast algorithm for a 4x4x4 (or more) Sudoku board?

My current algorithm works like this: I will fill grid 1 with a random number, making sure I don't put back the same number, then switch to grid 2. When I'm in the position 0.0 or any other one in the grid I remove any possible number from grid 1. I go on like that for every line/column in the grid. (By now you can see that English is not my first language so I'm sorry if it's hard to understand.)

---

Update:
a little followup, a few months later.

My current solution can be found here

So when I started this question, it as doing 1 grid every 30-50 seconds and now it's over 300 per seconds

Answer 1

What is your current algorithm?

I imagine the algorithms discussed on Wikipedia's Algorithmics of sudoku page could be expanded to 4x4x4.

Answer 2

A Sudoku Generator written in Python is available. An explanation (algorithm) on how the author generates the Sudoku boards is on that page, and the source code is provided.

Answer 3

Consider the following grid:

 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

Assuming that I haven't made any typos, it should be obvious (from the pattern of its construction) that this follows the requirements of a Sudoku layout (each value 1..16 occurs exactly once in each row, column, and 4x4 subgrid).

In addition, it should be obvious that each of the following changes leaves the requirements satisfied (where 1-origin indexing is assumed):

1. Column swaps: exchange the entire contents of any two columns that lie within the same subgrid (e.g. swapping cols 1 and 3, swapping cols 10 and 11, but not swapping cols 6 and 13).

2. Row swaps: exchange the entire contents of any two columns that lie within the same subgrid (similar indexing to #1).

3. Subgrid column swaps: exchange corresponding columns of two columns of subgrids (e.g. swap subgrid cols 2 and 4, which means swapping all of cols 5 and 13, cols 6 and 14, cols 7 and 15, and cols 8 and 16).

4. Subgrid row swaps: exchange corresponding rows of two rows of subgrids (similar indexing to #3).

So, based on the above facts, the strategy is to begin with the grid shown above, then for some suitable number of iterations (you can determine this by experiment), randomly choose one of the four transforms, and apply it to randomly-chosen indices that satisfy the requirements stated for the transform.

For example, to apply transform #1, randomly choose a subgrid column number sgcn in the range (1..4), then randomly choose two distinct column numbers cn1 and cn2 in the range (1..4). Swap all values in columns (sgcn - 1) * 4 + cn1 and (sgcn - 1) * 4 + cn2.

By starting with a (any) legal grid, and performing legality-preserving transformations, the result is guaranteed to be legal. However, as the number of transforms applied increases, it is progressively more difficult for a human observer to distinguish the pattern from randomness.

Replacing values in the "scrambled" grid with blanks to get the desired degree of difficulty.

Answer 4

this is the code for joel.neely suggestion

pass 3 for 3x3x3, 4 for 4x4x4, etc

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 I found out why it was so fast with a 3x3x3 but really slow with the 4x4x4

it was my back-tracking logic, it was very bad, now it take maximum 20 seconds (at least with my computer) most of them take less than 5 seconds