suduko-solver.js

suduko-solver.js

var solveSudoku = function(board, row=0, col=0) {
  function isSafe(row, col, num) {
    return isRowSafe(row, num) && isColSafe(col, num) && isGridSafe(row, col, num);
  }

  function isRowSafe(row, num) {
    for (let col=0; col<board.length;col++) {
      if (board[row][col] === num) return false;
    }
    return true;
  }

  function isColSafe(col, num) {
    for (let row=0; row<board.length;row++) {
      if (board[row][col] === num) return false;
    }
    return true;
  }

  function isGridSafe(row, col, num) {
    let startCoors = [];
    [row, col].forEach(num => {
      if (num >= 0 && num <= 2) {
        startCoors.push(0);
      } else if (num >= 3 && num <= 5) {
        startCoors.push(3);
      } else {
        startCoors.push(6);
      }
    });

    const [rowStart, colStart] = startCoors;
    for (let row=rowStart; row < rowStart+3; row++) {
      for (let col=colStart; col < colStart+3; col++) {
        if (board[row][col] === num) return false;
      }
    }
    return true;
  }

  if (col >= board.length) {
    return true;
  }

  if (row >= board.length) {
    row = 0;
    col += 1;
  }

  if (board[row][col] === '.') {
    for (let num=1; num<=board.length; num++) {
      if (isSafe(row, col, `${num}`)) {
        board[row][col] = `${num}`;
        if (solveSudoku(board, row+1, col)) return board;
        board[row][col] = '.';
      }
    }
    return false;
  }
  return solveSudoku(board, row+1, col);
};


// considered world's hardest suduko
// https://www.telegraph.co.uk/news/science/science-news/9359579/Worlds-hardest-sudoku-can-you-crack-it.html
const board = [
  ['8','.','.','.','.','.','.','.','.'],
  ['.','.','3','6','.','.','.','.','.'],
  ['.','7','.','.','9','.','2','.','.'],
  ['.','5','.','.','.','7','.','.','.'],
  ['.','.','.','.','4','5','7','.','.'],
  ['.','.','.','1','.','.','.','3','.'],
  ['.','.','1','.','.','.','.','6','8'],
  ['.','.','8','5','.','.','.','1','.'],
  ['.','9','.','.','.','.','4','.','.']
];

console.log(solveSudoku(board));