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:
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.
