Sudoku Challenge

Throughout the week we'll be doing the Sudoku challenge along with the normal labs and modules. This challenge is optional, and it is meant to be a fun way to work on your Java skills above and beyond the normal class. The challenge is to make a Java program that can solve Sudoku puzzles. If you opt to enter the Sudoku Challenge you'll be required to provide a program that implements the sudokuchallenge.SudokuSolver interface and can solve as many Sudoku puzzles as possible as fast as possible.

Here are the rules.

  1. The code must be authored completely in Java.
  2. The code needs to solve Sudoku puzzles according to the rules out-lined below and summarized here.
  3. You must submit your Java source-code with your entry. If time permits, we will try to discuss some of top code for everyone's benefit.
  4. You may submit as many versions of your code as you please; however, the final version must be submitted before we break for lunch on Friday.

Remember this challenge is meant to be a fun way to practice your Java coding skills. It is perfectly fine to submit code that only kind of works, and you are encouraged to ask others for help or to work in groups. If for any reason part of the sudoku challenge or one of the rules is in question, Jayson will act as The Decider.

How to enter your code

If you want to enter you code you need to provide a JAR with your code, and that JAR must include one class that implements the sudokuchallenge.SudokuSolver interface provided by Jayson in SudokuChallenge.jar.

The Fabulous Prize

The person with the best entry in the Sudoku Challenge will win more than knowing that they have the best Sudoku solving code out there. A fabulous prize shall be awarded to the winner on the last day of class.

More about Sudoku

Here is some more information about Sudoku invluding tips and tricks about solving sudoku puzzles taken from http://www.sudocue.net/guide.php.

For more help solving sudoku puzzles you can use any of the tools linked below. The Wikipedia page is a great source for more sudoku information.

Introduction

For those who are not familiar with the Sudoku phenomenon, a brief introduction.

A game called "Number Place" was designed by Howard Garns, and first published by Dell Magazines in 1979. The puzzle was introduced in Japan by Nikoli in 1984, who gave it the name "Sudoku", which is an abbreviation for the original Japanese name meaning "The Numbers must be Unique". The whole world adopted this new name, but in Japan, Nikoli owns the trademark, so other publishers in Japan call it Nanpure, the Japanese translation of Number Place. By the end of 2004, Sudoku appeared in The Times in Britain, brought to Europe by Wayne Gould, the founder of Pappocom. Many newspapers worldwide followed. Sudoku magazines can be found everywhere. Sudokus are published on the Internet on a daily basis. And many people have become addicted to it.

The Grid

A Sudoku puzzle consists of a 9x9 grid, with a total of 81 cells. Different sized grids exist in variations on Sudoku, but these are not discussed in this solving guide. Each position in the grid is called a "cell". A cell can be empty, or filled with a "digit". This digit can be any digit between 1 and 9. Zeros are not valid digits. When used, zeros represent empty cells. Despite the fact that numbers are used, there is no math involved in solving Sudokus. This is best illustrated by alternative versions, which use letters, colors, symbols or pictures. Digits are the easiest to communicate. A Sudoku made in Japan can be solved in Germany because digits are used. Sometimes people use the term "number", "value" or "symbol" for digit. Rows, Columns and Boxes

The grid can be divided into 9 "rows", each containing 9 cells. These rows are numbered 1 through 9 from top to bottom.

The grid can also be divided into 9 "columns", each containing 9 cells. These columns are numbered 1 through 9 from left to right.

A third method to divide the grid is in 3x3 boxes, each containing 9 cells. Other names for these boxes are "Blocks", "Regions" and "Minigrids". These boxes are numbered according to the following diagram:

Da Rule

The strength of Sudoku is in its simplicity. The grid of 81 cells must be filled with digits 1 through 9 in such a way that only one of each digit is present in each row, column and 3x3 box.

The Givens

A number of digits are already in place. These are the "givens". These givens are placed in such a way that there is only a single solution to the grid, otherwise, you are not playing Sudoku. You are not allowed to remove or change them, because they are part of the puzzle. An alternative name for givens is "clues".

Currently, there is a search going on in the Sudoku community for the minimum number of givens that a Sudoku puzzle can have. At the moment this manual was written, 17 is the minimum so far. About 32000 different puzzles with 17 givens have been collected by G.F.Royle. The number of puzzles with 18 clues runs into millions.

The number of givens does not reflect the difficulty of the puzzle. There are puzzles with 17 givens that can be solved easily, while there are puzzles with 28 clues amongst the toughest known. The placement of the givens and the information that you can extract from them is more important than the sheer quantity of givens. The Japanese publisher Nikoli limits its Sudokus to a maximum of 32 givens. One can conclude, however, that a Sudoku with more than 40 givens is probably not a very difficult one. Random puzzles generated by Sudo Cue usually have on average between 20 and 26 givens.

Experts call a Sudoku "minimal" when it is not possible to remove any Given without the resulting puzzle having multiple solutions.