Sudoku Solver

sudoku-solver.ts

type IRow = number[]
type IBoard = IRow[]

const board: IBoard = [
  [4, 5, 0, 8, 0, 0, 9, 0, 0],
  [0, 9, 0, 0, 5, 6, 0, 0, 4],
  [1, 0, 0, 0, 0, 0, 0, 0, 7],
  [2, 6, 0, 5, 4, 0, 0, 9, 0],
  [0, 0, 4, 1, 0, 2, 3, 0, 0],
  [0, 7, 0, 0, 6, 9, 0, 4, 8],
  [7, 0, 0, 0, 0, 0, 0, 0, 9],
  [8, 0, 0, 4, 9, 0, 0, 7, 0],
  [0, 0, 9, 0, 0, 3, 0, 2, 5],
]

let attempts = 0

// Check if value exists within row
const findInRow = (board: IBoard, row: number, value: number) => {
  return board[row].indexOf(value) > -1
}

// Check if value exists within column
const findInCol = (board: IBoard, col: number, value: number) => {
  let match = false

  board.forEach(row => {
    if (row[col] === value) match = true
  })

  return match
}

// Check if value exists within square
const findInSquare = (
  board: IBoard,
  row: number,
  col: number,
  value: number
) => {
  const rowNumber = Math.floor(row / 3)
  const colNumber = Math.floor(col / 3)
  let match = false

  for (let i = rowNumber * 3; i < (rowNumber + 1) * 3; i++) {
    for (let j = colNumber * 3; j < (colNumber + 1) * 3; j++) {
      if (board[i][j] === value) {
        match = true
      }
    }
  }

  return match
}

// Check if value is valid in other cells of given square
const isValidInOtherSquareCells = (
  board: IBoard,
  row: number,
  col: number,
  value: number
) => {
  const rowNumber = Math.floor(row / 3)
  const colNumber = Math.floor(col / 3)
  let candidate = false

  for (let i = rowNumber * 3; i < (rowNumber + 1) * 3; i++) {
    for (let j = colNumber * 3; j < (colNumber + 1) * 3; j++) {
      if (board[i][j] !== 0) {
        continue
      }

      if (row === i && col === j) {
        continue
      }

      if (
        !findInRow(board, i, value) &&
        !findInCol(board, j, value) &&
        !findInSquare(board, i, j, value)
      ) {
        candidate = true
      }
    }
  }

  return candidate
}

// Get 2d array of all empty cells
const getEmptyCells = (board: IBoard) => {
  const cells: [number, number][] = []

  board.forEach((row, i) => {
    row.forEach((value, j) => {
      if (value === 0) {
        cells.push([i, j])
      }
    })
  })

  return cells
}

// Solve it
const solveBoard = (board: IBoard): void => {
  const emptyCells = getEmptyCells(board)

  emptyCells.forEach((cell, cellIdx) => {
    const row = cell[0]
    const col = cell[1]

    for (let i = 1; i <= 9; i++) {
      if (
        findInRow(board, row, i) ||
        findInCol(board, col, i) ||
        findInSquare(board, row, col, i) ||
        isValidInOtherSquareCells(board, row, col, i)
      ) {
        continue
      }
      board[row][col] = i
      emptyCells.splice(cellIdx, 1)
    }
  })

  // Repeat until all cells are solved
  if (emptyCells.length) {
    attempts++

    if (attempts > 20) {
      console.log('Sorry! Unable to solve.')
      return
    }

    solveBoard(board)
  }
}

solveBoard(board)

console.log(board)