Table of contents

• Introduction
• Using the Solver
• Using region map and charset for different Sudoku variants
• Advanced solver options
• Solving logic
• Examples for solver
• Using the generator

Introduction

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

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.

Using region map and charset for different Sudoku variants

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.

Advanced solver options

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

Solving logic

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.

Examples for solver

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.

Using the generator

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.