Login | Register   
Twitter
RSS Feed
Download our iPhone app
TODAY'S HEADLINES  |   ARTICLE ARCHIVE  |   FORUMS  |   TIP BANK
Browse DevX
Sign up for e-mail newsletters from DevX


advertisement
 

Build a Sudoku Puzzle Game Generator and Solver for PocketPC : Page 2

Not only can you generate your own Sudoku puzzles with this mobile application, but you can solve them, too—even puzzles you enter from newspapers or books.


advertisement
Using Sudoku Solver
There are two ways to use Sudoku Solver:

  1. You can request a new Sudoku puzzle by selecting the New Game menu item.
  2. You can recreate an existing Sudoku game from a newspaper or puzzle book by starting with an empty grid, and entering the supplied numbers manually. To enter a puzzle manually, you must first clear the screen by clicking the "Clear" menu item.
Once you have a puzzle on-screen, clicking the "Solve" button causes Sudoku Solver to try to calculate a solution.

Although you can use the hardware keyboard, an easier way to enter the number for each cell is to select a cell and then click the button in the top row that has a caption matching the number you wish to enter in the cell. Figure 3 shows a solved puzzle.

 
Figure 3. A Solved Puzzle: Here's a puzzle solved by Sudoku Solver showing a correct solution.
Solving Puzzles with Sudoku Solver
The solved puzzle grid in Figure 3 shows three types of cells:

  • The cells with a blue background are read-only cells (the background color may depend on your device)—the pre-supplied numbers from the original Sudoku puzzle.
  • The cells with green numbers (only one in this case) indicate numbers I entered that were correct.
  • The cells where the numbers are red are those I got wrong.
I have deliberately not put any effort into ensuring that the Sudoku grid generated is complex or supports varying difficulty levels—I'll leave that up to you.

Each cell in the grid is a text box. The program must handle two events for each text box, but fortunately all the TextBoxes act identically, so you can use the same code for all of them. First, only numbers in the range 1 to 9 are allowed in the TextBoxes, which you can enforce via the Keypress event. Assign a delegate to each TextBox to handle the event.

this.txt21.KeyPress += new KeyPressEventHandler(this.KeyPressHandler)

Here's the definition of KeyPressHandler:

void KeyPressHandler(object sender, System.Windows.Forms.KeyPressEventArgs e) { System.Windows.Forms.TextBox txt = (System.Windows.Forms.TextBox)sender; int keyData = (int)e.KeyChar; if (! ( (keyData >= ASCII_ONE && keyData <= ASCII_NINE) || keyData == ASCII_BACKSPACE || keyData ==ASCII_DEL)) { e.Handled = true; } else { if (keyData >= ASCII_ONE && keyData <= ASCII_NINE) { e.Handled = true; txt.Text = e.KeyChar.ToString(); } } }

One of the KeyPressEventHandler delegate arguments is a KeyPressEventArgs instance, which provides information about the key that triggered the event. Wherever the ASCII number for the key is not within the expected range (1-9), the code simply ignores the key.

The other TextBox event you must handle is the GotFocus event. So that people can use the buttons at the top of the screen in Figure 3 to assign numbers to the text boxes, you need to keep track of the last textbox selected. The ActiveBox variable holds a reference to the most recently selected TextBox. Assign a delegate to the GotFocus event:



this.txt33.GotFocus += new EventHandler(this.GotFocusHandler);

Here's the GotFocusHandler definition:

void GotFocusHandler(object sender, System.EventArgs e) { if (sender is TextBox) ActiveBox = (TextBox)sender; }

Solving Sudoku Grids with Code
To solve Sudoku grids, you need to process ach row, column and 3 x 3 region, knowing that each number can only occur once in each. This rule allows you to identify the possible numbers that can be in the cells you're trying to fill. Usually, the rule alone is not enough to complete the grid, so you have to start looking for cells in the same row, column or region that contain identical likely candidates. For example, if you know columns 2 and 3 in row 4 both have 1 and 2 as possible candidates, then you can safely eliminate any occurrence of numbers 1 and 2 in all other columns in row 4. By following this logic for each row, column, and region, you can reduce the possible number of candidates even further. At this point, a very large number of cells would have been correctly filled.

However, when there are cells left with more than one possible candidate, you must introduce a guessing algorithm. The guessing algorithm used here is very simple. It looks for cells containing two possible candidates, selects one of them as the solution and then tries to solve the grid. If, using that "guess," you can't find a solution, the algorithm tries the other candidate. There are very impressive mathematical approaches I could have tried, but using this approach, I was able to solve all the Sudoku labeled "Difficult" in "Sudoku, Book 1" published by the The Times, a London newspaper. (I did this to pass the time during a six-hour flight in November).

The Sudoku grid is represented by an array of ArrayList objects. Each ArrayList represents a single cell in the grid and contains all the possible candidates for that cell. As the grid gets solved, the number of items in each ArrayList decreases. You have a solution when all the cells contain only one candidate.



Comment and Contribute

 

 

 

 

 


(Maximum characters: 1200). You have 1200 characters left.

 

 

Sitemap