Samuel M.H. - A sudoku solver

The idea

The purpose of this project is to implement a sudoku solver able to run in a web browser.

There will be to parts:

The sudoku solver engine.
A pretty user interface which takes the problem and shows the solution.

The two parts will comunicate each other in order to share a sudoku representation.

The view

Provides the following functions:

view_build(): builds the HTML sudoku object.
view_get()->data: gets the current HTML sudoku data in a format suitable for the solver.
view_set(data): sets the HTML sudoku object with the provided data.

The solver

The solver is the function that given the problem, tries to find a solution (function sudoku_solve(data)->data).

The data variable is supposed to hold a sudoku representation, which is an array of 81 integer positions. Each position ranges from 0 (unknown value) to [1-9] (a solution).

The solving algorithm performs a Depth First Search, checking for every 0 value assignation that no restriction is violated. The three restrictons to check for every value assignment are that there are no duplicated values (but zeroes) in the element:

Colum.
Row.
Minitable (each 3x3 none overlapping tables the sudoku can be split).

In order to map the later number sets into 9-length arrays, the offset_XXX(elem_index, offset)->index are coded.

The code

The library code can be found here.

It is implemented as the JavaScript-pattern module revealing. The variable smh_sudoku can be instantiated with the id of the div element which will contain the sudoku HTLM element and the following methods are exposed:

solve(): tries to solve the instantiaded sudoku.
reset(): cleans the instantiated sudoku view.

A good example of the usage can be found in the source code of this page (press CTRL+u to see it).

Weak points

The program is meant to be able to solve "solvable" sudokus, that is, if you provide a sudoku which has no solution, it is likely to hang your web browser. Nevertheless, the function check_solvable(data) performs a naïve comprobation of the user input (no basic restrictions are violated). But, disappointingly it will not recognice a malicious user input (i.e. an unsolvable sudoku with transitive violations).

to display an example of a malicious input.

Example of a malicious input

This one of the worst scenarios the algorithm can face. An unsolvable problem since one of the three variables can not be assigned without breaking a restriction.

This is the problem formulation, with rules and variable domains:

X={1} ≠ Y={1,2} ≠ Z={2}

No possible assignation matches the rules.

The initial check_solvable(data) function cannot detect this kind of problems because they are transitive dependencies, so the only way to demonstrate the incorrectness of the problem is actually trying all the possible solutions and discard all of them. This is computationally expensive for a DFS algorithm. I encourage you to try this problem taking in mind it's likely your web browser will freeze.

The thing

Here is the widget you are willing to play with!.