The purpose of this project is to implement a sudoku solver able to run in a web browser.
There will be to parts:
Provides the following functions:
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:
The library code can be found here.
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.
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:
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.
Here is the widget you are willing to play with!.