Sudoku solver in JS

Question

I'm trying to write an algorithm that can solve sudoku. For now, my code works till supplyGrid is out of numbers. When it happens it should go back and try another number, right? To be honest I have no clue how to achive that.

var grid = [
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0]
],
    supplyGrid = [1, 2, 3, 4, 5, 6, 7, 8, 9],
    row = 0,
    col = 0,
    value = 0,
    index = 0;


var solveSudoku = function (grid, row, col) {
    if (col > 8) {
        row++;
        col = 0;
        if (row > 8 && col > 8) {
            console.log(grid);
            return;
        }
    }
    if (grid[row][col] === 0) { //
        index = Math.floor(Math.random() * supplyGrid.length);
        value = supplyGrid[index];
        if (isValid(row, col, value)) {
            grid[row][col] = value;
            col++;
            supplyGrid = [1, 2, 3, 4, 5, 6, 7, 8, 9];
            solveSudoku(grid, row, col);
        } else {
            supplyGrid.splice(index, 1);
            console.log(supplyGrid);
            if (supplyGrid.length < 1) { 
                //backtrack();
                console.log('Out of numbers');
                return;
            }
            solveSudoku(grid, row, col);
        }
    } else { //row = 3, col = 5
        solveSudoku(grid, row, ++col);
    }
    return this;
}

function isValid(row, col, value) {
    if ((validateColumn(row, col, value)) || (validateRow(row, col, value)) || (validateBox(row, col, value))) {
        return false;
    } else {
        return true;
    }
}

function validateBox(row, col, value) {
    row = Math.floor(row / 3) * 3;
    col = Math.floor(col / 3) * 3;
    var isFound = false;
    for (var i = 0; i < 3; i++) {
        for (var j = 0; j < 3; j++) {
            if (grid[row + i][col + j] == value) isFound = true;
        }
    }
    return isFound;
}

function validateRow(row, col, value) { 
    var isFound = false;
    for (var i = 0; i < 9; i++) {
        if (grid[row][i] === value) isFound = true;
    }
    return isFound;
}

function validateColumn(row, col, value) { 
    var isFound = false;
    for (var i = 0; i < 9; i++) {
        if (grid[i][col] === value) isFound = true;
    }
    return isFound;
}

Melodious

This sounds like "I am trying to write a book with a fascinating story but I have no idea for a good story...". Please have a look at stackoverflow.com/help/mcve for information on how to create a minimal, complete, verifiable example. – Opulence

I think you want to do some backtracking. – Concent

Like I said. Algorithm stops when supplyGrid is out of numbers. How can I go back, retry another number (the last one shouldnt be picked (?))? – Melodious

If you already backtrack and finish without a solution, you have a bug in your code. – Concent

Answer 1

I solved this question with backtracking 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;
}

Permatron

Answer 2

Here is an open source repository which has provided a javascript solution:

https://github.com/pocketjoso/sudokuJS

Here is the code which details his solution:

https://github.com/pocketjoso/sudokuJS/blob/master/sudokuJS.js

Fife

Answer 3

I came up with this solution check this out:

function sudoku(grid: number[][]): boolean {
  const rows: Set<number>[] = [];
  const cols: Set<number>[] = [];
  const miniGrids: Set<number>[] = [];

  for (let i = 0; i < 9; ++i) {
    rows.push(new Set());
    cols.push(new Set());
    miniGrids.push(new Set());
  }

  for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
      const gridId: number = Math.trunc(i / 3) * 3 + Math.trunc(j / 3);
      const n: number = grid[i][j];
      if (rows[i].has(n) || cols[j].has(n) || miniGrids[gridId].has(n)) return false;

      rows[i].add(n);
      cols[j].add(n);
      miniGrids[gridId].add(n);
    }
  }

  return true;
}

Undergraduate

Answer 4

Here is a simpler way. You basically use a hash object to keep track of the rows, columns and sub-boxes.

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', '.', '.', '.', '.'],
];

function isValidSudoku(grid) {
    let seenRow = {},
        seenCol = {},
        seenSubBox = {},
        seen = {}

    for (let row = 0; row < 9; row++) {
        for (let col = 0; col < 9; col++) {
            let value = grid[row][col];
            if (!(value === '.')) {
                let rowKey = `${row}-${value}`,
                    colKey = `${col}-${value}`,
                    boxKey = `${Math.floor(row/3)}-${value}-${Math.floor(col/3)}`

                if (seenRow[rowKey] || seenCol[colKey] || seenSubBox[boxKey]) {
                    return false;
                }               
                seenRow[rowKey] = true;
                seenCol[colKey] = true;
                seenSubBox[boxKey] = true;
            }
        }
    }

    return true;
}

console.log(isValidSudoku(_board));

Barbellate

the point here is a resolutor, not just a validator of the board – Qr

Answer 5

I have written a solution to solve any squared sudoku since the answers solve only 9x9 squared.

https://github.com/Eomm/grokking/blob/master/games/sudoku/play-sudoku.js

The algorithm is always the backtracking one, but it is optimized to reduce the iterations (aka time) ignoring the default cells and using stochastic statistics to choose the value (aka random :) ).

Compared to the first answer that iterates always 768.028 times, this solution runs from 3.556 (very lucky run) to 31.824 (not so lucky) with an average of 19.592 iterations in 100 tests. Comparison done with the same input of course.

Here the code:

const gameSet = [
  new Uint8Array([0, 0, 1, 5, 0, 0, 0, 7, 0]),
  new Uint8Array([0, 0, 4, 0, 6, 0, 0, 0, 9]),
  new Uint8Array([0, 3, 0, 0, 0, 4, 0, 0, 0]),
  new Uint8Array([6, 2, 0, 0, 0, 5, 1, 0, 0]),
  new Uint8Array([0, 4, 0, 0, 0, 0, 5, 2, 0]),
  new Uint8Array([0, 0, 0, 0, 4, 8, 0, 0, 3]),
  new Uint8Array([4, 1, 0, 0, 7, 0, 0, 0, 0]),
  new Uint8Array([0, 0, 6, 8, 0, 0, 0, 0, 1]),
  new Uint8Array([8, 0, 0, 0, 0, 9, 0, 3, 0])
]

process.nextTick(() => {
  const sudoku = new Sudoku({ squareRegion: 3 })
  sudoku.play(gameSet)
  console.log(sudoku.printable())
})

function Sudoku (opts = {}) {
  // TODO improve to support different sudoku types
  this.region = opts.squareRegion || 3 // default classic
}

Sudoku.prototype.play = function (gameSet) {
  const allCells = buildCellStructure(gameSet, this.region)

  this.valueSet = Array(gameSet[0].length).fill(0).map((_, i) => (i + 1))

  // to reduce the calculation, we can just ignore the default game cells
  const cells = allCells.filter(c => c.init === 0)
  let iter = 0
  for (let i = 0; i < cells.length; i++) {
    const cell = cells[i]
    iter++
    if (!solveCell.call(this, cell)) {
      cell.history.clear() // out tries are invalid

      let backTrack = i - 1
      for (; backTrack >= 0; backTrack--) {
        if (assignValue.call(this, cells[backTrack], 0)) {
          break
        }
      }
      i = backTrack - 1
    }
  }

  this.lastGame = gameSet
  this.lastResult = allCells.map(_ => _.value)

  console.log(iter)
  return this.lastResult
}

function solveCell (cell) {
  const chooseNewValue = chooseValue.call(this, cell)
  if (chooseNewValue === 0) {
    return false
  }
  assignValue.call(this, cell, chooseNewValue)
  return true
}

function assignValue (cell, value) {
  cell.rows[cell.x] = value
  cell.columns[cell.y] = value
  cell.square[(cell.x % this.region) + ((cell.y % this.region) * this.region)] = value
  cell.value = value

  if (value > 0) {
    cell.history.add(value)
  }
  return true
}

Sudoku.prototype.printable = function (result) {
  const print = result || this.lastResult
  if (!print) {
    // nothing to print
    return
  }

  return print.flatMap((val, i) => {
    if ((i + 1) % this.region === 0) {
      if ((i + 1) % (this.region ** 2) === 0) {
        if ((i + 1) % (this.region ** 3) === 0) {
          return [val, '|', '\n', '-'.repeat(this.region ** 2), '--|\n']
        } else {
          return [val, '|', '\n']
        }
      } else {
        return [val, '|']
      }
    }
    return val
  }).join('')
}

function chooseValue (cell) {
  const values = this.valueSet
    .filter(_ => !cell.rows.includes(_))
    .filter(_ => !cell.columns.includes(_))
    .filter(_ => !cell.square.includes(_))
    .filter(_ => !cell.history.has(_))
  if (values.length === 0) {
    return 0
  }
  // stochastic hope
  return values[Math.floor(Math.random() * values.length)]
}

// this structure point always to the same arrays
function buildCellStructure (gameSet, squareLength) {
  const cells = []

  const columnMap = new Map()
  const squareMap = new Map()

  gameSet.forEach((row, y) => {
    row.forEach((cellValue, x) => {
      if (!columnMap.has(x)) {
        columnMap.set(x, [])
      }
      columnMap.get(x).push(cellValue)

      const squareId = `${Math.floor(x / squareLength)}-${Math.floor(y / squareLength)}`
      if (!squareMap.has(squareId)) {
        squareMap.set(squareId, [])
      }
      squareMap.get(squareId).push(cellValue)

      cells.push({
        x,
        y,
        value: cellValue,
        init: cellValue,
        rows: row,
        columns: columnMap.get(x),
        squareId,
        square: squareMap.get(squareId),
        history: new Set(),
        iter: 0
      })
    })
  })

  return cells
}

Freemasonry

Answer 6

using backtrack and search. also, you can visualise your solved board little better. Check this out.

const b = null;

//test cases

const bd1 = [
    [1, b, b, b, b, b, b, b, 7],
    [b, b, b, b, b, b, b, b, b],
    [b, b, b, 5, b, b, b, b, b],
    [b, b, b, b, b, b, b, b, b],
    [b, b, b, b, b, b, b, b, b],
    [b, b, b, b, 1, b, b, b, b],
    [b, b, b, b, b, b, b, b, b],
    [b, 2, b, b, b, b, b, b, b],
    [b, b, b, b, b, b, b, b, 6],
] 

const bd2 = [
    [1, b, 5, b, b, b, b, b, 3],
    [3, b, b, b, b, b, b, b, b],
    [b, b, b, b, 8, b, b, b, b],
    [b, b, b, b, b, b, b, b, b],
    [b, b, b, b, b, b, b, b, b],
    [b, b, b, b, b, b, 4, b, b],
    [b, b, b, b, b, b, b, b, b],
    [b, 3, b, b, b, b, b, b, b],
    [b, b, b, b, b, b, b, b, 9],
]

const bd3 = [
    [b, b, b, b, b, b, b, b, b],
    [b, b, b, b, b, b, b, b, b],
    [b, b, b, b, b, b, b, b, b],
    [b, b, b, b, b, b, b, b, b],
    [b, b, b, b, b, b, b, b, b],
    [b, b, b, b, b, b, b, b, b],
    [b, b, b, b, b, b, b, b, b],
    [b, b, b, b, b, b, b, b, b],
    [b, b, b, b, b, b, b, b, b],
] 

//words toughest 2012
const bdTf = [
    [8, b, b, b, b, b, b, b, b],
    [b, b, 3, 6, b, b, b, b, b],
    [b, 7, b, b, 9, b, 2, b, b],
    [b, 5, b, b, b, 7, b, b, b],
    [b, b, b, b, 4, 5, 7, b, b],
    [b, b, b, 1, b, b, b, 3, b],
    [b, b, 1, b, b, b, b, 6, 8],
    [b, b, 8, 5, b, b, b, 1, b],
    [b, 9, b, b, b, b, 4, b, b],
] 



function solveSudoku(board) {
    if (solveSudokud(board)) {
        return board
    } else {
        const possibilities = nextBoards(board)
        const validBoards = keepOnlyValid(possibilities) //filterFunction
        return searchForSolution(validBoards) //helperFunction :backtracking
    }
}

function searchForSolution(boards) {    
    if (boards.length < 1) {        //checking the board is empty
        return false
    } else {        
        var first = boards.shift()  //tak̉es the first board off and stores in the variable
        const tryPath = solveSudoku(first)   
        if (tryPath != false) { //checking if tryPath is false or not. if it is not false, we wil return the solved board
            return tryPath
        } else {
            return searchForSolution(boards)    
        }        
    }
}
function solveSudokud(board) {
    for (var i = 0; i < 9; i++) {       
        for (var j = 0; j < 9; j++) {
            if (board[i][j] === null) {
                return false
            }
        }
    }
    return true
}
//nextBoardFunction will generate 9 possiblities for a pissible sudoku board
function nextBoards(board) { 
    var res = [];       
    const firstEmpty = findEmptySquare(board) 
    if (firstEmpty != undefined) {     //if firstEmpty = not defined , then we will start generating possiblities 
        const y = firstEmpty[0]     
        const x = firstEmpty[1]
        for (var i = 1; i < 10; i++) {
            var newBoard = [...board]
            var row = [...newBoard[y]]
            row[x] = i
            newBoard[y] = row
            res.push(newBoard)
        }
    }
    return res // if firstEmpty does =  undefined that means there are no possibilities left and return res.
}

function findEmptySquare(board) {
    // board --> [int, int] | represents the x and y coordinates of the empty sq
    for (var i = 0; i < 9; i++) {
        for (var j = 0; j < 9; j++) {
            if (board[i][j] == null) {
                return [i, j]
            }
        }
    }
}
//filter funtion
function keepOnlyValid(boards) {
    return boards.filter(b => validBoard(b))    //filtered version of the board array will be returned
}   
function validBoard(board) {
    
    // check each row
    for(let i=0; i<9; i++) {
        if(!validate(board[i])) return false
    }
    //check each col
    for(let i=0; i<9; i++) {
        var arr = []
        for(let j=0; j<9; j++) {
            arr.push(board[j][i]);
        }
        if(!validate(arr)) return false;
    }
    //check each 3*3
    let row = [[0,1,2], [3,4,5], [6,7,8]]
    let col = [[0,1,2], [3,4,5], [6,7,8]]
    for(let i of row) {
        for(let j of col) {
            let arr = [];
            for(let num1 of i) {
                for(let num2 of j){
                    arr.push(board[num1][num2]);
                }
            }
            if(!validate(arr)) return false;
        }
    }
    return true
}



function validate(arr) {
    //check duplicates
    let set1 = new Set();
    for(let i=0; i< arr.length; i++) {
        if(arr[i] === b) continue;
        if(set1.has(arr[i])) return false
        set1.add(arr[i]);
    }
    return true
}


//for better visualisation and able to check manually

function get_row(board, row) {
    
    return board[row]
    
}
function print_cell(value) {
    if (Array.isArray(value)) {
        return '.'
    } else if (value == null) {
        return '.'
    } else {
        return value
    }
}
function print_board(board) {
   
    console.log()
    for (i = 0; i < 9; i++) {
        let row = get_row(board, i)
        if (i % 3 == 0) {
            console.log("|=======|=======|=======|")
        }
        console.log("|",
            print_cell(row[0]), print_cell(row[1]), print_cell(row[2]), "|",
            print_cell(row[3]), print_cell(row[4]), print_cell(row[5]), "|",
            print_cell(row[6]), print_cell(row[7]), print_cell(row[8]), "|")
    }
    console.log("|=======|=======|=======|")
}

console.log('testcase 1')
print_board(bd1)
print_board(solveSudoku(bd1))
console.log('testcase 2')
print_board(bd2)
print_board(solveSudoku(bd2))
console.log('testcase 3')
print_board(bd3)
print_board(solveSudoku(bd3))
console.log('testcase 4')
print_board(bdTf)
print_board(solveSudoku(bdTf))

Koodoo

Answer 7

I have used array.some which terminates the program as soon as the condition is not met and hence improves the performance. And no extra loop required to initialize 3*3 sub-matrix, I have done it in the some method only by checking if the matrix array already exists or not.

function sudoku2(grid) {
    let arrCol = [0,0,0,0,0,0,0,0,0];
    let arrRow = [0,0,0,0,0,0,0,0,0];
    let matrix = [];
    const result = grid.some((element, index) => {
        let internalResult = element.some((item, i) => {
            // matrix
            const gridId = Math.trunc(i/3)*3 + Math.trunc(index/3);
            if(!matrix[gridId]) {
                matrix[gridId] = [];
            }
            if(matrix[gridId].indexOf(item) != -1 && item != '.') {
                return true;
            } else if(item != '.'){
                matrix[gridId].push(item);
            }
            
            // column
            if (arrCol.indexOf(grid[i][index]) === -1 && (grid[i][index] != '.')) { 
                arrCol[Number(grid[i][index])] = grid[i][index];
            }
            else if (grid[i][index] != '.'){
                return true;
            }   
            
            // row
            if (arrRow.indexOf(grid[index][i]) === -1 && (grid[index][i] != '.')) { 
                arrRow[Number(grid[index][i])] = grid[index][i];

            } else if (grid[index][i] != '.') {
                return true;
            }
            if(i === 8) {
                arrRow = [0,0,0,0,0,0,0,0,0];   
                arrCol = [0,0,0,0,0,0,0,0,0];             
            }
        });
        
        // true means duplicate found in some method
        if(internalResult === true) {
            console.log('outer');
            return internalResult;
        } else if (index === 8) {
            return false // false means no duplicate found
        }
    });
    return !result;  
}

Jungly