Welcome!

PowerBuilder Authors: Chris Pollach, Yeshim Deniz, Jayaram Krishnaswamy, Kevin Benedict, Avi Rosenthal

Related Topics: PowerBuilder, Mobile IoT

PowerBuilder: Article

Pocket Sudoku

It's a numbers game

It's amazing how popular Sudoku has become in the last few months. You'll find one in nearly every daily magazine here in Austria. When I started to jump on this train (yes, I solve at least one Sudoku a day), I thought it would be amazing if we could have a version written completely in our number-one development tool, PowerBuilder, or it's small brother PocketBuilder. Since I wanted to be able to carry it around with me, I decided to write it in PocketBuilder 2.04 (because of its wonderful new support for horizontal/vertical windows) so that it would also support one of my new gadgets - the MDA PRO. Let's first look a little bit at the history of Sudoki and how it's played and, last but not least, how the solution is implemented.

History of Sudoku The name Sudoku is the Japanese abbreviation of a longer phrase: "suji wa dokushin ni kagiru," meaning "the digits must remain single." It's a trademark of the puzzle publisher Nikoli in Japan; you may know the original U.S. title - Number Place. As you can read on their homepage (www.nikoli.co.jp), it was not invented by them; they found it in an American puzzle magazine (it seems that it was first published in the late 1970s in Math Puzzles and Logic Problems magazine by Dell Magazines). For this puzzle Dell took Euler's Latin Square concept and applied it to a 9x9 grid with the addition of nine 3x3 sub-grids, or boxes, each containing all numbers from 1 to 9. Nikoli introduced this puzzle to the Japanese readers in 1984. At first the title of the puzzle was "Suji wa dokushin ni kagiru." But, as you can imagine, this title is too long, so it was abbreviated to Sudoku. So "SU" means number and "DOKU" means single. So, the Sudoku concept was not invented in Japan (which a lot of people may believe), but the name Sudoku was. In the late '80s, Sudoku became one of the best-selling puzzles in Japan; however, during that time hardly anyone in Europe knew anything about or paid any attention to the game Sudoku.

At the end of 2004 ,Wayne Gould, a puzzle fan and a computer programmer who has written a computer program that generates Sudoku puzzles of different difficulty levels, visited London trying to convince the editors of The Times to publish Sudoku puzzles. The Times launched their first Sudoku puzzle on November 12, 2004. By the end of May 2005, the puzzle was regularly published in many national newspapers in the UK, including The Daily Telegraph, The Independent, The Guardian, The Sun, and The Daily Mirror. In April 2005 Sudoku arrived back at Manhattan as a regular feature in the New York Post. On Monday, July 11, the Sudoku craze spread to other parts of the U.S. when both The Daily News and USA Today launched Sudoku puzzles on the same day. In both cases, the Sudoku puzzles replaced the traditional crosswords and bridge columns.

Today there are Sudoku clubs, chat rooms, strategy books, videos, mobile phone games, card games, competitions, and even a Sudoku game show. Sudoku has also sprung up in newspapers all over the world and is commonly described as the "fastest growing puzzle in the world." Read more in the Wikipedia article at http://en.wikipedia.org/wiki/Sudoku.

How to Play
The game of Sudoku is very simple. There are just three rules:

  1. Each row must have the numbers 1-9 occurring just once
  2. Each column must have the numbers 1-9 occurring just once
  3. And the numbers 1-9 must occur just once in each of the 9 sub-boxes of the grid.

Okay, that was the short story, but you might be interested in hearing more about it and how to use the PKSudoku application I have written.

When you begin a new Sudoku, some of the squares will already have numbers in them. The easier the Sudoku, the more squares that will be filled in (there is a total of 81 squares and depending on the level you will have 44, 34, or 28 hints). These squares cannot be altered to change the value. The puzzler is only able to change the values for the free (blank) squares.

To place numbers in the main puzzle board, first select a number on the right by clicking on the number you want. All squares with this value will change the background color, so it's easy to check if the number is really correct. Next, click on the square you want in the main puzzle board. The number will appear in the square; if the number is not correct, the number will be displayed crossed out. To remove a wrong number from the main puzzle board, select the blank square from the right, then click on the number you want to remove and the square will go blank. Note that correct values can't be removed.

If you think that you're hopelessly stuck, you could press the "Solve" button, then all the squares will be filled in with the correct numbers. The game doesn't have to be over, though. If you press the button again, the solution is hidden and the numbers revert back to what they were previously, so you can continue.

The "Clear" button clears the board. This is useful if you want to solve a Sudoku that you've seen in a magazine, for example. Simply set the given values and press the "Solve" button and you'll see the correct solution for the Sudoku.

If the "Allow Incorrect Moves" checkbox is ticked, when you enter a number that's not correct it will not be crossed out, which makes it a bit harder as you don't know if you're on the right track.

You might also run out of time and want to continue the Sudoku later on, then the save button is what you need. Just enter a file name and the Sudoku is stored on your device; to bring it back simply use the load button.

The Implementation
Have you ever wondered what could be the fastest method to solving a Sudoku? There is a name for it - it's called the Dancing Links algorithm devised by Don Knuth (his impact on the field of computer science is downright phenomenal). There is a whitepaper that describes this algorithm in detail (see www-cs-faculty.stanford.edu/~knuth/preprints.html). Knuth suggested an implementation of this algorithm using circular doubly linked lists and named this Dancing Links, or DLX.

The heart of the algorithm is a matrix that represents every possible move and the constraints those moves must satisfy in any valid solution. Each row in the DLX matrix represents a possible move (you place a particular digit in a particular cell). As there are nine possible digits and 9x9=81 possible cells, there are 9x81=729 DLX rows. In addition, each cell in a row and column must contain exactly one digit , each digit must occur in each row exactly once, each digit must occur in each column exactly once, and each digit must occur in each box exactly once; this gives us 324 columns.

Using this matrix and algorithm we can be sure to get a solution within a reasonable time. You'll find the complete implementation in the user object n_sudoku. The 9x9 grid is a simple DataWindow that holds the numbers and uses some expressions (for the strike out and the background coloring).

One of the cool new features in PocketBuilder 2.0.4 is the Multiple Orientation Painter (MOP) view manager. From the Window painter, you can select the View > Runtime MOP Views > MOPView Manager menu item to create multiple views for each PocketBuilder window (views in the MOPView Manager are automatically listed as menu items in the View > Runtime MOP Views menu. At design time, you can toggle between the different views by selecting these menu items). This means that you have only one window in your library, but you can design it for different views and the controls are properly positioned when the view is changed (i.e., on a PocketPC from horizontal to vertical or vice versa). As you can see in Figure 1 and Figure 2, I rearranged the buttons so that the application also looks nice in vertical mode. This took only a few minutes using the MOP view and there was a vertical version of PKSudoku available.

Summary
Sudoku is like a crossword puzzle using numbers instead of words. The puzzle is a box of 81 squares. Some squares are pre-filled with numbers. The rest are to be filled in by you, the puzzler. You fill in the blank squares, allowing the numbers 1-9 to appear only once in every row, column, and 3x3 box. Have fun playing Sudoku on your PocketPC and feel free to enhance the PocketBuilder code, which you can find on http://codexchange.sybase.com.

More Stories By Berndt Hamboeck

Berndt Hamboeck is a senior consultant for BHITCON (www.bhitcon.net). He's a CSI, SCAPC8, EASAC, SCJP2, and started his Sybase development using PB5. You can reach him under [email protected]

Comments (2) View Comments

Share your thoughts on this story.

Add your comment
You must be signed in to add a comment. Sign-in | Register

In accordance with our Comment Policy, we encourage comments that are on topic, relevant and to-the-point. We will remove comments that include profanity, personal attacks, racial slurs, threats of violence, or other inappropriate material that violates our Terms and Conditions, and will block users who make repeated violations. We ask all readers to expect diversity of opinion and to treat one another with dignity and respect.


Most Recent Comments
Bill G 03/02/06 09:53:59 AM EST

Nice article, but when I went to view the code at codexchange.sybase.com, I couldn't find it. Please let me know where it is located.

Thanks!

SYS-CON Italy News Desk 02/27/06 03:53:11 PM EST

It's amazing how popular Sudoku has become in the last few months. You'll find one in nearly every daily magazine here in Austria. When I started to jump on this train (yes, I solve at least one Sudoku a day), I thought it would be amazing if we could have a version written completely in our number-one development tool, PowerBuilder, or it's small brother PocketBuilder. Since I wanted to be able to carry it around with me, I decided to write it in PocketBuilder 2.04 (because of its wonderful new support for horizontal/vertical windows) so that it would also support one of my new gadgets - the MDA PRO. Let's first look a little bit at the history of Sudoki and how it's played and, last but not least, how the solution is implemented.