1+ function SudokuSolver ( grid ) {
2+ // Print unsolved grid
3+ printGrid ( grid )
4+ // Find first empty cell and start algo there
5+ for ( let i = 0 ; i < 9 ; i ++ ) {
6+ for ( let j = 0 ; j < 9 ; j ++ ) {
7+ if ( grid [ i ] [ j ] === '.' ) {
8+ solveBoard ( grid , i , j )
9+ }
10+ }
11+ }
12+ // print solved grid
13+ printGrid ( grid )
14+ }
15+
16+ function solveBoard ( grid , row , col ) {
17+ // if all board completed, sudoku solved
18+ if ( row === 9 ) {
19+ return true
20+ }
21+ // if current position is not empty, search for next one
22+ if ( grid [ row ] [ col ] !== '.' ) {
23+ if ( col === 8 ) {
24+ return solveBoard ( grid , row + 1 , 0 )
25+ }
26+ else {
27+ return solveBoard ( grid , row , col + 1 )
28+ }
29+ }
30+ else {
31+ // Check every possibility for this position
32+ for ( let n = 1 ; n <= 9 ; n ++ ) {
33+ grid [ row ] [ col ] = '' + n
34+ // Check if this number is valid here
35+ if ( isValid ( grid , row , col ) ) {
36+ // if it is, then solve next empty cell
37+ if ( col === 8 ) {
38+ if ( solveBoard ( grid , row + 1 , 0 ) ) {
39+ return true
40+ }
41+ }
42+ else {
43+ if ( solveBoard ( grid , row , col + 1 ) ) {
44+ return true
45+ }
46+ }
47+ }
48+ }
49+ // if no number suitable here, then we need to backtrack
50+ grid [ row ] [ col ] = '.'
51+ return false
52+ }
53+
54+ }
55+
56+ // Check if number at current position is valid
57+ function isValid ( grid , row , col ) {
58+ // Check row
59+ for ( let i = 0 ; i < 9 ; i ++ ) {
60+ if ( row === 0 && col === 5 ) {
61+ }
62+ if ( i !== row && grid [ i ] [ col ] === grid [ row ] [ col ] ) {
63+ return false
64+ }
65+ }
66+ // Check columns
67+ for ( let i = 0 ; i < 9 ; i ++ ) {
68+ if ( i !== col && grid [ row ] [ i ] === grid [ row ] [ col ] ) {
69+ return false
70+ }
71+ }
72+ // Check the box
73+ let bigrow = Math . floor ( row / 3 ) , bigcol = Math . floor ( col / 3 )
74+ for ( let i = 0 ; i < 3 ; i ++ ) {
75+ for ( let j = 0 ; j < 3 ; j ++ ) {
76+ if ( ( i + bigrow * 3 !== row ) && ( j + bigcol * 3 !== col ) && grid [ i + bigrow * 3 ] [ j + bigcol * 3 ] === grid [ row ] [ col ] ) {
77+ return false
78+ }
79+ }
80+ }
81+ return true
82+ }
83+
84+
85+ // Utility function o print the formatted grid
86+ function printGrid ( grid ) {
87+ let output = ""
88+ for ( let i = 0 ; i < grid . length ; i ++ ) {
89+ for ( let j = 0 ; j < grid [ 0 ] . length ; j ++ ) {
90+ output += grid [ i ] [ j ] + " "
91+ }
92+ output += "\n"
93+ }
94+ console . log ( output )
95+ }
96+
97+
98+ // Solve this case
99+ let grid = [
100+ [ '5' , '3' , '.' , '.' , '7' , '.' , '.' , '.' , '.' ] ,
101+ [ '6' , '.' , '.' , '1' , '9' , '5' , '.' , '.' , '.' ] ,
102+ [ '.' , '9' , '8' , '.' , '.' , '.' , '.' , '6' , '.' ] ,
103+ [ '8' , '.' , '.' , '.' , '6' , '.' , '.' , '.' , '3' ] ,
104+ [ '4' , '.' , '.' , '8' , '.' , '3' , '.' , '.' , '1' ] ,
105+ [ '7' , '.' , '.' , '.' , '2' , '.' , '.' , '.' , '6' ] ,
106+ [ '.' , '6' , '.' , '.' , '.' , '.' , '2' , '8' , '.' ] ,
107+ [ '.' , '.' , '.' , '4' , '1' , '9' , '.' , '.' , '5' ] ,
108+ [ '.' , '.' , '.' , '.' , '8' , '.' , '.' , '7' , '9' ]
109+ ] ;
110+ SudokuSolver ( grid )
0 commit comments