Recursion: reversing sudoku solution in JS

Question

I cannot get this recursive algorithm to work. It should solve the sudoku grid (2-dimensional array of ints). I did the same thing in Java (but, of course, OOP) and it works fine. But in JS this is not so. The values ​​in the grid do not change and never reach the base case. The algorithm is solved by Sudok - the basic case when it searches through the grid, but does not find any "empty" cells (with a value of "0").

I put all the code in one file. Can you spot a mistake? I’ve tried it for a week now and am going to suspect this small project.

"use strict"; var grid = [ [0,0,8,4,0,3,5,0,6], [0,0,3,1,0,2,0,0,4], [0,4,5,7,0,0,0,9,0], [6,9,0,0,0,5,0,0,7], [0,8,0,0,0,0,0,5,0], [4,0,0,3,0,0,0,1,8], [0,7,0,0,0,6,2,4,0], [1,0,0,5,0,7,8,0,0], [8,0,6,9,0,1,3,0,0] ]; // recursive algo function solveSudoku(grid, row, col) { var cell = findUnassignedLocation(grid, row, col); row = cell[0]; col = cell[1]; // base case: if no empty cell if (row == -1) { console.log("solved"); return true; } for (var num = 1; num <= 9; num++) { if ( noConflicts(grid, row, col, num) ) { grid[row][col] = num; if ( solveSudoku(grid, row, col) ) { return true; } // mark cell as empty (with 0) grid[row][col] = 0; } } // trigger back tracking return false; } function findUnassignedLocation(grid, row, col) { var done = false; var res = [-1, -1]; while (!done) { if (row == 9) { done = true; } else { if (grid[row][col] == 0) { res[0] = row; res[1] = col; done = true; } else { if (col < 8) { col++; } else { row++; col = 0; } } } } return res; } function noConflicts(grid, row, col, num) { return isRowOk(grid, row, num) && isColOk(grid, col, num) && isBoxOk(grid, row, col, num); } function isRowOk(grid, row, num) { for (var col = 0; col < 9; col++) if (grid[row][col] == num) return false; return true; } function isColOk(grid, col, num) { for (var row = 0; row < 9; row++) if (grid[row][col] == num) return false; return true; } function isBoxOk(grid, row, col, num) { row = (row / 3) * 3; col = (col / 3) * 3; for (var r = 0; r < 3; r++) for (var c = 0; c < 3; c++) if (grid[row + r][col + c] == num) return false; return true; } function printGrid(grid) { var res = ""; for (var i = 0; i < 9; i++) { for (var j = 0; j < 9; j++) { res += grid[i][j]; } res += "\n"; } console.log(res); } 

Answer 1

It was hard to find ... but the problem is

 row = (row / 3) * 3; col = (col / 3) * 3; 

Javascript only uses floating point numbers, so it does not do what you think.

Decision

 row = Math.floor(row / 3) * 3; col = Math.floor(col / 3) * 3; 

Answer 2

In javascript, numbers cannot be forced to be integers, so something like (a / 3) * 3 no different from a . In isBoxOk you need to replace

 row = (row / 3) * 3; col = (col / 3) * 3; 

by

 row = Math.floor(row / 3) * 3; col = Math.floor(col / 3) * 3; 

In addition, I think you can simplify the findUnassignedLocation function:

 function findUnassignedLocation(grid, row, col) { for (; row < 9 ; col = 0, row++) for (; col < 9 ; col++) if (grid[row][col] == 0) return [row, col]; return [-1, -1]; } 

Answer 3

I solved this issue using the return algorithm:

 const _board = [ ['.', '9', '.', '.', '4', '2', '1', '3', '6'], ['.', '.', '.', '9', '6', '.', '4', '8', '5'], ['.', '.', '.', '5', '8', '1', '.', '.', '.'], ['.', '.', '4', '.', '.', '.', '.', '.', '.'], ['5', '1', '7', '2', '.', '.', '9', '.', '.'], ['6', '.', '2', '.', '.', '.', '3', '7', '.'], ['1', '.', '.', '8', '.', '4', '.', '2', '.'], ['7', '.', '6', '.', '.', '.', '8', '1', '.'], ['3', '.', '.', '.', '9', '.', '.', '.', '.'], ]; sodokoSolver(_board); console.log(_board); function isValid(board, row, col, k) { for (let i = 0; i < 9; i++) { const m = 3 * Math.floor(row / 3) + Math.floor(i / 3); const n = 3 * Math.floor(col / 3) + i % 3; if (board[row][i] == k || board[i][col] == k || board[m][n] == k) { return false; } } return true; } function sodokoSolver(data) { for (let i = 0; i < 9; i++) { for (let j = 0; j < 9; j++) { if (data[i][j] == '.') { for (let k = 1; k <= 9; k++) { if (isValid(data, i, j, k)) { data[i][j] = '${k}'; if (sodokoSolver(data)) { return true; } else { data[i][j] = '.'; } } } return false; } } } return true; }