Parallel Depth-First Sudoku Solver Algorithm
April 6, 2011 2 Comments
Image via Wikipedia
| Preparing to go parallel with depth-first search using Sudoku as case study |
| Ali Tarhini |
| 04/06/2011 |
Contents
- What is Sudoku?.
- Rules of Sudoku.
- Computational Complexity.
- Sudoku Solving Techniques.
- Elimination.
- Finding Lone Rangers.
- Finding Twins.
- Finding Triplets.
- Brute-Force Elimination.
- Going Parallel
What is Sudoku?
Sudoku is the wildly popular new puzzle game that is taking the world by storm. Sudoku puzzles are 9×9 grids, and each square in the grid consists of a 3×3 subgrid called a minigrid. Your goal is to fill in the squares so that each column, row, and minigrid contains the numbers 1 through 9 exactly once. And some squares already contain numbers or symbols, which lend clues toward the solution. While the rules of Sudoku are extremely simple, solving a Sudoku puzzle is an intellectual challenge.
Figure1: Empty Sudoku grid
Rules of Sudoku
The aim of the game is to place a number from 1 to 9 into each of the cells, such that each
number must appear exactly once in each row and in each column in the grid. Additionally, each minigrid must contain all the numbers 1 through 9. A Sudoku puzzle usually comes with a partially filled grid. The aim is to complete the grid in the shortest amount of time.
Figure2: Partially filled Sudoku grid
Computational Complexity
From a mathematical perspective, it has been proven that the total number of valid Sudoku grids is 6,670,903,752,021,072,936,960 or approximately 6.671×1021 [1].
Trying to populate all these grids is itself a difficult problem because of the huge number, Assuming each solution takes 1 micro second to be found, then with a simple calculation we can determine that it takes 211,532,970,320.3 years to find all possible solutions.
If that number was small, say 1000, it would be very easy to write a Soduku solver application that can solve a given puzzle in short amount of time. The program would simply enumerate all the 1000 puzzles and compares the given puzzle with the enumerated ones. Unfortunately, this is not the case since the actual number of possible valid grids is extremely large so it’s not possible to enumerate all the possible solutions. This large number also directly eliminates the possibility of solving the puzzle with brute force technique in a reasonable amount of time. Therefore, a method for solving the puzzle quickly will be derived that takes advantage of some “logical” properties of Sudoku to reduce the search space and optimize the running time of the algorithm. Our goal off course, is to allow for that algorithm to take advantage of the manycore architecture to further reduce its running time. This is very important and is at the heart of our work because we can extend the 9×9 Sudoku grid to an NxN grid and as you would expect the complexity of the puzzle goes up by a big notch. Hence, the parallel algorithm must also scale as the grid size increases.
Sudoku Solving Techniques
Elimination
Elimination technique is probably one of the simplest ways to start solving a Sudoku grid. Basically this method scans the grid from the top left cell to the bottom right cell going one row at a time and looks for each cell, it checks whether the number of possible values is equal to 1 then it assigns the single possible number to the cell. This method is straight forward and is a basic step when deciding on which value to fill in a cell. The figure below shows the highlighted cell in green which could be assigned one possible value that happens to be 1 too since values 2,4,5,7 are in the same minigrid. 3, 6, 8 are on the same row and 9 is on the same row.
Figure2: 1 value is possible for the green cell
The method GetCellPossibleValues takes in the X and Y coordinates of the cell and determines the set of possible values for the cell. This method is important because it is being called almost everytime a value is about to be assigned to a cell and seems to be parallelizable since it is divided into three independent operations: row scan, column scan and minigrid scan:
<pre>
Public Function GetCellPossibleValues(ByVal XIndex As Byte, ByVal YIndex As Byte) As List(Of Byte)
Dim c As New Cell
c.PossibleValues.Clear()
For Each b As Byte In mCells(XIndex, YIndex).PossibleValues
c.PossibleValues.Add(b)
Next
For i As Byte = 0 To 8
If Not mCells(i, YIndex).Type = Cell.CellType.Empty AndAlso i <> XIndex AndAlso mCells(XIndex, YIndex).PossibleValues.Contains(mCells(i, YIndex).Value) Then
c.PossibleValues.Remove(mCells(i, YIndex).Value)
End If
If Not mCells(XIndex, i).Type = Cell.CellType.Empty AndAlso i <> YIndex AndAlso mCells(XIndex, YIndex).PossibleValues.Contains(mCells(XIndex, i).Value) Then
c.PossibleValues.Remove(mCells(XIndex, i).Value)
End If
Next
Dim regionX As Byte = Math.Ceiling((XIndex + 1) / 3 – 1) * 3
Dim regionY As Byte = Math.Ceiling((YIndex + 1) / 3 – 1) * 3
For i As Byte = regionX To regionX + 2
For j As Byte = regionY To regionY + 2
If Not mCells(i, j).Type = Cell.CellType.Empty AndAlso i <> XIndex AndAlso j <> YIndex AndAlso mCells(XIndex, YIndex).PossibleValues.Contains(mCells(i, j).Value) Then
c.PossibleValues.Remove(mCells(i, j).Value)
End If
Next
Next
Return c.PossibleValues
End Function
</pre>
Finding Lone Rangers
A Lone Ranger is a number that is one of multiple values for a cell but it appears only once in a row, column or minigrid. For example, the green cell shown in the figure below has 4 possible values. Intuitively, a human solving this grid will most likely to skip this cell because it seems “too early to predict its value” because of the several values possible. But if we take a closer look at the cell’s row, note that the number 8 appears only once in the row and it appears as a possible value for that cell. Hence, 8 is indeed the correct value for that cell.
The following 3 methods loop over the grid in rows, columns and minigrids and look for Lone Rangers, if one is found, its value is set directly and thus furthermore reducing the solution space.
<pre>
Public Function SetLoneRangersRow() As Boolean
Dim x As Byte = 0, y As Byte = 0
Dim changes As Boolean = False
Dim totalChanges As Boolean = False
Do
changes = False
For i As Byte = 0 To 8
For B As Byte = 1 To 9
Dim count As Byte = 0
For j As Byte = 0 To 8
If mCells(j, i).Type = Cell.CellType.Empty Then
If mCells(j, i).PossibleValues.Contains(B) Then
count += 1
If count > 1 Then Exit For
x = j
y = i
End If
End If
Next
If count = 1 Then
mCells(x, y).Value = B
mCells(x, y).IsValid = True
changes = True
totalChanges = True
End If
Next
Next
Loop Until Not changes
Return totalChanges
End Function
Public Function SetLoneRangersColumn() As Boolean
Dim x As Byte = 0, y As Byte = 0
Dim changes As Boolean = False
Dim totalChanges As Boolean = False
Do
changes = False
For i As Byte = 0 To 8
For B As Byte = 1 To 9
Dim count As Byte = 0
For j As Byte = 0 To 8
If mCells(i, j).Type = Cell.CellType.Empty Then
If mCells(i, j).PossibleValues.Contains(B) Then
count += 1
x = i
y = j
If count > 1 Then Exit For
End If
End If
Next
If count = 1 Then
mCells(x, y).Value = B
mCells(x, y).IsValid = True
changes = True
totalChanges = True
End If
Next
Next
Loop Until Not changes
Return totalChanges
End Function
Private Function SetLoneRangersRegion() As Boolean
Dim x As Byte = 0, y As Byte = 0
Dim counter As Byte = 0
Dim nextRegion As Boolean = False
Dim changes As Boolean = False
Dim totalChanges As Boolean = False
Do
changes = False
For B As Byte = 1 To 9
For i As Byte = 0 To 8 Step 3
For j As Byte = 0 To 8 Step 3
nextRegion = False
counter = 0
For r As Byte = i To i + 2
For c As Byte = j To j + 2
If mCells(c, r).Type = Cell.CellType.Empty Then
If mCells(c, r).PossibleValues.Contains(B) Then
counter += 1
x = c
y = r
If counter > 1 Then
nextRegion = True
Exit For
End If
End If
End If
Next
If nextRegion Then Exit For
Next
If (Not nextRegion) AndAlso counter = 1 Then
mCells(x, y).Value = B
mCells(x, y).IsValid = True
changes = True
totalChanges = True
End If
Next
Next
Next
Loop Until Not changes
Return totalChanges
End Function
</pre>
The flowchart below shows how the algorithm works after applying the Lone Rangers methods.
Figure3: Flowchart for solving Sudoku using elimination and lone ranger’s property.
Finding Twins
Twins are two cells that contain two numbers that appear nowhere else but in these cells on the same row, column or minigrid. For example, take a look at the two green cells below, both have the same two possible values 4 and 9 on the same column. This means that if one of the cells were to be assigned the value 4, the other cell will be assigned the value 9 and vice versa. Therefore we can be confident that 4 and 9 will not be assigned to any other cell on the same column. Therefore we remove the value 9 from the remaining cell in the same column that had two possible values 6 and 9 so that cell has only value 6 left. By process of elimination 6 will be assigned to that cell.
Figure4: A typical twins case
The following 3 methods implement the twins elimination method.
<pre>
Public Function SetTwinsRow() As Boolean
Dim changes As Boolean = False
For i As Byte = 0 To 8
For j As Byte = 0 To 8
If mCells(j, i).Type = Cell.CellType.Empty Then
If mCells(j, i).PossibleValues.Count = 2 Then
For k As Byte = j + 1 To 8
If mCells(j, i).StringPossibleValues = mCells(k, i).StringPossibleValues Then
For l As Byte = 0 To 8
If mCells(l, i).Type = Cell.CellType.Empty AndAlso l <> k AndAlso l <> j Then
If mCells(l, i).PossibleValues.Contains(mCells(j, i).PossibleValues(0)) Then
mCells(l, i).PossibleValues.Remove(mCells(j, i).PossibleValues(0))
changes = True
End If
If mCells(l, i).PossibleValues.Contains(mCells(j, i).PossibleValues(1)) Then
mCells(l, i).PossibleValues.Remove(mCells(j, i).PossibleValues(1))
changes = True
End If
If changes AndAlso mCells(l, i).PossibleValues.Count = 1 Then
mCells(l, i).Value = mCells(l, i).PossibleValues(0)
mCells(l, i).IsValid = True
True
End If
End If
Next
End If
Next
End If
End If
Next
Next
Return changes
End Function
Public Function SetTwinsColumn() As Boolean
Dim changes As Boolean = False
For i As Byte = 0 To 8
For j As Byte = 0 To 8
If mCells(i, j).Type = Cell.CellType.Empty Then
If mCells(i, j).PossibleValues.Count = 2 Then
For k As Byte = j + 1 To 8
If mCells(i, j).StringPossibleValues = mCells(i, k).StringPossibleValues Then
For l As Byte = 0 To 8
If mCells(i, l).Type = Cell.CellType.Empty AndAlso l <> k AndAlso l <> j Then
If mCells(i, l).PossibleValues.Contains(mCells(i, j).PossibleValues(0)) Then
mCells(i, l).PossibleValues.Remove(mCells(i, j).PossibleValues(0))
changes = True
End If
If mCells(i, l).PossibleValues.Contains(mCells(i, j).PossibleValues(1)) Then
mCells(i, l).PossibleValues.Remove(mCells(i, j).PossibleValues(1))
changes = True
End If
End If
If changes AndAlso mCells(i, l).PossibleValues.Count = 1 Then
mCells(i, l).Value = mCells(i, l).PossibleValues(0)
mCells(i, l).IsValid = True
End If
Next
End If
Next
End If
End If
Next
Next
Return changes
End Function
Public Function SetTwinsRegion() As Boolean
Dim changes As Boolean = False
For i As Byte = 0 To 8
For j As Byte = 0 To 8
If mCells(i, j).Type = Cell.CellType.Empty AndAlso mCells(i, j).PossibleValues.Count = 2 Then
Dim regionX As Byte = Math.Ceiling((i + 1) / 3 – 1) * 3
Dim regionY As Byte = Math.Ceiling((j + 1) / 3 – 1) * 3
For k As Byte = regionX To regionX + 2
For l As Byte = regionY To regionY + 2
If mCells(k, l).Type = Cell.CellType.Empty Then
If i <> k AndAlso j <> l AndAlso mCells(i, j).StringPossibleValues = mCells(k, l).StringPossibleValues Then
For m As Byte = regionX To regionX + 2
For n As Byte = regionY To regionY + 2
If m <> k AndAlso m <> i AndAlso n <> l AndAlso n <> j Then
If mCells(m, n).PossibleValues.Contains(mCells(i, j).PossibleValues(0)) Then
mCells(m, n).PossibleValues.Remove(mCells(i, j).PossibleValues(0))
changes = True
End If
If mCells(m, n).PossibleValues.Contains(mCells(i, j).PossibleValues(1)) Then
mCells(m, n).PossibleValues.Remove(mCells(i, j).PossibleValues(1))
changes = True
End If
If changes AndAlso mCells(m, n).PossibleValues.Count = 1 Then
mCells(m, n).Value = mCells(m, n).PossibleValues(0)
mCells(m, n).IsValid = True
End If
End If
Next
Next
End If
End If
Next
Next
End If
Next
Next
Return changes
End Function
</pre>
Finding Triplets
As with twins, we might also come across triplets. These are three cells on the same row, column or minigrid that share 3 unique values. For example, the figure below shows the second column of the grid with 3 cells highlighted in green. The three cells could be assigned with only three possible values each, 3, 6 and 9. Therefore the three numbers shall be removed from the remaining cell with four possible values 2, 3, 6 and 9. Hence, 2 remains the only possible value for that cell and will be assigned to it.
Figure5: A typical Triplets scenario
However, it is worth mentioning unlike lone rangers and twins, triplets could have 3 variants:
• Variant 1: Three cells with the same three possible values as shown in figure 5 in the last section)
• Variant 2: Two cells with three possible values and one cell containing two possible values that are a subset of the three possible values
• Variant 3: One cell with three possible values and two cells containing two possible values that are a subset of the three possible values
The code below implements the 3 methods for triplets detection using the 3 variants in rows, columns and minigrids
<pre>
Public Function SetTripletsColumn() As Boolean
Dim changes As Boolean = False
For i As Byte = 0 To 8
For j As Byte = 0 To 8
If mCells(i, j).Type = Cell.CellType.Empty AndAlso mCells(i, j).PossibleValues.Count = 3 Then
Dim w, v As Byte
Dim flag As Boolean = True
Dim partialChanges As Boolean = False
For k As Byte = j + 1 To 8
If mCells(i, k).Type = Cell.CellType.Empty Then
If mCells(i, j).StringPossibleValues = mCells(i, k).StringPossibleValues OrElse _
(mCells(i, k).PossibleValues.Count = 2 AndAlso mCells(i, j).PossibleValues.Contains(mCells(i, k).PossibleValues(0)) _
AndAlso mCells(i, j).PossibleValues.Contains(mCells(i, k).PossibleValues(1))) Then
If flag Then
w = k
flag = False
Else
v = k
partialChanges = True
End If
End If
End If
Next
If partialChanges Then
For l As Byte = 0 To 8
If l <> j AndAlso l <> w AndAlso l <> v Then
If mCells(i, l).PossibleValues.Contains(mCells(i, j).PossibleValues(0)) Then
mCells(i, l).PossibleValues.Remove(mCells(i, j).PossibleValues(0))
changes = True
End If
If mCells(i, l).PossibleValues.Contains(mCells(i, j).PossibleValues(1)) Then
mCells(i, l).PossibleValues.Remove(mCells(i, j).PossibleValues(1))
changes = True
End If
If mCells(i, l).PossibleValues.Contains(mCells(i, j).PossibleValues(2)) Then
mCells(i, l).PossibleValues.Remove(mCells(i, j).PossibleValues(2))
changes = True
End If
If changes AndAlso mCells(i, l).PossibleValues.Count = 1 Then
mCells(i, l).Value = mCells(i, l).PossibleValues(0)
mCells(i, l).IsValid = True
End If
End If
Next
End If
End If
Next
Next
Return changes
End Function
Public Function SetTripletsRow() As Boolean
Dim changes As Boolean = False
For i As Byte = 0 To 8
For j As Byte = 0 To 8
If mCells(j, i).Type = Cell.CellType.Empty AndAlso mCells(j, i).PossibleValues.Count = 3 Then
Dim w, v As Byte
Dim flag As Boolean = True
Dim partialChanges As Boolean = False
For k As Byte = j + 1 To 8
If mCells(k, i).Type = Cell.CellType.Empty Then
If mCells(j, i).StringPossibleValues = mCells(k, i).StringPossibleValues OrElse _
(mCells(k, i).PossibleValues.Count = 2 AndAlso mCells(j, i).PossibleValues.Contains(mCells(k, i).PossibleValues(0)) _
AndAlso mCells(j, i).PossibleValues.Contains(mCells(k, i).PossibleValues(1))) Then
If flag Then
w = k
flag = False
Else
v = k
partialChanges = True
End If
End If
End If
Next
If partialChanges Then
For l As Byte = 0 To 8
If l <> j AndAlso l <> w AndAlso l <> v Then
If mCells(l, i).PossibleValues.Contains(mCells(j, i).PossibleValues(0)) Then
mCells(l, i).PossibleValues.Remove(mCells(j, i).PossibleValues(0))
changes = True
End If
If mCells(l, i).PossibleValues.Contains(mCells(j, i).PossibleValues(1)) Then
mCells(l, i).PossibleValues.Remove(mCells(j, i).PossibleValues(1))
changes = True
End If
If mCells(l, i).PossibleValues.Contains(mCells(j, i).PossibleValues(2)) Then
mCells(l, i).PossibleValues.Remove(mCells(j, i).PossibleValues(2))
changes = True
End If
If changes AndAlso mCells(l, i).PossibleValues.Count = 1 Then
mCells(l, i).Value = mCells(l, i).PossibleValues(0)
mCells(l, i).IsValid = True
End If
End If
Next
End If
End If
Next
Next
Return changes
End Function
Public Function SetTripletsRegion() As Boolean
Dim changes As Boolean = False
For i As Byte = 0 To 8
For j As Byte = 0 To 8
If mCells(i, j).Type = Cell.CellType.Empty AndAlso mCells(i, j).PossibleValues.Count = 3 Then
Dim regionX As Byte = Math.Ceiling((i + 1) / 3 – 1) * 3
Dim regionY As Byte = Math.Ceiling((j + 1) / 3 – 1) * 3
Dim w, v, x, y As Byte
Dim flag As Boolean = True
Dim partialChanges As Boolean = False
For r As Byte = regionX To regionX + 2
For c As Byte = regionY To regionY + 2
If (Not (i = r AndAlso j = c)) AndAlso (mCells(i, j).StringPossibleValues = mCells(r, c).StringPossibleValues OrElse _
(mCells(r, c).PossibleValues.Count = 2 AndAlso mCells(i, j).PossibleValues.Contains(mCells(r, c).PossibleValues(0)) _
AndAlso mCells(i, j).PossibleValues.Contains(mCells(r, c).PossibleValues(1)))) Then
If flag Then
w = r
v = c
flag = False
Else
x = r
y = c
partialChanges = True
End If
End If
Next
Next
flag = True
If partialChanges Then
For k As Byte = regionX To regionX + 2
For l As Byte = regionY To regionY + 2
If Not (k = i AndAlso l = j) AndAlso Not (k = w AndAlso l = v) AndAlso Not (k = x AndAlso l = y) Then
If mCells(k, l).PossibleValues.Contains(mCells(i, j).PossibleValues(0)) Then
mCells(k, l).PossibleValues.Remove(mCells(i, j).PossibleValues(0))
changes = True
End If
If mCells(k, l).PossibleValues.Contains(mCells(i, j).PossibleValues(1)) Then
mCells(k, l).PossibleValues.Remove(mCells(i, j).PossibleValues(1))
changes = True
End If
If mCells(k, l).PossibleValues.Count > 2 Then
If mCells(k, l).PossibleValues.Contains(mCells(i, j).PossibleValues(2)) Then
mCells(k, l).PossibleValues.Remove(mCells(i, j).PossibleValues(2))
changes = True
End If
End If
If changes AndAlso mCells(k, l).PossibleValues.Count = 1 Then
mCells(k, l).Value = mCells(k, l).PossibleValues(0)
mCells(k, l).IsValid = True
End If
End If
Next
Next
End If
End If
Next
Next
Return changes
End Function
</pre>
Brute-Force Elimination
When all logical means have been used to solve a Sudoku puzzle and the puzzle remains unsolved, we have to perform some guesswork and choose a value for a cell and see if that helps to solve a puzzle but which cell? As a heuristic I have decided to choose the cell with the least number of possible values. This will decrease the probability of guessing it wrong.I should also mention that the possibility of a wrong guessing, so what happens if the algorithm guessed a value that turned out to be yield an unsovable puzzle within few steps. To work around the problem, we introduce the notion of “backtracking” or simply, undoing the puzzle to a previous state just before we took the wrong guess and continue from there by taking a different guess. To get the undo strategy working, we will utilize the classic stack data structure. When a guess is made, a copy of the puzzle is pushed onto the stack before the guess is taken. When a dead end is reached, the puzzle is popped from the stack and replaces the current unsolvable one.
The methods below implement the brute force algorithm for solving the puzzle with guessing
<pre>
Private Sub FindSmallestPossibilities(ByRef XIndex As Byte, ByRef YIndex As Byte)
Dim min As Byte = 10
For i As Byte = 0 To 8
For j As Byte = 0 To 8
If mCells(j, i).Type = Cell.CellType.Empty AndAlso mCells(j, i).PossibleValues.Count < min Then
min = mCells(j, i).PossibleValues.Count
XIndex = j
YIndex = i
End If
Next
Next
End Sub
Private CellsStack As New Stack(Of Cell(,))
Private StopBruteForce As Boolean = False
Private Sub BruteForceRecursive(Optional ByVal HintOnly As Boolean = False)
Dim i, j As Byte
FindSmallestPossibilities(j, i)
Try
CellsStack.Push(mCells.Clone)
Catch ex As StackOverflowException
Return
End Try
While mCells(j, i).PossibleValues.Count > 0
mCells(j, i).Value = mCells(j, i).PickNumber()
If SolveLogical(HintOnly) Then
StopBruteForce = True
mCells(j, i).IsValid = True
Return
Else
Dim goodMove As Boolean = True
For y As Byte = 0 To 8
For k As Byte = 0 To 8
If mCells(y, k).Type = Cell.CellType.Empty AndAlso mCells(y, k).PossibleValues.Count = 0 Then
goodMove = False
Exit For
End If
Next
Next
If goodMove Then
mCells(j, i).IsValid = True
BruteForceRecursive()
If StopBruteForce Then Return
Else
If CellsStack.Count > 0 Then
mCells = CellsStack.Pop
Else
Return
End If
End If
End If
End While
End Sub
</pre>
Even though I call this technique brute-force elimination, solving the puzzle using this technique does not imply that we are solving the entire puzzle by guesswork. In fact, for most puzzles, you need to apply the brute-force elimination technique only a few times, and then you can solve the rest of the grid by other logical techniques covered earlier.
Below is the main method that we need to call to solve the puzzle which in turn utilizes strategies in all the methods described earlier..
<pre>
Public Function SolveLogical() As Boolean
Dim changes As Boolean = False
Do
changes = SetPossibleValues()
If Not changes Then
While SetTripletsRegion()
If IsSolution() Then Return True
changes = True
End While
If Not changes Then
While SetTripletsRow()
If IsSolution() Then Return True
changes = True
End While
If Not changes Then
While SetTripletsColumn()
If IsSolution() Then Return True
changes = True
End While
If Not changes Then
While SetTwinsRegion()
If IsSolution() Then Return True
changes = True
End While
If Not changes Then
While SetTwinsRow()
If IsSolution() Then Return True
changes = True
End While
If Not changes Then
While SetTwinsColumn()
If IsSolution() Then Return True
changes = True
End While
If Not changes Then
While SetLoneRangersRegion(HintOnly)
If IsSolution() Then Return True
changes = True
End While
If Not changes Then
While SetLoneRangersRow(HintOnly)
If IsSolution() Then Return True
changes = True
End While
If Not changes Then
While SetLoneRangersColumn(HintOnly)
If IsSolution() Then Return True
changes = True
End While
End If
End If
End If
End If
End If
End If
End If
End If
End If
Loop Until IsSolution() OrElse Not changes
Return changes
End Function
</pre>
Going Parallel
In this section, I will describe how to parallelize the elimination method. However, it seems that parallelizing any of these methods including finding lone rangers, twins and triplets. These efforts do not yield good scaling over manycore because even though the degree of parallelism is well achieved, the amount of work being done in parallel is small compared to the overall algorithm that is calling on to these methods which is still sequential in nature. That’s why a cleverer algorithm that is able to deal with concurrency needs to be developed later.
Anyway let’s take a look again at the GetCellPossibleValues. The method, performs 2 actions in sequence, these are:
1. Find possible values using row and column scan
2. Find possible values using minigrid scan
<pre>
Public Function GetCellPossibleValues(ByVal XIndex As Byte, ByVal YIndex As Byte) As List(Of Byte)
Dim c As New Cell
c.PossibleValues.Clear()
For Each b As Byte In mCells(XIndex, YIndex).PossibleValues
c.PossibleValues.Add(b)
Next
For i As Byte = 0 To 8
If Not mCells(i, YIndex).Type = Cell.CellType.Empty AndAlso i <> XIndex AndAlso mCells(XIndex, YIndex).PossibleValues.Contains(mCells(i, YIndex).Value) Then
c.PossibleValues.Remove(mCells(i, YIndex).Value)
End If
If Not mCells(XIndex, i).Type = Cell.CellType.Empty AndAlso i <> YIndex AndAlso mCells(XIndex, YIndex).PossibleValues.Contains(mCells(XIndex, i).Value) Then
c.PossibleValues.Remove(mCells(XIndex, i).Value)
End If
Next
Dim regionX As Byte = Math.Ceiling((XIndex + 1) / 3 – 1) * 3
Dim regionY As Byte = Math.Ceiling((YIndex + 1) / 3 – 1) * 3
For i As Byte = regionX To regionX + 2
For j As Byte = regionY To regionY + 2
If Not mCells(i, j).Type = Cell.CellType.Empty AndAlso i <> XIndex AndAlso j <> YIndex AndAlso mCells(XIndex, YIndex).PossibleValues.Contains(mCells(i, j).Value) Then
c.PossibleValues.Remove(mCells(i, j).Value)
End If
Next
Next
Return c.PossibleValues
End Function
</pre>
These 2 code blocks can be easily set to run in parallel at the same time because they are not dependant on each other. However, a lock needs to be set on the possible values of the cell since two or more threads might want to update the values at the same time. However, it is possible that the lock may not be needed because it doesn’t matter if one thread updates another thread’s value since the only action taken by any of the threads is to remove an element from the list. Therefore, if a thread is removing an element by setting its value to null and another thread came in to set the same elements value to null, it doesn’t matter which thread updates the other. The value will be null afterall. This is my own theory and I still need to test if I’m imagining it right J
Welcome to Ali's blog, A computer engineer & scientist specialized in software development and algorithms.
Ali Tarhini 
Hi , thanks for the information. This is really helps for me to do my assignment.
hi man good thanks for the info..
do u have the code….. if u have the working code of both parallel programmin and the normal code will u mail me to shuaibindia007@gmail.com…. its urgent as i have to submit in few days else the exp given by u is enough to do it….. but its more than enought to explain…. thanks man.