How To Increase Your Internet Connection Speed

It is possible to gain an extra 20% of bandwidth out of your internet connection. By default Windows XP, Windows Vista and also Windows 7 reserve 20% of your Internet speed for use by services like windows update and other programs that require frequent internet access. This limit is configurable from Group policy Object Editor. When we set this value to 0, the reserved 20% will be added to your browsing and download speed. Below are the configuration steps:

1. Start -> Run -> GPEdit.msc
2. Expand the Administrative Templates under Computer Configuration
3. Expand the Network tab
4. Select QoS Packet Scheduler
5. Click on Limit Reservable Bandwidth
6. Enable the check box
7. Change the Bandwidth limit to 0%
8. Start -> Run -> “gpupdate /force” Or restart your computer

Hacking Windows 7: The God Mode

Image via CrunchBase

One of the secrets of Windows 7 that is undocumented by Microsoft is the secret option known as God Mode.

GodMode is simply a hidden control panel that contains everything about windows 7 configuration options and settings, all located in one place plus additional features that are not easily found in the ordinary Control Panel. Below is a picture of a small part of the options found in GodMode panel.

The trick to access the GodMode is simple, just follow these steps:

• Create a new folder
• Name the folder with the following name: GodMode.{ED7BA470-8E54-465E-825C-99712043E01C}
• Once created, you should see the folder icon changed to the control panel icon.

Give it a try and explore the powerful and useful hidden features in windows 7. I have not tested the GodMode on Windows Vista. Try it out and let us know about the results!

Exception Handling Guidelines

Image via Wikipedia

Follow class naming conventions, but add Exception to the end of the name.
Some rules listed below are to be followed in Exceptions blocks or classes:

1. Never do a “catch” exception and do nothing. If you hide an exception, you will never know if the exception happened or not.
2. In case of exceptions, give a friendly message to the user, but log the actual error with all possible details about the error, including the time it occurred, method and class name etc.
3. Always catch only the specific exception, not generic exception as well as system exceptions.
4. You can have an application level (thread level) error handler where you can handle all general exceptions. In case of an ‘unexpected general error’, this error handler should catch the exception and should log the error in addition to
   giving a friendly message to the user before closing the application, or allowing the user to ‘ignore and proceed’.
5. Do not write try-catch in all your methods. Use it only if there is a possibility that a specific exception may occur. For example, if you are writing into a file, handle only FileIOException.
6. Do not write very large try-catch blocks. If required, write separate try-catch for each task you perform and enclose only the specific piece of code inside the try-catch. This will help you find which piece of code generated the exception and you can give specific error message to the user.
7. You may write your own custom exception classes, if required in your application. Do not derive your custom exceptions from the base class SystemException. Instead, inherit from ApplicationException.
8. To guarantee resources are cleaned up when an exception occurs, use a try/finally block. Close the resources in the finally clause. Using a try/finally block ensures that resources are disposed even if an exception occurs.
9. Error messages should help the user to solve the problem. Never give error messages like “Error in Application”, “There is an error” etc. Instead give specific messages like “Failed to update database. Make sure the login id and password are correct.”
10. When displaying error messages, in addition to telling what is wrong, the message should also tell what the user should do to solve the problem. Instead of message like “Failed to update database.” suggest what should the user do: “Failed to update database. Make sure the login id and password are correct.”
11. Show short and friendly message to the user. But log the actual error with all possible information. This will help a lot in diagnosing problems.
12. Define a global error handler in Global.asax to catch any exceptions that are not handled in code. You should log all exceptions in the event log to record them for tracking and later analysis.

Adding IntelliSense for JQuery in Visual Studio 2008

To set up IntelliSense for JQuery you will need to download the JQuery Documentation File
from the JQuery site.

At the top of the JavaScript file in which you would like to have jQuery IntelliSense enabled, you will need to add a line to reference
the documentation file:

                                        /// <reference path="jquery-1.3.2-vsdoc2.js" />

If you downloaded jQuery and saved it to your project Visual Studio will look for the vsdoc.js file automatically if
the following conditions are met.

• You downloaded and installed the hotfix for Visual Studio.
• jQuery and the documentation file need to be named the same with the exception that the documentation file end with -vsdoc.js.
  So when you add jQuery to your project make sure to rename them similarly. For instance, jquery-1.3.2.js is your jQuery library,
  Visual Studio will look for the documentation file at jquery-1.3.2-vsdoc.js and load it.

  (Note: the jQuery 1.3.2 documentation file is named jquery-1.3.2-vsdoc2.js on the Download page so make sure you take out
  the 2 so that the file will be found by Visual Studio).

• To test to make sure the documentation file loaded correctly, you can type $( and you should be presented with some documentation.

The network BIOS command limit has been reached

Image via Wikipedia

When you are building an asp.net deployment project, you may often recieve an ASPNETCOMPILER error “The network BIOS command limit has been reached” . As describes by Microsoft, the error occurs because of the following reasons:

This issue may occur if the client computer submits simultaneous, long-term requests against a file server that uses the Server Message Block (SMB) protocol. An example of a long-term request is when a client computer uses the FindFirstChangeNotification function to monitor a server share for changes.
This issue may occur if the MaxCmds registry value setting on the client is less than 50, or the MaxMpxCt registry value setting on the server is less than 50.

To resolve this issue, verify that the MaxCmds and MaxMpxCt registry values are set to 50 or more. To do this, follow these steps:

Click Start -> Run – > “regedit”
Navigate to the following registry key:
HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\lanmanworkstation\parameters
Open the MaxCmds entry in the right listview.
In the Value data, enter a value of 50 or more.
Navigate to the following registry key:
HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\lanmanserver\parameters
Open the MaxMpxCt entry in the right listview.
In the Value data, enter a value of 50 or more.
Restart your computer for the changes to take effect.

Note The MaxCmds and MaxMpxCt registry entries are REG_DWORD decimal entries. If they do not exist on your computer, you can create them as new REG_DWORD values. The range of values for these registry entries is between 0 and 65535.

Collection was modified; enumeration operation may not execute

Image via Wikipedia

The error occurs when you are performing a for each loop over a generic list or a collection and there is a line of code inside the loop that is trying to modify the contents of the list. Take a look at the code below :

                                        Dim myList As New List(Of Integer)
                                        myList.Add(1)
                                        myList.Add(2)
                                        myList.Add(3)
                                        myList.Add(4)
                                        myList.Add(5)
                                        For Each i As Integer In myList
                                            myList.Remove(i)
                                        Next

the above code will throw an InvalidOperationException because we are removing items from the list while we are still iterating over its items using the for each loop.

a simple fix to the above code would be replacing the for each loop with the standard index loop as follows :

                                      For i As Integer = 0 To myList.Count - 1
                                            myList.Remove(i)
                                        Next

Cross-thread operation not valid: Control ‘ControlName’ accessed from a thread other than the thread it was created on

Image via Wikipedia

This is a common error when you are developing a multithreading application you often recieve an InvalidOperationException
indicating that a thread is trying to access an object that was created on another thread. A typical code block that generates this
error is shown below :

Dim th As New Threading.Thread(AddressOf test)
 

Private Sub test()
    TextBox1.Text = "using textbox from another thread"
End Sub


Private Sub Form1_Load(ByVal sender As System.Object, _ 
 ByVal e As System.EventArgs) Handles MyBase.Load
     th.Start()
End Sub

In the code above, TextBox1 is a normal textbox placed in the form. As we predicted, the error is thrown because TextBox1 belongs to main thread
, which is the single thread that runs the form and th is another thread accessing the textbox from the test function. To resolve
this problem, each control must be exclusively accessed from it belonging thread. What we are talking about here is to apply
context switching whenever we need to access controls on different threads. This is easy to do in .net framework. In face, we can
also add a small functionality to check whether a cross threading operation is required before we actually go on and swtich the context
because context switching has its performance penalties.

Using the Invoke method of the form, we can pass in a MethodInvoker object, which is a delegate specifying the address of the
function that we would like to invoke in case if an invokation is required by the form’s thread. To do the actual testing if an invokation
is needed, we use the form’s InvokeRequired property. Below is the working version of the code:

Dim th As New Threading.Thread(AddressOf test)
 

Private Sub test()
      If Me.InvokeRequired Then
             Me.Invoke(New MethodInvoker(AddressOf test))
       Else
                TextBox1.Text = "using textbox from another thread"
        End If
End Sub

Private Sub Form1_Load(ByVal sender As System.Object, _ 
 ByVal e As System.EventArgs) Handles MyBase.Load
     th.Start()
End Sub

Sequence contains no elements

Image via Wikipedia

The error occurs when you try to access an object returned by a Linq query with 0 elements in the result set an
InvalidOperationException is thrown. Below is a simulation to generate the error:

Dim productQuery = From p In context.Products Where p.ID = -1 Select p

Dim p As Product = productQuery.Single()

An exception is thrown by the Single() method because the productQuery object has no products inside and the Single() method is
trying to reach the first entity in the productQuery.

To avoid this problem, we must check whether productQuery is containing some items or not. Here is the correct way to do it:

                                    Dim productQuery = From p In context.Products Where p.ID = -1 Select p 
                                    If productQuery.Count > 0 Then
                                            Dim p As Product = productQuery.Single()
                                    Else
                                            Return Nothing
                                    End If

This row already belongs to another table

Occurs when you copy a DataRow from one DataTable to another throwing an ArgumentException

The error occurs because the same datarow object could not be added to different datatables.The best solution is using
the DataTable.ImportRow method which creates an exact copy of the row and adds it to the other table. However, in order to use this function
, both tables should have the same schema which is achieved using a method call to DataTable.Clone() to copy shema only or DataTable.Copy() to copy both data and schema. The code below shows how to do this:

Dim dt As New DataTable

'dt = FillRowFromDataBase

Dim dtClone As DataTable = dt.Clone

For Each row As DataRow In dt.Rows

dtClone.ImportRow(row)Next

Parallel Depth-First Sudoku Solver Algorithm

Image via Wikipedia

Preparing to go parallel with depth-first search using Sudoku as case study

Ali Tarhini

04/06/2011

Contents

1. What is Sudoku?.
2. Rules of Sudoku.
3. Computational Complexity.
4. Sudoku Solving Techniques.
5. Elimination.
6. Finding Lone Rangers.
7. Finding Twins.
8. Finding Triplets.
9. Brute-Force Elimination.
10. 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×10²¹ [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