09-07-2007 11:46 AM
Hello,
I have developed a Sodoku solver. For easy and medium Sodoku is work fine,
but for difficult Sokodu's the algorithm need to guess numbers for more
than one field.
I need to guess a whole path of number and make sure that I can increment
the path members in order to find the correct solution.
How to implement this? Is there a kind of pattern to this kind of problem?
Regards & Thanks,
Guido
09-07-2007 12:02 PM
I fail to see how this is a Abap OO -related question, but since it interests me I did the effort of looking for an algorithm in <a href="http://www.google.be/search?q=sudoku+algorithm">google</a> and came up with this :
http://www.di-mgt.com.au/sudoku.html
Algorithm
There are 3 stages:-
Start with a matrix of 81 squares each with 9 'possible' values
As you fill in a new number, remove all the possibles in (a) the same row, (b) the same column and (c) the same box.
First Stage: Work through each square in turn and see if it only has one possibility. If so, we've solved that square, so fill it in and remove all associated possibilities. Repeat this until you get no more changes.
This first stage solves most easy and medium problems outright.
2nd Stage: Now work through each row, column and box in turn and check all remaining values 1..9 in turn in each unsolved square of the set. See if we can find a square that can only have one possible value. This lets us fill in some more and then we repeat with stage 1 again.
This second stage solves most hard ones.
3rd Stage: If we've not solved it by now, we've finished the simple deterministic process and we now have to guess one of the possibles. Find the square with the least number of possibles and pick one of them. This gets tricky because we now have to remember all we fill in from now on so we can delete them all if we're wrong. Having guessed one square, repeat stages 1 and 2 again.
If our guess solves it, we're done. If not, delete all the guesses and pick the next guess. Repeat until we solve it.
And that was just from the first result.
And this one claims to be able to solve all puzzles : http://www.seedmagazine.com/news/2006/03/microscopy_and_the_art_of_sudo.php
09-07-2007 12:02 PM
I fail to see how this is a Abap OO -related question, but since it interests me I did the effort of looking for an algorithm in <a href="http://www.google.be/search?q=sudoku+algorithm">google</a> and came up with this :
http://www.di-mgt.com.au/sudoku.html
Algorithm
There are 3 stages:-
Start with a matrix of 81 squares each with 9 'possible' values
As you fill in a new number, remove all the possibles in (a) the same row, (b) the same column and (c) the same box.
First Stage: Work through each square in turn and see if it only has one possibility. If so, we've solved that square, so fill it in and remove all associated possibilities. Repeat this until you get no more changes.
This first stage solves most easy and medium problems outright.
2nd Stage: Now work through each row, column and box in turn and check all remaining values 1..9 in turn in each unsolved square of the set. See if we can find a square that can only have one possible value. This lets us fill in some more and then we repeat with stage 1 again.
This second stage solves most hard ones.
3rd Stage: If we've not solved it by now, we've finished the simple deterministic process and we now have to guess one of the possibles. Find the square with the least number of possibles and pick one of them. This gets tricky because we now have to remember all we fill in from now on so we can delete them all if we're wrong. Having guessed one square, repeat stages 1 and 2 again.
If our guess solves it, we're done. If not, delete all the guesses and pick the next guess. Repeat until we solve it.
And that was just from the first result.
And this one claims to be able to solve all puzzles : http://www.seedmagazine.com/news/2006/03/microscopy_and_the_art_of_sudo.php
09-07-2007 2:43 PM
Hello,
thanks for input!
I have cover the stage 1 and 2, but I failed to implement stage 3.
How to implement this tricky algorithm in ABAP OO? If procedural
ABAP offers a solution it should be no issue as well ;-).
Regards & Thanks & Nice weekend,
Guido