As mentioned in my previous articles this solver is based on the artificial intelligence technique of the company MIBS. The first version was built in 3 days to show the power of this technique. The second version was been built in 2 weeks. Because this software is part of the MIBS project planner promotion campaign to show the power of this technique and this campaign is now in the final phase. Therefore a final article about the SUDOKU solver is made and it contains a third rule in solving the SUDOKU squares.
SUDOKU game is today a very popular game. The basic rule is that all rows, colons and the 4 3X3 squares must contain the numbers 1, 2, 3, 4, 5, 6, 7, 8 and 9.
The first 2 rules correspond with many articles describing solving the SUDOKU square techniques.
The other techniques are quite complicated and an iteration solution is used here.
In my previous article I mentioned 2 rules which were implemented. We also give some results in solving different SUDOKU squares.
In some cases the square are not automatically solved.
In those cases I mentioned that the tool is still a help in solving the squares because a list of the potential cells can be produced.
This document describes the optimization of this list and also the application of the third rule. There is only one solution.
The optimized list is an evaluated basic list where a selection is done. We will first discuss the content and then how you can use it in solving SUDOKU squares. Layout of the optimized list
psudsql30
HCEL
NTP
TP
GRPNR
Expr1
A6
3
V
1
0,5
A6
8
V
1
0,5
A8
3
V
1
1,5
A8
8
V
1
0,5
E8
2
S
6
1
E8
6
S
6
2
F8
2
S
6
1
F8
6
S
6
2
The colon HCEL contains the potential cells. This they can have only 2 values which is the result of applying the first 2 rules. The colon NTP shows the possible values. The colon TP is the type of area (row, colon or square) The colon GRPNR : sequence number The colon Expr1 probability estimate for this value.
The way to use this list. The contains groups of 4 lines which are the remaining cells of that area We have 2 possible values for the 2 cells so there are 2 solutions where 1 is the correct one. Let's take the example; A6, A8 can have the values 3, 8. So 2 possibilities {A6:3; A8:8} and {A6:8; A8:3} one of them is correct. The probability field can be used to choice a priority in the 2 possibilities. But there is no guarantee.
The advise is to apply 1 set at the time not all possible sets, because it is a choice. Limit yourself to a set of two possibilities. You know that 1 possibility is correct. In the above example use the set of area V1 or S6 but not both
On expert level it is possible that you have a cascade of rule 3 problems. So can this be a hopeless problem? The answer is NO because we know there is 1 solution. We have solved a lot of expert SUDOKU squares with this last version in all cases the results are.
Cascade number
Number of runs
1
1-2
2
1-2-3
3
1-2-3-4
So the solution strategy is not hopeless: maximum number of trials is linear with the cascade number. The reason for this fact is that when we took a wrong choice we ended very fast into a non solved solution. A disadvantage is that you have to track your trials
Author: Dirk Verhelst
Author Bio:
You want to know more information about artificial intelligent technique of the company MIBS or you want to know more about this SUDOKU solver. Visit the site www.mibs.be
