- SAP Community
- Groups
- Interest Groups
- Application Development
- Discussions
- Algorithm to solve a diffcult Sodoku

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.

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Mute
- Printer Friendly Page

Algorithm to solve a diffcult Sodoku

Former Member

Options

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

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

- SAP Managed Tags:
- ABAP Development

1 ACCEPTED SOLUTION

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

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

- SAP Managed Tags:
- ABAP Development

2 REPLIES 2

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

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

- SAP Managed Tags:
- ABAP Development

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

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

- SAP Managed Tags:
- ABAP Development