Fat man and his mixed bag of goodies

OO, Patterns and Sudoku Solver: Part 2

Manoj.Oswal — Mon, 07 May 2007 06:10:00 GMT

In the first part we covered the actual usage of the Sudoku solver and in this part we are going to cover the different techniques and logic used to solve this problem and some statistics and pros and cons of each method.

Brute force solver

Brute force solver is the simplest but not the most efficient method to solve problems like sudoku. It relies on the sheer speed and number crunching capability of a modern microprocessor. In simple terms it tries out each possibility till it finds a valid solution to a given problem. In the current context it tries putting different possible numbers in each unsolved cell till a valid solution is found. You can imagine this can take some time if there are lots of unsolved cells. To minimise the number of iterations we could use the back tracking algorithm with brute force solver. Back tracking reduces the number of iterations by not starting from the beginning each time the loop fails at a particular point. Instead it tries different number in the current cell till all the valid numbers fail in the current cell and then it goes back just one step to previous cell tries different number there and then continues in this manner till a valid solution is found. This greatly reduces the number of iterations. The brute force solver I have implemented in this solution uses the backtracking technique.

Quick solver (Serial cells)

Brute force with backtracking improves the solving time but is only good enough for grid of a certain size as the solving time exponentially increases with number of unresolved cells. To give you an example, an empty grid of 4 X 4 (16 unresolved cells in total) takes typically 62 milliseconds on my pc but it takes 13 seconds to solve an empty grid of 9 X 9 (81 unresolved cells in total). That’s approximately 210 times increase in solving time for 5 folds increase in unresolved cell numbers. And for an empty 16 X 16 grid I stopped processing after 15 minutes. So effectively its performance becomes unacceptable at that size. This is when injecting domain knowledge in to brute force solving technique becomes essential. The quick solver does exactly that. We know the sudoku rules and we can use those rules to optimise our solver.

No Duplicates Rule

We know that each unsolved cell can have a value from the possible number values set. e.q in a 9 X 9 grid any unsolved cell can only have a value between 1 to 9. But we can reduce that possible values set by removing values that a particular cell can’t have. And according to the rules; no row, column or square can have duplicates. So if we take all the values from the solved cells and then remove them from the appropriate row, column and square then we can greatly reduce the number of possible values for each unsolved cell. Let me give you an example:

In the figure given above, the cells with the single blue coloured values are resolved cells. And the cells with multiple black coloured values are the unresolved cells, each with initial possible values set. So if we apply the no duplicates rule then the yellow shaded cell (row 1 column 2) with value 2 can’t have the same value in its corresponding row (outlined in red), column (outlined in blue) or square (outlined in green). This means we can safely remove each blue or fixed value from its corresponding row, column and square. That leaves us with a sudoku as shown in the figure given below:

As you can see the possible values set in each unresolved cell has greatly reduced. Apply this rule to most simple and some medium difficulty level sudoku that you find in a newspaper. And after each iteration of removing duplicates; you will find at least one unresolved cell left with only one possible value. That is the resolved value for that cell. And now you can continue removing the recently solved value from all the unresolved cells of its corresponding row, column and square.

If we keep doing that then one of the following two things is going to happen:

1. We get a solved sudoku. (Hurray!)

2. We still have some unresolved cells.

If we arrive at 2, then is this the stage at which we start guessing values?

No, there is at least one more rule we can implement.

The Unique Square Value Rule

Sometimes after all possible duplicates removal you will come across the sudoku state as shown below:

You can place value 1 in the yellow shaded cell of row 2, column 8. Why? If you look at all the possible values for all the unresolved cells in that square you will find that 1 is only present once. And we need to put 1 somewhere in that square and only possible square we can put 1 is the yellow shaded cell and hence we can put 1 in that cell even though there are more than one possible values available for that cell. There are a few more cells with unique square values and they are all shaded in red.

We can only run USV (unique square value) rule if there are no more duplicates to remove. If we run this rule before all the duplicates are removed then the sudoku solver can put wrong values in the cells. Now after applying USV rule we get a few more resolved cells hence a few more duplicates to remove. And now if we keep doing that in a loop, again we come across one of the following two situations:

1. We get a solved sudoku. (Hurray!)

2. We still have some unresolved cells.

If we are still at 2 then we guess a value for the first unresolved cell found and then continue applying duplicates and USV rules. If we keep doing this then you are guaranteed to find a solution to any valid or solvable sudoku.

Quick solver (Possible Vals)

What can we do to reduce the number of iterations further? The quick solver (serial cells) puts the guessed values in a serial order. It starts scanning for unresolved cell starting from row 1, column 1 and moves on to cell in row 1, column 2 till it finds an unsolved cell. If no such cell is found in row 1 then it moves to row 2 and so on. If we alter this order then we are bound to get different number of iterations. What if we order the unsolved cells by the possible number of values they can have? So the unsolved cell with two possible values remaining comes on top and the cell with three possible values remaining next and so on. With this sort of ordering, the numbers of different starting path are less and discarding the wrong path happens very early on. Thus the numbers of iterations are reduced drastically in most cases. In addition to that the amount of work needed to code this type of solver on top of previous one is trivial using the inheritance (More details on that in the next part.).

Is Brute Force Solver Bad?

Here is the stats table for the numerical minded (all the solving times given are in milliseconds):

	Grid size
	4 X 4	9 X 9	16 X 16	25 X 25
Brute Force	62	13000	30000	Too long
Quick Solver (Serial cell)	45	750	1900	Too long
Quick Solver (Pos vals)	45	250	2000	9000

And here is the graphical view of the table (some values are changed in the graph to better illustrate the relative difference in the solving curves):

This just re-emphasises the fact that after certain complexity threshold the brute force solving technique becomes unacceptable.

But is the brute force technique always bad? In my opinion that’s not true. This technique definitely has its advantages and the most notable is the cheaper cost to develop and maintain it over others. In the scenario given above, the quick solver is always fast compared to the brute force solver. But in many other cases it’s quite possible that due to the added processing required, the quick solver kind of technique is slower to brute force at low complexity levels. And hence offer no real benefit at lower complexity levels. In those kinds of scenarios the Brute force is the winner. Let me illustrate it further with the help of the following hypothetical graph:

It is almost identical to the previous graph. Only the fast quick solver is kept and the red horizontal line is added; it is a sample ideal acceptable performance threshold for this app which is around 125 milliseconds in this case. The purple curve represents brute force solver and the green curve illustrate the quick solver. The point of intersection between these two curves is circled in red. This is the point where the quick solver starts getting faster compared to the brute force solver. Let’s call it the brute force performance cross over point. The point of intersection between the brute force curve and the performance threshold line is circled in green this is the point after which the performance of the brute force solver is consistently inferior to the ideal acceptable performance. Let’s call it the brute force performance cut-off point. So does this mean this is the point after which the brute force solver should be discarded as a rule of thumb? No, in many cases it is quite possible that the higher cost of developing better solution can push the acceptable performance threshold a little lower. That point is shown with filled brown circle. Let’s call it the brute force viability cut-off point. This is the point after which the brute force can’t be accepted as a solution.

Let’s put some more colour around the brute force viability cut-off point:

The yellow shaded region is the brute force operation zone.

If your application is always going to operate within the brute force operation zone then the brute force solver is your winner and you can save some money by not investing in developing faster but costlier solutions. If you know for sure that your app is going to operate beyond this region then you need to have better solution like the quick solver. In case of uncertainty where you know at the start you are going to be operating within the brute force operation zone, but not sure whether you will operate beyond that zone in the future. In such cases you need to implement something that will allow you to plug in better solver if and when the need arises.

This is where the design patterns can come to your rescue. In this particular case you can implement the Strategy pattern. This particular pattern allows you to plug in different strategies depending on the requirements. So you can have your application running with brute force solver strategy and in the future you can swap it with quick solver strategy if required. I have implemented the strategy pattern in the Sudoku Solver.

More details about the strategy pattern and the code walkthrough of the critical areas will be covered in the next part. I will also be posting the complete source code in the next part. Some of the comments on the previous posting have mentioned the very obvious short comings of the UI. And I had replied that the actual code have many hidden goodies that are not utilised in the front end due to the time constraints and the lack of focus in that UI. I will cover those areas and will explain how to use those goodies to help you make a better sudoku solver.

OO, Patterns and Sudoku Solver: Part 1

Manoj.Oswal — Sun, 22 Apr 2007 23:11:00 GMT

Primary focus of this blog entry is to demonstrate some of the power and flexibility offered by object orientated programming and design patterns. I will try to demonstrate these techniques and how to use them to solve complex problems like Sudoku.

I chose Sudoku rather than "Hello world" because it's fun, complex and seems like all the rage at the moment.

I have divided this entry in to multiple parts for the benefit of all.

Part 1 is for people who are only interested in acquiring a free Sudoku solver but don't necessarily give a damn about any of the programming techniques mentioned above.

Part 2 is for those who are interested in knowing the different techniques and logic used to solve the problem and some statistics and pros and cons of each method.

Part 3 will be for developers who are interested into the actual code walkthrough.

Well without any further babble I will describe the usage of the Sudoku solver.

The main screen of Sudoku Solver

Starting a new sudoku.

Click on New menu item and it will pop up the following dialog box

Choose the required grid size (9 X 9 is the standard size).
Choose the solving strategy (quick solver possible vals is the fastest one).
Tick the populate sample data check box if you want to populate a sample sudoku.
Click OK button.

Now you will have a sudoku on the main screen as shown before.

Click on any blank cell you want to put a value in and it will show you a drop down box with values as shown below

Select a value and it will be placed in that cell.

Solving sudoku

Once you have finished placing all the values click on the Solve menu item to solve the sudoku.

The tool will solve any sudoku with a valid solution.

Restarting a Sudoku.

If you want to start a new sudoku based on the same grid and solving strategy then click on Reset menu else start over a new sudoku based on new options by clicking on New menu item again.

More...

You can also use this tool as a sudoku generator by placing just a couple of random values and clicking solve button.

Any grid bigger than 25 X 25 will be pure academic and with no fun value to the sudoku fans. So I have restricted it to that size through UI but for the benefit of the geeks the underlying code is made capable of solving sudoku of any grid size and is only restricted by the memory and processing power.

You can download the zip file for this sudoku solver at the end of this post. Please note that you will need .NET 2 runtime on your machine in order to run this programme. If you dont have it then you can download it from Microsoft website here.

SQL generic split function

Manoj.Oswal — Wed, 31 Jan 2007 11:02:00 GMT

Last Friday I was discussing with Jamie one of the SQL function I was working on. At the end of it Jamie gave me some encouragement to blog it (“If I don’t see a blog on it by Monday, I will be having a word with you!” Jamie).

With that support here I am, finally writing my first blog.

My current assignment is with the world’s leading, specialist insurance market. The situation I came across was like this, I was receiving a comma delimited string in one of my stored procedures and it was meant to be used in a where clause.

e.q.

SELECT … FROM … WHERE ITEMID IN (Comma delimited string)

The first solution that sprang to my mind was to construct a dynamic SQL in stored procedure utilising the delimited string and executing it at the end of it. This would have taken away all the obvious benefits a stored procedure offers plus would have opened the doors to potential abuse of this stored proc. Another solution would have been to use OPENXML but I didn't have a choice of getting input string in XML format.

After some further thinking and search the better solution seemed to be a SQL function accepting comma delimited string and returning a resultset which then could be used in a WHERE clause or a JOIN.

The first function developed worked to the expectations and I was delighted with it. But after a few minutes, questions started popping up in my head about the inflexibility of this function. First it was assuming the string would always be delimited with a comma and hence the other implication was a delimiter would always be a single character. Secondly the function was returning a single column table of type int. So the input and output format were fixed (arrrrrrggh!!!).

So before letting those limitations haunt me in the middle of the night, I decided to make this function a bit more generic and what follows is the result of those efforts:

-- ===========================================================

-- Author: Manoj Oswal (Conchango)

-- Create date: 26 Jan 2007

-- Description: Generic Split function

-- Accepts List and separator as string

-- Returns single variant column TABLE of items

-- ===========================================================

CREATE FUNCTION [dbo].[GenericStringSplit]

(

@List VARCHAR(8000),

@Separator VARCHAR(10)

)

RETURNS

@ItemsList TABLE

(

Item SQL_VARIANT

)

BEGIN

DECLARE @CurrItem SQL_VARIANT, @Pos INT

SET @List = LTRIM(RTRIM(@List))+ @Separator

SET @Pos = CHARINDEX(@Separator, @List, 1)

IF REPLACE(@List, @Separator, '') <> ''

BEGIN

WHILE @Pos > 0

BEGIN

SET @CurrItem = LTRIM(RTRIM(LEFT(@List, (@Pos -1 ))))

IF @CurrItem <> ''

BEGIN

INSERT INTO @ItemsList (Item)

VALUES (@CurrItem)

END

SET @List = RIGHT(@List,(LEN(@List) - (@Pos + LEN(@Separator)-1)))

SET @Pos = CHARINDEX(@Separator, @List, 1)

END

RETURN

END

The above function now accepts a delimited string and a separator up to 10 char and returns a single column table of sql_variant. The consuming SQL can then cast the return of this function with the desired type.

Usage:

SELECT CAST(Item AS INT) FROM [GenericStringSplit]('1;-2;-3;-4;-5',';-')

SELECT CAST(Item AS DATETIME) FROM [GenericStringSplit]('12 feb 2005~~~10 Jan 2006~~~15 Jan 2006','~~~')

One of the limitations of this function is the input list size is limited to 8000. VARCHAR(MAX) is the possible solution for this problem but that also means some more changes in the function namely changing @CurrItem type to something like VARCHAR(100). This is due to the incompatibility of VARCHAR(MAX) and SQL_VARIANT.

Interestingly enough the same day I had to write something to do the opposite of the above mentioned function. I had to write something that returned a comma separated list of items from a table. The solution I used is as follows:

DECLARE @List VARCHAR(MAX)

SET @List = ''

SELECT @List = @LIST + ',' + COLNAME FROM TABLE

IF @List <>''

BEGIN

SET @List = STUFF(@List,1,1,'')

END

SELECT @List

Please send any feedback/suggestions you have, to further improve this work.