#### AsimplealgorithmforcreatingSudokupuzzlesusingVisualBasic 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

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

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

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.