[LeetCode] 37. Sudoku Solver

https://leetcode.com/

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:
1. Each of the digits 1-9 must occur exactly once in each row.
2. Each of the digits 1-9 must occur exactly once in each column.
3. Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

The '.' character indicates empty cells.

 

Example 1:

출처 : https://leetcode.com/problems/sudoku-solver/

Input: board =
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: [["5","3","4","6","7","8","9","1","2"],
["6","7","2","1","9","5","3","4","8"],
["1","9","8","3","4","2","5","6","7"],
["8","5","9","7","6","1","4","2","3"],
["4","2","6","8","5","3","7","9","1"],
["7","1","3","9","2","4","8","5","6"],
["9","6","1","5","3","7","2","8","4"],
["2","8","7","4","1","9","6","3","5"],
["3","4","5","2","8","6","1","7","9"]]
Explanation: The input board is shown above and the only valid solution is shown below:

출처 : https://leetcode.com/problems/sudoku-solver/

 

Constraints:

• board.length == 9
• board[i].length == 9
• board[i][j] is a digit 1-9 or '.'.
• It is guaranteed that the input board has only one solution.

 

Code :

var solveSudoku = function(board) {
    solve(board);
};

var solve = function(board) {
    for (let row = 0; row < 9; row++) {
        for (let col = 0; col < 9; col++) {
            if (board[row][col] === ".") {
                for (let num = 1; num <= 9; num++) {
                    const numStr = num.toString();
                    if (isValidMove(board, row, col, numStr)) {
                        board[row][col] = numStr;
                        if (solve(board)) {
                            return true;
                        }
                        board[row][col] = ".";
                    }
                }
                return false;
            }
        }
    }
    return true; // 스도쿠 퍼즐 완성
};

var isValidMove = function(board, row, col, num){
    for (let i = 0; i < 9; i++) {
        if (board[i][col] === num || board[row][i] === num) {
            return false; // 같은 열 또는 같은 행에 중복된 숫자가 있음
        }
    }
    
    const startRow = Math.floor(row / 3) * 3;
    const startCol = Math.floor(col / 3) * 3;
    for (let i = 0; i < 3; i++) {
        for (let j = 0; j < 3; j++) {
            if (board[startRow + i][startCol + j] === num) {
                return false; // 같은 3x3 서브 그리드에 중복된 숫자가 있음
            }
        }
    }
    
    return true;
};

 

Solutions Code :

function solveSudoku(board) {
  const n = board.length;
  // 스도쿠를 해결하는 함수 호출
  dfs(board, n);
}

function dfs(board, n) {
  // 스도쿠의 모든 셀에 대해서
  for (let row = 0; row < n; row++) {
    for (let col = 0; col < n; col++) {
      // 해당 셀이 비어있는 경우 건너뜀
      if (board[row][col] !== '.') continue;
      // 1부터 9까지의 숫자에 대해 시도
      for (let i = 1; i <= 9; i++) {
        const c = i.toString();
        // 해당 숫자가 유효한지 확인
        if (isValid(board, row, col, n, c)) {
          board[row][col] = c;
          // 해당 보드에 대한 검색을 계속하고, 해결책이 도출되면 true 반환
          if (dfs(board, n)) return true;
        }
      }
      // 1부터 9까지 어떤 숫자에 대해서도 해결책이 도출되지 않은 경우...
      // 현재 셀을 다시 빈 칸으로 설정
      board[row][col] = '.';
      // 막다른 골목을 나타내기 위해 false 반환
      return false;
    }
  }
  // 모든 셀이 채워졌으므로 해결책이 존재함을 나타냄
  return true;
}

function isValid(board, row, col, n, c) {
  // 현재 3x3 박스의 행과 열 인덱스 계산
  const blockRow = Math.floor(row / 3) * 3;
  const blockCol = Math.floor(col / 3) * 3;
  // 보드의 크기만큼 반복하면서 해당 숫자가 행, 열, 3x3 박스 내에서 중복되는지 확인
  for (let i = 0; i < n; i++) {
    // 현재 행 또는 열에 숫자가 중복되는 경우 false 반환
    if (board[row][i] === c || board[i][col] === c) return false;
    // 현재 3x3 박스 내에 숫자가 중복되는 경우 false 반환
    const curRow = blockRow +  Math.floor(i / 3);
    const curCol = blockCol +  Math.floor(i % 3);
    if (board[curRow][curCol] === c) return false;
  }
  // 모든 조건을 만족하는 경우 true 반환
  return true;
}

 

 

출처 : https://leetcode.com/problemset/all/

Problems - LeetCode