Shepherd Technology Sudoku


		SUDOKU v1.0 by Shepherd Technology Table of Contents 1. Introduction 2. Loading a Game 3. Using the Gameboard 4. Adding New Games 5. Sudoku Strategy 6. History of Sudoku 7. Known Issues & Support 8. License

1. Introduction
Why create yet another Sudoku game with so many other offerings already available? Primarily this program evolved out of frustration with other Sudoku games when compared to using paper and pencil. When using pencil you can use guess marks (or marking up with subscript notation as described in the strategy section) for possible numbers in a cell, but no free program I found provided this functionality...so I wrote one. From that point on it became a programming challenge that has been both entertaining and instructive. It's a work in progress so please feel free to visit the web site for updates or if you'd like to make suggestions: http://www.shepherdtrack.com/sudoku

Clearly this first version lacks a few key bits of functionality. Here is my to-do list for future releases:

"How am I Doing" feature to check invalid/duplicate entries
Remember/Save the current game in progress
Create/Save game feature to avoid direct editing of the xml file to add new games
Bookmarks that can be reverted back to - this is especially important for the harder games

2. Loading a Game
When you start the program a blank game board is loaded. There are a number of games distributed with the program that you can play. You load a new game by selecting File and then Load from the menu. A list of available games is displayed along with their category (Easy, Medium, Hard, etc).

Select a game by double-clicking it or clicking once and pressing the Select button. The game is loaded onto the gameboard and the pre-defined entries are bolded and read-only.

3. Using the Gameboard
The gameboard is made up of 81 cells that are either play cells or pre-set cells.
Pre-set cells have numbers already in them and cannot be changed.
Play cells are where you set numbers or guesses while playing the game.

Play cells are used to:

set guesses by clicking on the guess numbers in the cell which turns them from faint blue to black
set numbers by right-clicking and selecting the number to complete the cell

Multiple (in fact, all) guess numbers can be selected at one time in a cell. If a number is set, it will not erase the guesses previously set. A number can be removed by selecting "empty" from the number list.

4. Adding New Games
The games are stored as a string of numbers, one digit for each cell and 0 for blanks. The numbers are in the XML file gamedata.xml stored in the default program directory. It is possible to add new games by simply editing the xml file. There are three fields to each xml record although the program is not picky about the content of the file at this time - basically you can leave the ID and CAT (short for category) fields empty and the program won't even notice. The only thing that counts is the contents of the CD field which is the game board itself. If you accidentally leave out cell values the program will still function but you'll notice that the last few cells won't be overwritten with new values so you may end up with an unsolveable game. If you intend to edit gamedata.xml please be sure to make a copy first in case something goes wrong. In addition, you can always download the latest version of gamedata.xml from out website.

Additional games in an updated gamedata.xml will eventually be available for download from our website.

5. Sudoku Strategy courtesy of Wikipedia
The strategy for solving a puzzle may be regarded as comprising a combination of three processes: scanning, marking up, and analyzing.

Scanning
Scanning is performed at the outset and throughout the solution. Scans need to be performed only once in between analyses. Scanning consists of two techniques:

Cross-hatching: the scanning of rows to identify which line in a region may contain a certain numeral by a process of elimination. The process is repeated with the columns. For fastest results, the numerals are scanned in order of their frequency, from high to low. It is important to perform this process systematically, checking all of the digits 1–9.
Counting 1–9 in regions, rows, and columns to identify missing numerals: Counting based upon the last numeral discovered may speed up the search. It also can be the case, particularly in tougher puzzles, that the best way to ascertain the value of a cell is to count in reverse—that is, by scanning the cell's region, row, and column for values it cannot be, in order to see what remains.

Advanced solvers look for "contingencies" while scanning, narrowing a numeral's location within a row, column, or region to two or three cells. When those cells lie within the same row and region, they can be used for elimination during cross-hatching and counting. Puzzles solved by scanning alone without requiring the detection of contingencies are classified as "easy"; more difficult puzzles cannot be solved by basic scanning alone.

Marking Up
Scanning stops when no further numerals can be discovered, making it necessary to engage in logical analysis. One method to guide the analysis is to mark candidate numerals in the blank cells. There are two popular notations: subscripts and dots.

In the subscript notation the candidate numerals are written in subscript in the cells. Because puzzles printed in a newspaper are too small to accommodate more than a few subscript digits of normal handwriting, solvers may create a larger copy of the puzzle.
The second notation uses a pattern of dots in each square, where the dot position indicates a number from 1 to 9. The dot notation can be used on the original puzzle. Dexterity is required in placing the dots, since misplaced dots or inadvertent marks inevitably lead to confusion and may not be easily erased.

An alternative technique is to "mark up" the numerals that a cell cannot be. A cell will start empty and as more constraints become known, it will slowly fill until only one mark is missing. Assuming no mistakes are made and the marks can be overwritten with the value of a cell, there is no longer a need for any erasures.

Analysis
The two main approaches to analysis are "candidate elimination" and "what-if". In "candidate elimination", progress is made by successively eliminating candidate numerals from cells to leave one choice. After each answer has been achieved, another scan may be performed—usually checking to see the effect of the contingencies. In general, if entering a particular numeral prevents completion of the other necessary placements, then the numeral in question can be eliminated as a candidate. One method works by identifying "matched cell groups". For instance, if precisely two cells within a scope (a particular row, column, or region) contain the same two candidate numerals (p,q), or if precisely three cells within a scope contain the same three candidate numerals (p,q,r), these cells are said to be matched. The placement of those candidate numerals anywhere else within that same scope would make a solution impossible; therefore, those candidate numerals can be deleted from all other cells in the scope.

In the "what-if" approach (also called "guess-and-check", "bifurcation", "backtracking" and "Ariadne's thread"), a cell with two candidate numerals is selected, and a guess is made. The steps are repeated unless a duplication is found or a cell is left without a possible candidate, in which case the alternative candidate must be the solution. For each cell's candidate, the question is posed: 'will entering a particular numeral prevent completion of the other placements of that numeral?' If the answer is 'yes', then that candidate can be eliminated. The what-if approach requires a pencil and eraser or a good layout memory.

There are three kind of conflicts, which can appear during puzzle solving:

basic conflicts - there are only N-1 different candidates in N cell in the area
fish conflicts - when eliminating number from N rows/columns, it will disappear also from N+1 columns/rows.
unique conflicts - this pattern means multiple solutions, all numbers in the pattern exist exactly two times in every area, row and column. If there are only one candidate in the cell, any virtual candidate can be added.

Encountering any of those would indicate that the puzzle is not uniquely solvable. So, if you encounter them as a consequence of "what-if", you use your eraser and go back to try untried alternatives.

6. History of Sudoku courtesy of Wikipedia
Number puzzles first appeared in newspapers in the late 19th century, when French puzzle setters began experimenting with removing numbers from magic squares. Le Siècle, a Paris-based daily, published a partially completed 9×9 magic square with 3×3 sub-squares in 1892. It was not a Sudoku because it contained double-digit numbers and required arithmetic rather than logic to solve, but it shared key characteristics: each row, column and sub-square added up to the same number.

Within three years Le Siècle's rival, La France, refined the puzzle so that it was almost a modern Sudoku. It simplified the 9×9 magic square puzzle so that each row and column contained only the numbers 1–9, but did not mark the sub-squares. Although they are unmarked, each 3×3 sub-square does indeed comprise the numbers 1–9. However, the puzzle cannot be considered the first Sudoku because, under modern rules, it has two solutions. The puzzle setter ensured a unique solution by requiring 1–9 to appear in both diagonals.

These weekly puzzles were a feature of newspaper titles including L'Echo de Paris for about a decade but disappeared about the time of the First World War.

According to Will Shortz, the modern Sudoku was most likely designed anonymously by Howard Garns, a 74-year-old retired architect and freelance puzzle constructor, and first published in 1979 by Dell Magazines as Number Place (the earliest known examples of modern Sudoku), because Garns' name was always present on the list of contributors in issues of Dell Pencil Puzzles and Word Games that included Number Place, and was always absent from issues that did not. Sadly, he died in 1989 before getting a chance to see his creation as a worldwide phenomenon.

The puzzle was introduced in Japan by Nikoli in the paper Monthly Nikolist in April 1984 as Suuji wa dokushin ni kagiru, which can be translated as "the numbers must be single" or "the numbers must occur only once." At a later date, the name was abbreviated to Sudoku by Maki Kaji, taking only the first kanji of compound words to form a shorter version. In 1986, Nikoli introduced two innovations: the number of givens was restricted to no more than 32, and puzzles became "symmetrical" (meaning the givens were distributed in rotationally symmetric cells). It is now published in mainstream Japanese periodicals, such as the Asahi Shimbun.

7. Known Issues & Support
Sudoku has been tested on Windows 2000 and Windows XP with screen resolutions of 1024x768 or greater. The only issues that have cropped up so far are related to windows color schemes making the guess numbers difficult to read because of poorly contrasting colors.

There is no official support for this program but a forum will be available from the web site at http://www.shepherdtrack.com/sudoku and questions will be addressed on a best-effort basis. Revenue generating activities will take precedent over support for this program until such time as we're independently wealthy and can commit all our time to our hobbies.

8. License
This program is provided for free, as in free beer. It does not provide you with any additional rights including access to the source code, our fridge, or our beer recipes. You may use this program free of charge, redistribute it or ignore it entirely. If you make a point of redistributing this program it'd be nice if you'd make a point of giving credit where it's due by not misrepresenting it as your own work, hacking the binary code to change text strings, etc. What goes around comes around so watch yourself.