Sudoku Solver & Generator is a simple web application written for both solving and generating Sudoku puzzles. The application can handle any sort of N*N sudoku grids with user defined regions and is basically able to solve any of these kinds of Sudoku puzzles and find if it has multiple answers. (However, some sudoku puzzles are just too hard to solve fast enough).

Using the solver may seem complicated as there are multiple fields and various options which can be set. However, most of the time you do not need to modify almost any of these, as the default settings used are good for solving most sudoku puzzles.

The first thing you need to enter is the sudoku puzzle itself in the text area named "The Sudoku Puzzle". Simply write the numbers in the puzzle in that box in same order as the appear in the puzzle you have (like write on the first line the numbers on the first line in the puzzle, then next line the numbers on the next line and so on...)

For cells that are not yet solved, simply use 0 for them. Assuming you are trying to solve a normal 9*9 Sudoku puzzle, this is all you need to do. Just hit the "Solve the Sudoku Puzzle" button and the solution will be provided to you (assuming there is one). If the solver claims that there is no solution, check the puzzle for any typing errors. The solution page displays to board you gave, so you can easily check it for any errors.

There are large number of Sudoku variants in many Magazines and websites. This Solver can solve any N*N sudoku puzzles, but the more irregular ones require you to enter the map and charset, so that the solver can understand the Sudoku puzzle.

The map is never needed for any symmetrical Sudoku puzzles. What I call a symmetric sudoku puzzle is one with size S, where S is N*N (e.g. Sudokus of size 1, 4, 9, 16, 25, etc. are symmetrical), and which has regions of size N*N. Every other kind of Sudoku does require a map, or it can't be solved.

The region map indicates how the regions are placed on the Sudoku puzzle. The region is entered similarly to the puzzle itself. However, for each cell you enter the region it belongs to, using numbers from 0 to 8 (if using 9*9 sudoku grid).

The charset tells the solver how to interpret the given puzzle and region map. Every character that is not present in the charset is completely ignored. The first character in the charset represents the unsolved square and the every character after that is the number starting from 1. For example a 4*4 sudoku puzzle could use a charset of 0ABCD. If no charset is given, the board will ignore all characters in the puzzle and region map that are not digits or letters and a default charset of 0-9 followed by A-Z is used.

Note that for user convenience, all the input is case insentive, so characters 'a' and 'A' are considered the same.

The Sudoku solver provides a few different advanced options to use for solving sudoku puzzles. These options are mostly for playing around with the solver, but also because different puzzles are solved more optimally in different ways. Here is explanation of each option:

**Solving type**- This option determines the logic used for solving the puzzle. Mixed logic uses both guessing and elimination logic (see below) for solving the puzzle. Guessing logic does not use elimination logic and Logic only option does not use guessing for solving the puzzle. If you wish to try whether puzzle is solvable by logic or not, you can simply choose the logic only option and attempt to solve it. (Note: If the solver can not solve the puzzle using only logic, it does not necessarily mean it wasn't possible, since the solver only implements few different sudoku solving logics). For normal human solvable puzzles, the Mixed type is best. However, if guessing is absolutely necessary for solving, ignoring the elimination logic might make the solver faster.**On guess**- This option determines what to do when the puzzle reaches a contradiction as result of failed guess. On "Store safe" option, the board stores a copy of the board in previous state and returns to that copy on failure. When "Backtrack on failure" is enabled, the board simply backtracks to the previous guess. Due to how PHP works, storing previous copies is almost always a lot faster (even if more memory consuming).**Guessing Order**- This option determines the order in which guesses are made within a cell. On "Ascending" order, the smallest number is always tried first. On "Descending" order the highest number is tried first. On "Random" the numbers are selected in random order.**Count weight**- This option determines how much weight the guessing algorithm places on number of candidates available in the square for determining the best possible cell to guess. On "None" it has no effect. On "Single" it has slight effect and on "Weighted" it means the number of candidates available comes before anything else.**Check Multiple**- This option simply tells the solver whether to check if the board has multiple solutions. Whenever a cell needs to be guessed, it means that it's possible to have more than 1 answer. Enabling this option will force it to go all possible guesses until it verifies whether multiple solutions exist

The sudoku solver implements a few different logics it uses to solve the sudoku puzzles. Basically, they can be separated into two different things which is finding the actual solutions and eliminating possible candidates in cells. when you use the solver to solve a puzzle, at the bottom of the page it will display a "path" to the correct solution. The column "M" in that table gives a letter, which indicates the used method. Below is the description for each method.

Solution methods:

**Singleton Finder (A)**: The board keeps track of available condidates for each cell in the puzzle. Singleton finder is simply a lookup to find any cell which has only one candidate. Obviously, as the cell has only one possible solution, that must be it.**Hidden Singles (B)**: Method B is close to Method A. This scans the board for cells which contain the only appearance for spesific candidate in an unit. Because each unit must contain each number, the correct solution for that cell is that candidate.**Guessing (C)**: When all else fails, the solver resorts to guessing solutions for the puzzle. The guessing algorithm is implementation of Ariadne's Thread. However, instead of simply choosing any cell to guess, the algorithm attempts to make the guess at best possible cell. To determine the best possible cell, the board keeps track of a value for each cell which determines how good guess it is. The number is a representation of number of cells solved relating to that cell. The cell with smallest value is guessed. The reasoning behind this algorithm is that the best possible guess to make is the one that leads fastest to a contradiction.

Elimination logics:

**Locked regions (D)**: Whenever all cells with a spesific candidate exist in the same row or column in a region, the candidate may not exist in any other region in that row or column. Method D eliminates these candidates from other regions.**Locked candidates (G)**: This is a "reverse" of the locked regions search. Whenever all cells with spesific candidate exist in a single region within a row or column, the candidate can not exist in any other row or column within that region. Method D eliminates all these candidates.**Hidden Pairs (E)**: Hidden pair exists when all possible cells for N candidates in an unit exist in N cells. Because these cells must have all these solutions, any other candidate can be eliminated from the cells.**Naked Pairs (F)**: When N identical cells in an unit contain N different candidates, these candidates can not exist in any other cell within the same unit, so they can be safely eliminated.

Note: Naked Pairs elimination is actually a partial chain elimination. The difference to the chain rule is that chain rule only requires N cells in a unit with only N different candidates. However, only the Naked Pairs search is used due to ease of implementation.

Most human made puzzles or ones that are generated for humans to solve can be solved using these logics without the guessing method. In fact, often only the hardest puzzles even require elimination logic at all. There are however a few more common logics such as the chain rule and N-wing logic which are not implemented in this solver (mainly due to my inexperience). So Some of the most hardest puzzles might not be possible to solve using only logic with this solver.

Even if the puzzle can not be solved using logic only, the guessing algorithm always enables the ability to find all possible solutions for any sudoku puzzle.

Here is a few examples, which you can play around with the solver to help you figure out how it works. For example example, the charset, puzzle and the region map is given which you can insert in the solver page.

070040010

301506408

000000000

060010040

105709803

000000000

030070020

204805709

000111222

000111222

333444555

333444555

333444555

666777888

666777888

666777888

This is a simple example of a sudoku board. This demonstrates also a board which can be solved using nothing but the Method A, as you can see from the solution page. Normally a puzzle like this would be ranked something like very easy.

Note that as this map uses default grid and default charset, you don't actually need to enter anything but the puzzle for the solver, and it can figure out the rest.

009060400

060000070

400010003

050402010

600030004

020000050

003090800

000206000

000111222

000111222

333444555

333444555

333444555

666777888

666777888

666777888

Like the previous example, this uses default map and charset, so those do not need to be given for the solver. This puzzle example demonstrates a puzzle which also requires a elimination logic to solve, so this kind of sudoku puzzle could be ranked somehat hard.

002060100

010908020

005000600

020000010

009000800

080304060

004010900

500000007

000111222

033331112

003444411

333345555

664444577

866655557

888666777

888886777

This is an example of sudoku with custom region map. As you can see especially on the solution page, the regions are not the normal 3x3 blocks, but little pieces. Because this uses a custom region map, the map must be entered, even though you don't need to enter the charset.

Note that puzzles with custom region maps are much more difficult to solve than standard maps. So, depending on the map, the solver may not always be able to solve custom region maps.

706000190

035070000

200400000

309000040

050001420

004035000

080090000

000302700

123456781

123456782

123456783

123456784

123456785

123456786

123456787

123456788

Regions do not actually need to be connected in the sudoku puzzle as this example demonstrates. In addition, this example also shows that while some puzzle may have only one solution, the solver may not be able to solve them without guesses (as not every possible logic is implemented).

####

C#D#

####

##AA

BBCC

BBCC

As this example demonstrates, not every sudoku has to be 9*9. Also, this puzzle uses a custom charset, containing letters instead of numbers (except for the unsolved square). If you want, you could even use non symmetrical sizes (like 5*5 or 7*7).

While the main emphasis of this web application is to solve sudoku puzzles, this can also generate them. The sudoku generator, however, is mostly built because I could, not because I particularly wanted to create a sudoku generator. Thus, the quality of the generated puzzles is rather low, as the generation algorithm is very simple.

When generation a sudoku puzzle, you can choose to create a map in one of the following ways:

**New map**: This method simply creates a completely new basic sudoku puzzle with the selected size. The given charset, map and puzzle will be completely ignored with this option**Base on map**: This method will first solve the given puzzle and then generate a new one based on that. This can be for example be used for generating sudokus with custom region maps, or generatea puzzle when you have an answer ready for. Note that you do not need to enter anything in the puzzle if you do not want to, as it defaults to completely empty board.**Start from map**: This option will continue generating the puzzle forward from the already given puzzle. This can be used to continue puzzle generation if it takes too long or see if any puzzle could be taken further.

When you have selected the type, you can also choose one of the difficulty levels for the puzzle. Note that these are only limits for the puzzle level. There is no guarantee that the actually generated puzzle will be this hard.

Once the puzzle is generated, you can see indication of the level of difficulty in the tittle given as stars. The number of stars indicate the complexity of solving methods required to solve the board, so even a 1 star puzzle might be hard for human to solve, if the right solutions are hard to spot, even if the methods required are very simple.

Sudoku Solver & Generator v5.2 is copyright © 2006 - 2007 to
Riimu