Creating a Sudoku game

• Download source code [VS2008] - 6.71 KB
• Download source code [VS2005] - 6.65 KB
• Download compiled demo - 12.2 KB

Introduction

This is the code-behind to generate / solve / use a Sudoku grid. I won't describe or provide the code to display a grid because there are millions of ways to do that and I will let you decide how you want to do it.

But, I will provide an executable with an interface to demonstrate how it can be used.

Background

This code was written with speed in mind.

Using the Code

In the zip file, I have provided a project file, a module and four classes. The code inside the class could be moved into the module; since the function / sub inside them are shared, I decided to split it that way so it's clearer. Let's start with the project file; there is one major thing inside it: I enabled "Remove integer overflow checks" in the advanced compiler settings, everything else are the default settings.

I have the following variables declared in the module:

Private Const debugTime As String = "hh:mm:ss.fffffff"
Private r As New Random()

Private iSquare As Integer
Private squareExp2 As Integer
Private squareExp3 As Integer
Private gridRow() As Integer
Private gridCol() As Integer
Private gridbox() As Integer
Private gridbox1() As Integer

Private selectedGameType As gridSize = gridSize.grid9X9
Private Enum gridSize
    grid9X9 = 3
    grid16X16 = 4
End Enum

Private gameType As benchType = benchType.random
Private Enum benchType
    random
    solve
End Enum

I initialized iSquare, squareExp2, and squareExp3 by doing the following:

iSquare = selectedGameType
squareExp2 = iSquare * iSquare
squareExp3 = squareExp2 * squareExp2 - 1

To populate the row and column arrays, I use the code below:

For i = 0 To squareExp3
    gridCol(i) = i Mod squareExp2
    gridRow(i) = i - gridCol(i) 
Next

In the beginning, I had this code to populate the box array, but I didn't like it:

For j = 0 To squareExp2 - 1
 For i = 0 To squareExp2 - 1
     box = (j * squareExp2) + i

     gridbox(box) = ((j \ Square) * squareExp2 * Square) + _
       ((j Mod Square) * Square) + (i \ Square) * squareExp2 + (i Mod Square)
     gridbox1(gridbox(box)) = ((j \ Square) * squareExp2 * Square) + _
       (((j Mod Square) * Square) * Square)
 Next
Next

So, I went to stackoverflow and I submitted this question.

I got the following response from another user:

So for the gridbox, you are basically taking i and j and interleaving their digits in base(square). E.g., given i and j in base(scale), you are computing: i(2)j(2)i(1)j(1), where (n) signifies the digit base(scale). So that's easy enough to speed up: just keep a running tally of each digit's contribution to the final value of gridbox(...).

Speeding up gridbox1(...) is even easier. Basically, you are computing:

Square * Square *(j\Square * Square + (j Mod Square))

Now, (j Mod Square) expands to:

(j - j\Square*Square)

which reduces the above to:

Square * Square *(j\Square * Square + (j - j\Square*Square))

which simplifies to:

Square * Square *(j\Square * Square + j - j\Square*Square)

which simplifies to:

C#

Square * Square * (j)

I changed my code after reading the response, as follows:

Dim box As Integer
Dim Square2 As Integer = iSquare * iSquare
Dim Square3 As Integer = Square2 * iSquare
Dim Square4 As Integer = Square2 * Square2
Dim j2_offset As Integer, j1_offset As Integer
Dim j1_interleaved_offset As Integer, i2_offset As Integer
Dim i2_interleaved_offset As Integer, j_offset_value As Integer
Dim offset_value As Integer, interleaved_value As Integer

For j2 As Integer = 0 To iSquare - 1
    j1_offset = 0
    j1_interleaved_offset = 0
    For j1 As Integer = 0 To iSquare - 1
        i2_offset = 0
        i2_interleaved_offset = 0
        j_offset_value = j2_offset + j1_offset
        For i2 As Integer = 0 To iSquare - 1
            offset_value = j_offset_value + i2_offset
            interleaved_value = j2_offset + _
               i2_interleaved_offset + j1_interleaved_offset
            For i1 As Integer = 0 To iSquare - 1
                 box = offset_value + i1
                 gridbox(box) = interleaved_value + i1
                 gridbox1(gridbox(box)) = j_offset_value
             Next
             i2_offset += iSquare
             i2_interleaved_offset += Square2
         Next
        j1_offset += Square2
        j1_interleaved_offset += iSquare
    Next
    j2_offset += Square3
Next

Why do all these steps to fill these arrays? To be able to use them this way:

To get every number inside a row, based on a position (which is i in these examples):

j = myGridRow(i)
For x = j To (j + squareExp2) - 1
    foundNumber(grid(x)) = grid(x)
Next

To get every number inside a column:

j = myGridCol(i)
For x = j To squareExp3 Step squareExp2
    foundNumber(grid(x)) = grid(x)
Next

To get every number inside a box, normally, you would do something like this:

k = (gridRow(pos) \ iSquare) * iSquare
l = (gridCol(pos) \ iSquare) * iSquare

For i = l To l + iSquare - 1
    For j = k To k + iSquare - 1
        box = (j * squareExp2) + i
        foundNumber(grid(box)) = grid(box)
    Next
Next

But, since with the gridbox and gridbox1 array you already know every position inside the box, you only need to do this:

j = myGridbox1(i)
For x = j To (j + squareExp2) - 1
    foundNumber(grid(myGridbox(x))) = grid(myGridbox(x))
Next

For the classes, I always pass all the pre-calculated variables, arrays, and the random variable.

The function returning a random grid returns an one dimensional array. To display it, you just need to use a loop and make a new row after every squareExp2. For example:

Dim msg As String = Nothing

For i = 0 To squareExp3
    If i Mod squareExp2 = 0 Then
       msg += vbCrLf
    End If
    msg += grid(i).ToString
Next
MsgBox(msg)

To generate a grid, I have two main parts inside the function. The first part contains the backtracking logic, and the second part finds every possible number for a specific position and then selects a random one from the resulting list of possible numbers.

The Grid array has a size of squareExp3, and I loop through it to fill it sequentially.

Let's start with the backtracking logic:

If count = 0 Then
   x = i

   If tried > squareExp2 Then
      tried = 0

      If i > squareExp2Mult2 Then
         i -= squareExp2Mult2 - 2
      Else
         i = 0
      End If
   Else
      tried += 1
      i -= squareExp2 - 2
   End If

   For j = i To x
      grid(j) = 0
   Next
End If

squareExp2Mult2 equals squareExp2 * 2.

count shows how many possibilities were in the previous position, and I initialize it to one so it won't enter when I start the loop.

If there was no possible number in the previous position, the code will check to see how many times it entered the backtracking logic for the current grid, and if it was, for an example with a 9x9 grid 10 times, it will check what is the current position (i) to make sure it won't go into a negative value and remove, for the same 9x9 grid, a maximum of 16 numbers; if it was less than 10 times, it would just remove 7 numbers.

When that is done, the main loop counter will change so it can continue to fill the grid. I picked the numbers "16" and "7". When I was doing benchmarking, they seem to be the best numbers so far, but if you find others, let me know.

For the second part:

j = myGridRow(i)
For x = j To (j + squareExp2) - 1
    foundNumber(grid(x)) = grid(x)
Next

j = myGridCol(i)
For x = j To squareExp3 Step squareExp2
    foundNumber(grid(x)) = grid(x)
Next

j = myGridbox1(i)
For x = j To (j + squareExp2) - 1
    foundNumber(grid(myGridbox(x))) = grid(myGridbox(x))
Next

count = 0
For x = 1 To squareExp2
    If foundNumber(x) = 0 Then
       foundNumberRnd(count) = x
       count += 1
    End If
    foundNumber(x) = 0
Next

If count > 1 Then
     grid(i) = foundNumberRnd(r.Next(count))
Else
     grid(i) = foundNumberRnd(0)
End If

I already explained how the first three loops are working, so I will start explaining from the "count = 0" line.

I loop through the foundNumber array, which has a size of squareExp2, to find every 0. When a 0 is found, it means there is a possible number for the current position (i), so I put the value of counter x inside the second array (foundNumberRnd), which is used to find the random number, and then increment the counter. Finally, I reset the foundNumber value to 0 for the next loop (position).

If there is more than one number found, count > 1, I pick a random number inside the foundNumberRnd array. Otherwise, I pick the first number inside the foundNumberRnd array which can be a valid or invalid number; if it is an invalid number, it means the count is still 0, and the backtracking logic will be triggered. The function returning hints needs two more parameters, the actual grid() and the position, and it will return a one dimensional array. To use the result, you only need to check the array between 1 and squareExp2 and find every 0.

I wrote a function that verifies if the grid is valid. You need to pass the grid() to the function and it will return true/false.

The function to solve the grid is far from done, it's a work in progress.

Beware, there is no "stop" inside this logic so you can get an infinite loop if the grid is not valid or the current algorithm cannot find a solution. The function needs a string to represent the grid, or you can pass nothing to actually create one. When a solution is found, it will return an array, and you can use the code used for the generator to display it.

Points of Interest

While I was implementing this code, I learned a few optimization tricks. For example:

• An array is still faster than a List(Of T).
• Enabling "Remove integer overflow checks" in advanced compiler settings givess some boost.
• An one dimensional array is a lot faster than a multi dimensional array, but it's harder to work with.
• It's better to declare a random variable at class / application level than redo it all the time in a sub / function.

And a few more minor ones.

I can do over 53,000 9x9 random grids per second, and over 310 16x16 random grids per second in my home computer.

History

• Version 1.3, 2009-03-12.

Updated demo to fix a bug when resized.

• Version 1.2, 2009-03-10
.

Added a Zip file for Visual Studio 2005.

• Version 1.1, 2009-03-08.

Added how the grid is generated.

• Initial release version 1.0, 2009-03-05.