Introduction
To the uninitiated Sudoku is an addictive number game that has become very popular of late. Most local papers carry a daily puzzle, millions of commuters world wide can be seen hunched over on the way to and from the daily grind. The game is traditionally is a 9X9 grid, the goal is to ensure that each row, column and 3X3 box contain all the numbers 1 through 9. The game starts with some pre-defined numbers in random cells; the number filled depends on the difficulty, the lower the level, higher the pre filled numbers. Then it’s up to you and your powers of deduction to solve the remaining numbers.
There are many Solvers available, noticeably abscent was an ABAP version. As an exercised I thought I'd write one with a BSP front-end
Sudoku Solver
A prerequisite to solving the puzzle is ensuring it can be solved. Each cell needs to be validated with cells in the box it resides in plus the intersecting row and column, making sure that the value does not conflict with another entry and that there is at least one possible value achievable.
There are many different approaches to solving a Sudoku puzzle, the majority of them use a Backtracking search algorithm. Backtracking incorporates a Depth first search (DFS) approach, starting at the first cell try all possible values until you find one which works, then move on to the next cell, if you exhaust all possible values, backtrack to the previous cell and try the next value.
Creating New Games
Creating new games is relatively simple once the solver has been determined. There are 3 stages
The Code
The code is now available as a SAPlink nugget.
To download the source for the Sudoku app goto
http://abap-sudoku.googlecode.com/svn/trunk/
Currently there is no plug-in available of Message Classes, I can guarantee you there will be shortly as I have volunteered to write one.
In the mean time you will have to create message class ZBSP_SUDOKU manually and then cut and paste the messages from the provided txt file.
Conclusion
I had many plans for the BSP Sudoku application - possible values in a drop down list, cell hints, setting up real time checking, custom elements to name a few. An MDM project has meant I have had to put this excercise on hold for a while.
The one thing that I would like to revisit is the time it takes to solve a puzzle, on average I found it took 5 - 8 seconds to solve a puzzle on my laptop (duo 1.5 gig ram), slightly different times on other machines. For testing I found a puzzle on the internet which was deemed one of the hardest for a computer to solve (See load_games) and the best time on my computer was a little over 300 seconds (in background). I played around with a few different variations of the algorithm (DLX), this wasn't the problem, the constraint appears to be in the time it takes to read from a table. I will not post the time it took in a similar Java application I wrote, don't want another discussion on Java vs ABAP or even data structures vs string arrays. I would however be interested if someone out there has the time to investigate more effective options and the comparitive times they get.
To the uninitiated Sudoku is an addictive number game that has become very popular of late. Most local papers carry a daily puzzle, millions of commuters world wide can be seen hunched over on the way to and from the daily grind. The game is traditionally is a 9X9 grid, the goal is to ensure that each row, column and 3X3 box contain all the numbers 1 through 9. The game starts with some pre-defined numbers in random cells; the number filled depends on the difficulty, the lower the level, higher the pre filled numbers. Then it’s up to you and your powers of deduction to solve the remaining numbers.
There are many Solvers available, noticeably abscent was an ABAP version. As an exercised I thought I'd write one with a BSP front-end
Sudoku Solver
A prerequisite to solving the puzzle is ensuring it can be solved. Each cell needs to be validated with cells in the box it resides in plus the intersecting row and column, making sure that the value does not conflict with another entry and that there is at least one possible value achievable.
There are many different approaches to solving a Sudoku puzzle, the majority of them use a Backtracking search algorithm. Backtracking incorporates a Depth first search (DFS) approach, starting at the first cell try all possible values until you find one which works, then move on to the next cell, if you exhaust all possible values, backtrack to the previous cell and try the next value.
Creating New Games
Creating new games is relatively simple once the solver has been determined. There are 3 stages
 | 1. Fill 3 boxes without any intersection with random values 1 - 9 |
 | 2. Use the solver to find solution |
 | 3. Randomly remove cells until you reach the number of clues associated with the skill level |
The Code
The code is now available as a SAPlink nugget.
| To download the latest version of SAPlink goto http://saplink.googlecode.com/svn/Current%20Release/ |  |
http://abap-sudoku.googlecode.com/svn/trunk/
Currently there is no plug-in available of Message Classes, I can guarantee you there will be shortly as I have volunteered to write one.
In the mean time you will have to create message class ZBSP_SUDOKU manually and then cut and paste the messages from the provided txt file.
Conclusion
I had many plans for the BSP Sudoku application - possible values in a drop down list, cell hints, setting up real time checking, custom elements to name a few. An MDM project has meant I have had to put this excercise on hold for a while.
The one thing that I would like to revisit is the time it takes to solve a puzzle, on average I found it took 5 - 8 seconds to solve a puzzle on my laptop (duo 1.5 gig ram), slightly different times on other machines. For testing I found a puzzle on the internet which was deemed one of the hardest for a computer to solve (See load_games) and the best time on my computer was a little over 300 seconds (in background). I played around with a few different variations of the algorithm (DLX), this wasn't the problem, the constraint appears to be in the time it takes to read from a table. I will not post the time it took in a similar Java application I wrote, don't want another discussion on Java vs ABAP or even data structures vs string arrays. I would however be interested if someone out there has the time to investigate more effective options and the comparitive times they get.
9 Comments
