Skip to Content
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

image

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

image 1. Fill 3 boxes without any intersection with random values 1 – 9
image 2. Use the solver to find solution
image 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/
do yourself a favor

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 report this post you need to login first.

9 Comments

You must be Logged on to comment or reply to a post.

    1. Ed Herrmann
      Hi John,

      Cool app!  I am looking through your objects above, and you should be able to package and distribute all these in a nugget via SAPlink.  The only object we don’t have right now available from your app is the message class.  The message class shouldn’t be too hard for everyone to copy and paste manually, but ideally someone would create the plugin for message classes.  Let me know if you have any questions.

      -ewH

      (0) 
      1. John Patterson Post author
        Hi Edward,
        SAPlink is cool. I put all the objects into a nugget. Only question i have is how do i link the nugget to the blog.

        cheers
        jsp

        (0) 
        1. Ed Herrmann
          Hi John, great to hear that you like SAPlink!
          I have one quick comment and then an answer to your question.
          COMMENT
          In the current version of SAPlink 0.1.1, there were some bugs with classes that utilized interfaces. We have fixed the bugs and plan on releasing them in our next minor version this week. I would be more than happy to try to coordinate the release with your nugget release.  I am also trying to coordinate it with Thomas Jung’s release of his BSP extension that is an SAPLink and my first real community project.
          The fixes are to the class plugin and you can download and install the latest version here.
          I would definitely recommend re-exporting your nugget with the new version. I apologize for not mentioning this earlier, as I overlooked that you had some interfaces in your classes.

          ANSWER
          To answer your question about where to attach a nugget to a blog, we are currently talking with the SDN team to hopefully have a way built-in to host slinkees and nuggets right here on SDN. For now, the easiest way is to create your own google code page to host all your SAPlink files.  It’s easy and free and our own Ryan Quackenboss provides a quick and dirty tutorial on it in his weblog Show me your .slnk and I will show you mine (2of2).

          I hope this helps.  Feel free to post to our SAPlink group or email me with any questions, or report any bugs at our own google SAPlink project page

          -ewH

          (0) 
  1. Detlev Beutner
    … I also don’t want to have a general discussion on Java vs ABAP about this, but I really just wonder… I have implemented I think one of the shortest, even if definitely not fastest solutions in Java several months ago. Tested it with your input code (300 seconds? “Three hundred”? 5 minutes? Not milliseconds???), it takes 1.6 seconds (and that’s _really_ long). And I have no SPARC station at home, promised 😉
    Probably your station went out for a cigarette in between? 😉
    Best regards, Detlev
    (0) 
    1. John Patterson Post author
      Hi Detlev,
      You forgot to add the runtime took 1.5 seconds to load. I found a browser based dhtml solution which solves in about the same time, but thems apples, not oranges.
      (0) 

Leave a Reply