Application Development Discussions
Join the discussions or start your own on all things application development, including tools and APIs, programming models, and keeping your skills sharp.
cancel
Showing results for 
Search instead for 
Did you mean: 

Algorithm to solve a diffcult Sodoku

Former Member
0 Kudos

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

1 ACCEPTED SOLUTION

dhorions
Contributor
0 Kudos

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

2 REPLIES 2

dhorions
Contributor
0 Kudos

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

Former Member
0 Kudos

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