We solve JavaScript sudoku

Sudoku is a popular puzzle game whose main task is to place numbers in the correct order.

The game field is a square of 9x9 cells. Cells are grouped into nine 3x3 segments. Each cell can contain a number from one to nine. The basic rule of sudoku is that a digit cannot be repeated in a row, column and segment.

Under the cut is a solution algorithm Sudoku, implemented in JavaScript. Only basic tactics for solving the puzzle are considered, but this is sufficient for a large number of easy and medium sudoku.

main idea

A cell on the field can have one of three states:

• in - value defined initially
• unknown - value not defined
• solved - value found

For each unsolved cell, an array of suggested values ​​is stored, which it can accept (candidates). To solve a sudoku, it is enough to iterate through the unsolved cells and reduce the number of candidates in each of them. If the number of candidates is reduced to one, then the value of the cell is found and it is assigned the status of solved .
')
The search for a solution ends if, after going through all the unresolved cells, none of them managed to find a solution or the number of candidates was not changed:

/** *   * *      ,       *   ,   . */ function solve() { var changed = 0; do { //        changed = updateSuggests(); steps++; if ( 81 < steps ) { //    break; } } while (changed); }; // end of method solve() /** *    * *    --   ,   . */ function updateSuggests() { var changed = 0; var buf = arrayDiff(solved[1][3][2], rowContent(1)); buf = arrayDiff(buf, colContent(3)); buf = arrayDiff(buf, sectContent(1, 3)); for ( var i=0; i<9; i++) { for ( var j=0; j<9; j++) { if ( 'unknown' != solved[i][j][1] ) { //    ,   continue; } // "" changed += solveSingle(i, j); // " " changed += solveHiddenSingle(i, j); } } return changed; }; // end of method updateSuggests() 

Algorithm implementation

There are many ways to solve sudoku, but for the sake of demonstration, consider the two most simple methods: “ Single ” and “ Hidden loner ”. These are basic methods for solving Sudoku and they are great for learning basic principles.

The “ Singleton ” method is based directly on the rules of sudoku: any number can occur only once in a row in a column and a segment. From the point of view of the algorithm, this means that all the found numbers from its row, column, and segment will be deleted from the list of candidates.

 /** *  "" */ function solveSingle(i, j) { solved[i][j][2] = arrayDiff(solved[i][j][2], rowContent(i)); solved[i][j][2] = arrayDiff(solved[i][j][2], colContent(j)); solved[i][j][2] = arrayDiff(solved[i][j][2], sectContent(i, j)); if ( 1 == solved[i][j][2].length ) { //      markSolved(i, j, solved[i][j][2][0]); return 1; } return 0; }; // end of method solveSingle() 

The “ Hidden loner ” method uses the rule: if among the candidates in a row / column / segment a single digit is found only in one cell, then the value of this cell will be equal to that digit.

 /** *  " " */ function solveHiddenSingle(i, j) { var less_suggest = lessRowSuggest(i, j); var changed = 0; if ( 1 == less_suggest.length ) { markSolved(i, j, less_suggest[0]); changed++; } var less_suggest = lessColSuggest(i, j); if ( 1 == less_suggest.length ) { markSolved(i, j, less_suggest[0]); changed++; } var less_suggest = lessSectSuggest(i, j); if ( 1 == less_suggest.length ) { markSolved(i, j, less_suggest[0]); changed++; } return changed; }; // end of method solveHiddenSingle() /** *      */ function lessRowSuggest(i, j) { var less_suggest = solved[i][j][2]; for ( var k=0; k<9; k++ ) { if ( k == j || 'unknown' != solved[i][k][1] ) { continue; } less_suggest = arrayDiff(less_suggest, solved[i][k][2]); } return less_suggest; }; // end of method lessRowSuggest() /** *      */ function lessColSuggest(i, j) { var less_suggest = solved[i][j][2]; for ( var k=0; k<9; k++ ) { if ( k == i || 'unknown' != solved[k][j][1] ) { continue; } less_suggest = arrayDiff(less_suggest, solved[k][j][2]); } return less_suggest; }; // end of method lessColSuggest() /** *      */ function lessSectSuggest(i, j) { var less_suggest = solved[i][j][2]; var offset = sectOffset(i, j); for ( var k=0; k<3; k++ ) { for ( var l=0; l<3; l++ ) { if ( ((offset.i+k) == i && (offset.j+l) == j)|| 'unknown' != solved[offset.i+k][offset.j+l][1] ) { continue; } less_suggest = arrayDiff(less_suggest, solved[offset.i+k][offset.j+l][2]); } } return less_suggest; }; // end of method lessSectSuggest() 

Using

All code is designed as a Sudoku class. To solve the puzzle, you need to create an instance of the class, pass the problem condition to it, and call the solve () method. The result of the solution is output by the html () method, which returns the formatted table and the number of passes it took to find a solution. If the solution cannot be found, a table of the found results will be displayed and a list of candidates will be displayed by hovering the cursor over the empty cells.

The initial values ​​are given by the 9x9 integer matrix. “0” is written in the cells if the value is not defined and the number is different.

 var in_val = [ [0, 0, 3, 0, 0, 8, 2, 0, 4], [0, 2, 0, 0, 6, 4, 0, 1, 0], [9, 0, 0, 0, 0, 0, 0, 0, 8], [0, 8, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 6, 9, 8, 0], [0, 0, 0, 0, 0, 0, 5, 0, 0], [0, 0, 4, 9, 0, 7, 0, 3, 0], [8, 0, 0, 0, 0, 1, 0, 0, 0], [0, 7, 0, 0, 5, 0, 4, 0, 0] ]; var sudoku = new Sudoku(in_val); document.write(sudoku.html()); 

The result of the algorithm is as follows:



The source code of the Sudoku class, as well as several sample tasks are available at this link .

Links

Sudoku [wikipedia]
How to solve sudoku: ways, methods and strategy

UPD User rozboris kindly created a demo

UPD 2 Reverse lookup implemented . Now solves all sudoku. And a new demo from rozboris .

UPD3 Since the links in the article died, I posted the source code on Google Code .