3DRLI YASS - Code - OmegaJunior.Net

Or: How to Solve Sudoku Puzzles

You may wish to use an HTML 5 / CSS 3-compatible browser to appreciate the full experience of this article and the YASS. Opera 9.6 / 10 and Google Chrome 1 come to mind. Recent nightly builds of Firefox 3 look promising and sport the fastest javascript engine for this application, but fail to support the innerText-property and some HTML5 elements.

Description

Game Objective

The objective of the Sudoku Puzzle is to complete a Game Board, on which the puzzle creator placed a couple of clues, presenting the challenge. To complete the Board and solve the Puzzle, the player must place 9 copies of each of the numbers from the range 1 through 9, amounting to 81 number placings (minus the clues). Placing the numbers on the Board should obey a couple of Numbering Rules. To understand these rules, the player does well to understand the design of the Game Board.

The Game Board

The Sudoku Game Board consists of a square grid divided into 9 rows by 9 columns, amounting to 81 squares. A player usually finds this grid printed on a visual medium like paper, or displayed as a table on a computer screen. Besides the rows and columns, thick lines on the grid divide the same 81 squares into 9 boxes containing 9 squares each: 3 squares high by 3 squares wide. Once the player completes the Puzzle, each square will hold one single number.

Numbering Rules

As stated in the Game Objective, the player has to fill out the entire Game Board with the numbers 1 to 9 (i.e.: 1, 2, 3, 4, 5, 6, 7, 8, and 9). The Board contains 81 squares, allowing for each of those numbers to exist exactly 9 times. The total amount of possible variations equals 9 to the 81st power. Luckily, the Numbering Rules limit this amount considerably (to a little under 5.5 billion).

A Game Board without any clues proves easy to solve. A puzzle creator will place number clues on the Board to highten the challenge. The player must consider these clues while solving the puzzle.

The One Rule

Quoting from Wikipedia:

Fill in all (blank) cells so that each row, column and box contains the values 1-9. Same as: fill in the grid so that each row, column and box contains the values 1-9 exactly once, without changing the clues.

This One Rule falls apart into the more elaborated rules below, describing all 3 degrees of clues.

Row Degree Rule

Each row of 9 squares crosses 9 columns, which also consists of 9 squares. Each row should receive each of the numbers from 1 to 9, exactly one number per square, without any duplicates in that row. (Trivia: the name Sudoku is a Japanese abbreviation of a phrase meaning: only one of each.)

Column Degree Rule

Each column of 9 squares crosses 9 rows. Each column should receive each of the numbers from 1 to 9, exactly one number per square, without any duplicates in that column.

Box Degree Rule

Each of the 9 boxes holds 9 squares, overlapping 3 rows and 3 columns. Each box should receive each of the numbers from 1 to 9, exactly one number per square, without any duplicates in that box, and without creating duplicates in the overlapped rows and columns.

Diagonal, Diamond, Midpoint, and other rules

Some versions of Sudoku Puzzles go beyond the Numbering Rules mentioned above. For instance, some also impose a diagonal rule, whereby the two diagonals of the grid also must receive each of the numbers. Sometimes, manufacturors invent Numbering Rule variations based on other shapes like crystals, squares, or meaningful polygons.

Although those rules present further limitations and usually make it easier to solve the puzzles, they play no part in the regular Sudoku Puzzles described in this article.

Competitions and Time Limits

Regular Sudoku Puzzles impose no other rules than the Numbering Rules explained above. This allows for game play by a single player, without constraints on time or number of retries. One may add competition rules and time limitations, to extend participation or create contests. Such rule extensions however must not change the intent of the Sudoku Numbering Rules.

Solving

Sample Puzzle

3 Degrees Reduction and Lock-In Strategy

The player may find the key to solving Sudoku Puzzles in the degrees of clues for each square. What number goes into a square? Each belongs simultaneously to a box (1st degree), and a column (2nd degree), and a row (3rd degree), and thus can hold no duplicate to any number already present in each of these degrees.

Several strategies for solving Sudoku Puzzles may exist. The one we show here, minimizes the amount of guesswork and extrapolation. Hereby we name the following strategy 3DRLI: the 3 Degrees Reduction and Lock-In Strategy.

For each empty square:

1. Look at the clues in the same degrees to assess potential solutions for that square.
2. If the availability of numbers got limited to 0, either an error occurred or we reached the solution. Stop solving.
3. Otherwise, if the amount of potential solutions got limited to 1, fill it in as the solution for that square. From then on, it will serve as a clue for solving other squares. Also: reduce the potentials for all degrees of the same square.
4. Otherwise, compare each of the remaining potentials for that square with all other solutions in all its degrees simultaneously, to see which potential it holds exlusively. If the square has only one such potential, fill it in as the solution for that square. If the square has several exclusive potentials, remove all its non-exclusive potentials.
5. The remaining potentials for the square serve both to avoid having to repeat all the steps in a future iteration, and as a Lock-In Clue for solving other squares.
6. If we reduced the number of potentials to 3 or less, check for Lock-Ins with other squares across its other degrees. A Lock-In occurs where a potential in a square either can or cannot count as its solution, due to the existence of potentials in any of the degrees overlapping its own. (In the sample puzzle above, a Lock-In exists in the 3rd row from the bottom, 3rd square from the right: it must be a 2, locked in by the existing 2s in the other rows overlapping the same box.)
7. Repeat until an iteration no longer reduces potentials for any of the squares.

Sample Solution

Yet Another Sudoku Solver

Many an automated Sudoku Solver exists, usually in the form of computer programs. Why do we want to program a YASS ourselves? Well... because we like the challenge of figuring out how some people's brains work. Obviously we will use the 3DRLI strategy described above. That means that we didn't set out to solve any and all Sudoku challenges out there... just that we created a program that mimics one single solving strategy, which can and indeed does fail with some specially crafted challenges.

You must allow Javascript / Ecmascript to run on this page, in order to use the YASS.

Disclaimer

Sudoku seems invented by late American architect Howard Garns in 1979, or so says Wikipedia. The copyright on the 3 Degrees Reduction and Lock-In Strategy belongs to us: we developed it independently while solving these puzzles. Other parties may have developed and published differing or similar strategies. We claim all rights to 3 Degrees Reduction and Lock-In Strategy as described in this article, and hereby grant anyone the right to employ it to solve Sudoku Puzzles manually (that means: without an automation of the strategy algorithm).

The YASS (and thus the 3DRLI Strategy) cannot solve some Sudoku challenges:

• Easter Monster by JPF
• tarek071223170000-052 by tarek
• golden nugget by tarek
• col-02-08-071 by coloin