Archive

Archive for the ‘sudoku solver algorithm’ Category

Sudoku Solver Algorithm

March 17th, 2012 admin 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
  1. Clear will simply delete any of the previously run Sudoku puzzles.
    Public Sub Clear()
        Sudoku.Clear()
    End Sub
  2. 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
  3. 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
  4. 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
  5. 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 Tags:
Sitemap