스도쿠 문제를 풀면된다.
DFS에 Backtracking을 응용한 문제
배열을 '열'부터 순차적으로 .
을 만났을때 1~9까지 값을 넣어보면서 스도쿠의 조건에 올바른지 확인한다.
만약 조건에 맞지않다면 바로 이전 경우의 수로 돌아가 다음 케이스를 넣어본다. 이 방법을 조건이 맞는 경우가 나올때까 실행하다가 모든 행렬을 다 돌면 그값을 리턴한다.
/**
* @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
}