[Leetcode] 37. Sudoku Solver

Problem

문제 링크

스도쿠 문제를 풀면된다.

Solution

DFS에 Backtracking을 응용한 문제

배열을 '열'부터 순차적으로 .을 만났을때 1~9까지 값을 넣어보면서 스도쿠의 조건에 올바른지 확인한다.
만약 조건에 맞지않다면 바로 이전 경우의 수로 돌아가 다음 케이스를 넣어본다. 이 방법을 조건이 맞는 경우가 나올때까 실행하다가 모든 행렬을 다 돌면 그값을 리턴한다.

JS Code

/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solveSudoku = function (board) {
  const N = 9
  function doSolveSudoku(grid, row, col) {
    // All checked matrix (row,col)
    if (row === N - 1 && col === N) return true

    // move row
    if (col === N) {
      row++
      col = 0
    }

    // next col
    if (grid[row][col] !== '.') return doSolveSudoku(grid, row, col + 1)

    // input 1~9 case
    for (let num = 1; num <= 9; num++) {
      if (isSafe(grid, row, col, num)) {
        grid[row][col] = `${num}`
        if (doSolveSudoku(grid, row, col + 1)) return true
      }
      grid[row][col] = '.'
    }
    return false
  }

  function isSafe(grid, row, col, num) {
    for (let x = 0; x < 9; x++) if (grid[row][x] == num) return false

    for (let y = 0; y < 9; y++) if (grid[y][col] == num) return false

    const startRow = row - (row % 3),
      startCol = col - (col % 3)
    for (let i = 0; i < 3; i++) for (let j = 0; j < 3; j++) if (grid[i + startRow][j + startCol] == num) return false

    return true
  }

  doSolveSudoku(board, 0, 0)
  return board
}