Today I stumbled on an program I had written years ago. During a hot summer I used to spend my time solving Sudoku puzzles at the beach - which is quite fun if you are in a must-not-work mode. Of course, very soon I found myself on my laptop, writing a program for creating and solving Sudoku puzzles. The algorithm for the creation of new puzzles is interesting, although probably not the most efficient, and surely someone else has thought it before me. In any case, I am sharing:
Algorithm description
Instead of using a brute-force method, it is possible to modify an existing Sudoku puzzle so that it remains valid. It turns out that any cell can be swapped with another one (in the same 3 x 3 matrix, of course), as long as the corresponding modifications are made along their rows or columns.
Any valid configuration can be used as seed (i.e. initial puzzle). For instance, we may want to use this one:
1 2 3 | 4 5 6 | 7 8 9
4 5 6 | 7 8 9 | 1 2 3
7 8 9 | 1 2 3 | 4 5 6
-----------------------
3 1 2 | 6 4 5 | 9 7 8
6 4 5 | 9 7 8 | 3 1 2
9 7 8 | 3 1 2 | 6 4 5
-----------------------
2 3 1 | 5 6 4 | 8 9 7
5 6 4 | 8 9 7 | 2 3 1
8 9 7 | 2 3 1 | 5 6 4
Suppose we want to swap the top-left cell ("1") with the one below it ("4"):
4 2 3 | 4 5 6 | 7 8 9
1 5 6 | 7 8 9 | 1 2 3
7 8 9 | 1 2 3 | 4 5 6
-----------------------
3 1 2 | 6 4 5 | 9 7 8
6 4 5 | 9 7 8 | 3 1 2
9 7 8 | 3 1 2 | 6 4 5
-----------------------
2 3 1 | 5 6 4 | 8 9 7
5 6 4 | 8 9 7 | 2 3 1
8 9 7 | 2 3 1 | 5 6 4
The new puzzle is invalid. For instance, there are two fours ("4") in the first row. We locate the other instance of "4" in the first row, and swap it with its counterpart in the second row:
4 2 3 | 7 5 6 | 7 8 9
1 5 6 | 4 8 9 | 1 2 3
7 8 9 | 1 2 3 | 4 5 6
-----------------------
3 1 2 | 6 4 5 | 9 7 8
6 4 5 | 9 7 8 | 3 1 2
9 7 8 | 3 1 2 | 6 4 5
-----------------------
2 3 1 | 5 6 4 | 8 9 7
5 6 4 | 8 9 7 | 2 3 1
8 9 7 | 2 3 1 | 5 6 4
We fixed the "4"'s, but now there are two "7"'s in the first row. We locate the other instance of "7" in the first row, which is located in the seventh column, and swap it with its counterpart in the second row:
4 2 3 | 7 5 6 | 1 8 9
1 5 6 | 4 8 9 | 7 2 3
7 8 9 | 1 2 3 | 4 5 6
-----------------------
3 1 2 | 6 4 5 | 9 7 8
6 4 5 | 9 7 8 | 3 1 2
9 7 8 | 3 1 2 | 6 4 5
-----------------------
2 3 1 | 5 6 4 | 8 9 7
5 6 4 | 8 9 7 | 2 3 1
8 9 7 | 2 3 1 | 5 6 4
It turns out that this counterpart ("1") is the same as the cell we originally swapped. This is the termination criterion, as the current state is a valid Sudoku puzzle.
Classic VB (vb6) code
The code is written in classic vb (vb6). I am afraid that I have the time to neither convert the code to .NET (although it is very easy) nor optimize it. So I will copy-paste it here, and hope not to be flamed for incompetent programming:
Private Sub BuildNewSudokuPuzzle()
Dim gA As Integer
Dim gB As Integer
Dim gC As Integer
Dim gStep As Integer
Dim gValue1 As Integer
Dim gValue2 As Integer
Dim gRow1 As Integer
Dim gRow2 As Integer
Dim gCol1 As Integer
Dim gCol2 As Integer
Dim gTargetValue As Integer
Dim gCellList(81) As Integer
Dim gOverallStep As Integer
'hard-code the initial state, which can be any valid sudoku puzzle
Dim iMatrix(9, 9) As Integer
iMatrix(1, 1) = 1: iMatrix(1, 2) = 2: iMatrix(1, 3) = 3: iMatrix(1, 4) = 4: iMatrix(1, 5) = 5: iMatrix(1, 6) = 6: iMatrix(1, 7) = 7: iMatrix(1, 8) = 8: iMatrix(1, 9) = 9
iMatrix(2, 1) = 4: iMatrix(2, 2) = 5: iMatrix(2, 3) = 6: iMatrix(2, 4) = 7: iMatrix(2, 5) = 8: iMatrix(2, 6) = 9: iMatrix(2, 7) = 1: iMatrix(2, 8) = 2: iMatrix(2, 9) = 3
iMatrix(3, 1) = 7: iMatrix(3, 2) = 8: iMatrix(3, 3) = 9: iMatrix(3, 4) = 1: iMatrix(3, 5) = 2: iMatrix(3, 6) = 3: iMatrix(3, 7) = 4: iMatrix(3, 8) = 5: iMatrix(3, 9) = 6
iMatrix(4, 1) = 3: iMatrix(4, 2) = 1: iMatrix(4, 3) = 2: iMatrix(4, 4) = 6: iMatrix(4, 5) = 4: iMatrix(4, 6) = 5: iMatrix(4, 7) = 9: iMatrix(4, 8) = 7: iMatrix(4, 9) = 8
iMatrix(5, 1) = 6: iMatrix(5, 2) = 4: iMatrix(5, 3) = 5: iMatrix(5, 4) = 9: iMatrix(5, 5) = 7: iMatrix(5, 6) = 8: iMatrix(5, 7) = 3: iMatrix(5, 8) = 1: iMatrix(5, 9) = 2
iMatrix(6, 1) = 9: iMatrix(6, 2) = 7: iMatrix(6, 3) = 8: iMatrix(6, 4) = 3: iMatrix(6, 5) = 1: iMatrix(6, 6) = 2: iMatrix(6, 7) = 6: iMatrix(6, 8) = 4: iMatrix(6, 9) = 5
iMatrix(7, 1) = 2: iMatrix(7, 2) = 3: iMatrix(7, 3) = 1: iMatrix(7, 4) = 5: iMatrix(7, 5) = 6: iMatrix(7, 6) = 4: iMatrix(7, 7) = 8: iMatrix(7, 8) = 9: iMatrix(7, 9) = 7
iMatrix(8, 1) = 5: iMatrix(8, 2) = 6: iMatrix(8, 3) = 4: iMatrix(8, 4) = 8: iMatrix(8, 5) = 9: iMatrix(8, 6) = 7: iMatrix(8, 7) = 2: iMatrix(8, 8) = 3: iMatrix(8, 9) = 1
iMatrix(9, 1) = 8: iMatrix(9, 2) = 9: iMatrix(9, 3) = 7: iMatrix(9, 4) = 2: iMatrix(9, 5) = 3: iMatrix(9, 6) = 1: iMatrix(9, 7) = 5: iMatrix(9, 8) = 6: iMatrix(9, 9) = 4
Randomize
For gOverallStep = 1 To 5 'this introduces enough diversity
'load list
For gA = 1 To 81
gCellList(gA) = gA
Next gA
'shuffle list
For gA = 1 To 81
gB = GetRandom(1, 81)
If gB <> gA Then
gC = gCellList(gB)
gCellList(gB) = gCellList(gA)
gCellList(gA) = gC
End If
Next gA
For gStep = 1 To 81
'we will change the following cell
gRow1 = Fix((gCellList(gStep) - 1) / 9) + 1
gCol1 = gCellList(gStep) - (gRow1 - 1) * 9
'we will change either its row or its col
If GetRandom(1, 2) = 1 Then
'we will change its column
Select Case (gCol1 - 1) Mod 3
Case 0
If GetRandom(1, 2) = 1 Then
gCol2 = gCol1 + 1
Else
gCol2 = gCol1 + 2
End If
Case 1
If GetRandom(1, 2) = 1 Then
gCol2 = gCol1 + 1
Else
gCol2 = gCol1 - 1
End If
Case 2
If GetRandom(1, 2) = 1 Then
gCol2 = gCol1 - 2
Else
gCol2 = gCol1 - 1
End If
End Select
gTargetValue = iMatrix(gRow1, gCol1)
Do
'load
gValue1 = iMatrix(gRow1, gCol1)
gValue2 = iMatrix(gRow1, gCol2)
'swap
iMatrix(gRow1, gCol1) = gValue2
iMatrix(gRow1, gCol2) = gValue1
If gValue2 = gTargetValue Then Exit Do 'terminate if you swapped the initial number
'seek
For gA = 1 To 9
If iMatrix(gA, gCol1) = gValue2 And gA <> gRow1 Then
gRow2 = gA
Exit For
End If
Next gA
'initialize next
gRow1 = gRow2
Loop
Else
'we will change its row
Select Case (gRow1 - 1) Mod 3
Case 0
If GetRandom(1, 2) = 1 Then
gRow2 = gRow1 + 1
Else
gRow2 = gRow1 + 2
End If
Case 1
If GetRandom(1, 2) = 1 Then
gRow2 = gRow1 + 1
Else
gRow2 = gRow1 - 1
End If
Case 2
If GetRandom(1, 2) = 1 Then
gRow2 = gRow1 - 2
Else
gRow2 = gRow1 - 1
End If
End Select
gTargetValue = iMatrix(gRow1, gCol1)
Do
'load
gValue1 = iMatrix(gRow1, gCol1)
gValue2 = iMatrix(gRow2, gCol1)
'swap
iMatrix(gRow1, gCol1) = gValue2
iMatrix(gRow2, gCol1) = gValue1
If gValue2 = gTargetValue Then Exit Do 'terminate if you swapped the initial number
'seek
For gA = 1 To 9
If iMatrix(gRow1, gA) = gValue2 And gA <> gCol1 Then
gCol2 = gA
Exit For
End If
Next gA
'initialize next
gCol1 = gCol2
Loop
End If
Next gStep
Next gOverallStep
End Sub
The routine swaps all 81 cells in random order, for 5 overall loops. The choice to modify columns or rows, as well as which column or row to use, is also random. The function GetRandom is given below:
Private Function GetRandom(gLower As Long, gUpper As Long) As Long
GetRandom = Int((gUpper - gLower + 1) * Rnd + gLower)
End Function
Conclusion
Although probably inefficient, this algorithm is a simple solution if you want to create Sudoku puzzles.
