## Sudoku Solver Algorithm

March 17th, 2012
Comments off

# Sudoku Solving Algorithm

In this post we are going to take a look at a sudoku solving algorithm that solves sudoku puzzles. One of the key features to this particular algorithm is that it will eventually end and let us know if the particular sudoku in question has a solution.

If so it will reveal at least one solution it is possible to have more than one, in fact it is possible to have several for an individual puzzle.

**A Simple Sudoku Solving Algorithm**

Here is a very simple sudoku solving algorithm that starts with a grid that is already partially completed. For more information visit code project or cornell university mathematics and sudoku

```
Public Sub GenerateGrid()
Clear()
Dim Squares(80) As Square 'an arraylist of squares: see line 86
Dim Available(80) As List(Of Integer) 'an arraylist of generic lists (nested lists)
'we use this to keep track of what numbers we can still use in what squares
Dim c As Integer = 0 'use this to count the square we are up to
For x As Integer = 0 To Available.Length - 1
Available(x) = New List(Of Integer)
For i As Integer = 1 To 9
Available(x).Add(i)
Next
Next
Do Until c = 81 'we want to fill every square object with values
If Not Available(c).Count = 0 Then 'if every number has been tried
'and failed then backtrack
Dim i As Integer = GetRan(0, Available(c).Count - 1)
Dim z As Integer = Available(c).Item(i)
If Conflicts(Squares, Item(c, z)) = False Then 'do a check with the
'proposed number
Squares(c) = Item(c, z) 'this number works so we add it to the
'list of numbers
Available(c).RemoveAt(i) 'we also remove it from its individual list
c += 1 'move to the next number
Else
Available(c).RemoveAt(i) 'this number conflicts so we remove it
'from its list
End If
Else
For y As Integer = 1 To 9 'forget anything about the current square
Available(c).Add(y) 'by resetting its available numbers
Next
Squares(c - 1) = Nothing 'go back and retry a different number
c -= 1 'in the previous square
End If
Loop
Dim j As Integer ' this produces the output list of squares
For j = 0 To 80
Sudoku.Add(Squares(j))
Next
'This algorithm produces a Sudoku in an average of 0.018 seconds,
'tested over 5000 iterations
End Sub
```

`Clear will`

simply delete any of the previously run Sudoku puzzles.Collapse | Copy CodePublic Sub Clear() Sudoku.Clear() End Sub

`Square`

This is the name for the particular structure. it could be any name just square was the one actually chosen. Each instance you see of`square`

will represent an object with information about the particular value, index and relative positions of each of the`square`

contained in it's its region (3×3 area), row, column, index and value.Public Structure Square Dim Across As Integer Dim Down As Integer Dim Region As Integer Dim Value As Integer Dim Index As Integer End Structure

`GetRan will`

retrieve a random number of between 0 and the last index of the current list,Private Function GetRan(ByVal lower As Integer, ByVal upper As Integer) _ As Integer Dim r As New Random GetRan = r.Next(lower, upper - 1) End Function

- Conflicts this is the most important function in the overall algorithm. It will tell us whether the number we are considering is actually going to work. To do this it takes the squares currently produced and compares them with an instance of a not yet produced square. This test square ('the hypothetical') is made in the '
`Item`

' function below.Private Function Conflicts(ByVal CurrentValues As Square(), _ ByVal test As Square) As Boolean For Each s As Square In CurrentValues If (s.Across <> 0 And s.Across = test.Across) OrElse _ (s.Down <> 0 And s.Down = test.Down) OrElse _ (s.Region <> 0 And s.Region = test.Region) Then If s.Value = test.Value Then Return True End If End If Next Return False End Function

- Item takes the given value and the given index and returns a square item containing all relevant information. It does this by calling on 3 other functions to acquire the row, column and region of the square. These other functions use simple math to determine the row, column etc.
Private Function Item(ByVal n As Integer, ByVal v As Integer) As Square n += 1 Item.Across = GetAcrossFromNumber(n) Item.Down = GetDownFromNumber(n) Item.Region = GetRegionFromNumber(n) Item.Value = v Item.Index = n - 1 End Function Private Function GetAcrossFromNumber(ByVal n As Integer) As Integer Dim k As Integer k = n Mod 9 If k = 0 Then Return 9 Else Return k End Function Private Function GetDownFromNumber(ByVal n As Integer) As Integer Dim k As Integer If GetAcrossFromNumber(n) = 9 Then k = n\9 Else k = n\9 + 1 End If Return k End Function Private Function GetRegionFromNumber(ByVal n As Integer) As Integer Dim k As Integer Dim a As Integer = GetAcrossFromNumber(n) Dim d As Integer = GetDownFromNumber(n) If 1 <= a And a < 4 And 1 <= d And d < 4 Then k = 1 ElseIf 4 <= a And a < 7 And 1 <= d And d < 4 Then k = 2 ElseIf 7 <= a And a < 10 And 1 <= d And d < 4 Then k = 3 ElseIf 1 <= a And a < 4 And 4 <= d And d < 7 Then k = 4 ElseIf 4 <= a And a < 7 And 4 <= d And d < 7 Then k = 5 ElseIf 7 <= a And a < 10 And 4 <= d And d < 7 Then k = 6 ElseIf 1 <= a And a < 4 And 7 <= d And d < 10 Then k = 7 ElseIf 4 <= a And a < 7 And 7 <= d And d < 10 Then k = 8 ElseIf 7 <= a And a < 10 And 7 <= d And d < 10 Then k = 9 End If Return k End Function

Categories: sudoku solver algorithm