Before we start
* Sudoku is puzzle first introduced in Japan; the rules and restrictions are explained below It is combinatorial puzzle which needs to fill up the empty cells such that none of the following constraints are violated: 1. No repetition in each row.
2. No repetition in each column.
3. No repetition in each square.
Our approach towards the puzzle
Every Sudoku can easily solved by Exhaustive search algorithm in an exponential time complexity, as shown below.
*
Lets assume we have n empty boxes to be filled in the puzzle. And we knew that every box have the possibilities as the set {1,2,3,4,5,6,7,8,9}. i.e. each empty square is having 9 possibilities; so total no possibilities are now become 9n . So the time complexity for this trivial procedure is in the order of O(9n), i.e. exponential complexity. * Suppose if assume tg is time required to generate the possibility and tt is time for testing the generated solution, then Total Time Taken is given by…
Total Time Taken(T.T.T) = 9n * ( tg + tt )
T.T.T = 9n * Tc where Tc = ( tg + tt )
As we see Tc is constant to increase the efficiency of this ES we need to decrease the first member of the above expression, i.e. 9n
So lets modify the ES to Modified ES and call the same as MES throughout this discussion...
Modified Exhaustive Search
* As we discussed in the previous page we need to reduce 9 n part of the T.T.T equation… To do this we can decrease ' 9 ' or ' n '. So lets first discuss how to reduce ' n '.
* Actually reducing ' n ' can be done by using well known AI Technique called Constraint Satisfaction .
* What is Constraint Satisfaction…?
Actually this is a method to solve the problems - in which the goal is to discover some problem state that satisfies a given set of constraints.
* As we know Sudoku has some constraints as stated in page 1… But here we are using this technique to solve only some part of the puzzle…
* As we see in the above board all squares are filled except the box at Row 2 and Column 2.
* And the possibilities for this empty box are the set of numbers between 1 to 9 which are not in Row 2, not in Column 2 and not in first square.
* So in general the set of possibilities for a box at Row m and Column n is given by…
P [ m , n ] = ( Su - Sm ) Л ( Su - Sn ) Л ( Su - Ssq( m, n ) )
Where Su = { 1, 2, 3, 4, 5, 6 ,7 ,8 ,9 }, Sm set of elements in row m, Sn set of elements in column n, Ssq(m,n) set of elements in the square to which the box with row m and column n associated with...
* If the cardinality of P is one then it is clear that the respective box as only one possibility; which can be filled up. So by calculating P for each void places we can fill up some void places ( sometimes all), and we simplify our further search in our problem solution space.
* After applying the above technique we can fill some voids; but one thing which is to be carefully observed here is, after filling some voids the new state of the board will affect the possibility sets of other unfilled boxes. So finding the possibility sets for each unfilled boxes again, might make some possibility sets to have the cardinality as one, which can normalized as explained.
* So by above discussion we conclude that the mentioned technique is a recursively applicable one.
So lets make this idea to work by constructing an algorithm for the same.
We are calling this Algorithm as FON ( stands for First One Normalize ).
It is called so because, It is applied first ( First ) to normalize ( Normalize ) the empty boxes with only one(One) possibility.
* Algorithm: Fon
//Input: Sudoku Board as SB
//Output: Modified board or Same board
N <- findNoOfVoids ( SB ) //Getting no of void places...
Pos[N] <- getPosListOfAllVoids ( SB ) //Finding the possibilities for all voids by CS
If IsFonnable(Pos) then //Checking whether Fon is applicable or not
SB <- Normalize ( SB, Pos ) //Normalizing and Updating the board
Return Fon(SB) //Calling recursively for further Fon
Else
Return SB //Returning on non-applicability of Fon
End If
* As we seen in the algorithm we assumed some methods and their description is given below…
1. findNoOfVoids ( SB ): This method returns the number of unfilled boxes in the board given as argument.
2. getPosListOfAllVoids ( SB ): This methods returns the possibility sets for all void places in the board given as argument. And this is the method where we're applying the Constraint Satisfaction ( CS ) idea.
3. IsFonnable ( Pos ): This method returns True if Pos is not empty and their exist at least one entry with cardinality one, else it returns False.
4. Normalize ( SB, Pos ) : This method fills the unique possibility boxes and returns the updated board.
* As we can conclude from the algorithm output description, Fon may or may not reduce the number of unfilled boxes. If it fails in the first step then we end up with the same state of the board. In contrast if it fills the all unfilled boxes ( recursively or just in one pass ) then we end with the solution itself. So the number of filled boxes by Fon is lies between zero and total number of voids.
i.e. If we consider nf is number of unfilled boxes which were resolved by Fon then,
0 ≤ nf ≤ n
* So after Fon the number of unfilled boxes left is given by,
N = n - nf
* Finally the n value is reduced to n - nf; which makes the T.T.T expression as
T.T.T = 9( n - nf) * Tc
T.T.T = 9N * Tc
* After doing the FON, if we still have voids; we need to move on to concrete analysis step.
Concrete analysis step is a hill climbing searching algorithm with a special technique of backtracking.
The nodes with less number of possibilities are considered first, during searching. The backtracking used here is different from normal backtracking by latter sense. And this will be explained in one of the next coming posts...
This app is now available online... Click here
No comments:
Post a Comment