Algorithm problem-06

1. 문제

• 스도쿠 보드를 완성해라

2. 시도

• 가로, 세로, 3x3보드 내에서 중복되는 숫자가 없는지를 각각 검사하도록 내부 함수 구현
• 3가지를 모두 통과하는 숫자를 빈칸에 배치하도록 하고
• 0,0 부터 8,8까지를 전부 검사한 후, 리턴 보드하면 될 것이라고 예상

3. 수도코드

const sudoku = function (board) {
  // 보드, 바꿔야할 숫자, 숫자의 위치 정보(r/c index값)
  // 위의 정보를 같이 전달해 줘야 함
  // 0인 위치 정보를 빈 배열에 저장, 저장한 값들을 꺼내서 사용
  const emptySpot = (board) => {
    let spot = []
    for (let i = 0; i < board.length; i++) {
      for (let j = 0; j < board[i].length; j++) {
        if (board[i][j] === 0) {
          spot.push([i, j])
        }
      }
    }
  }
  
  // 가로를 검사하는 함수, boolean
  // 변수의 보드에서의 위치에 따른 검사 행을 설정해야 함
  const row = (board, r, n) => {
  }
  // 세로를 검사하는 함수, boolean
  // 변수의 보드에서의 위치에 따른 검사 열을 설정해야 함
  const column = (board, c, n) => {
  }
  // 3x3 블록을 검사하는 함수, boolean
  // 변수의 보드에서의 위치에 따른 검사 블럭을 설정해야 함
  const block = (board, r, c, n) => {
  }
  // 포문, 0일때 3가지 조건을 모두 통과하는 숫자로 바꿔서 대입
  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[i].length; j++) {
      if (board[i][j] === 0) {
        for (let k = 0; k <= 9; k++) {
          if (row(k) && column(k) && block(k)) {
            board[i][j] = k
          }
        }
      }
    }
  }
  // 포문이 끝나고 나오면 리턴 보드
  return board;
};
// 3가지 조건이 존재
// 열, 행, 그리고 3X3 내에 중복되는 숫자가 없어야 함(1-9)
// 각각의 조건을 따로 판별하는 내부 함수를 만들고
// 0이 입력된 곳에 숫자를 변경하도록 구현

4. 레퍼런스

const sudoku = function (board) {
  // 빈 칸을 찾아서 저장하는 함수, 빈 칸은 0으로 표현하였음
    function nextEmptySpot(board) {
      for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board.length; j++) {
          if (board[i][j] === 0) return [i, j];
        }
      }
    return [-1, -1];
    }
    // row 열(가로)값을 돌아보는 함수이다.
    function checkRow(board, row, value){
      for(let i = 0; i < board[row].length; i++) {
        if(board[row][i] === value) {
          return false;
        }
      }
    return true;
    }
    // col 행(세로)값을 돌아보는 함수이다.
    function checkColumn(board, column, value){
      for(let i = 0; i < board.length; i++) {
        if(board[i][column] === value) {
          return false;
        }
      }
    return true;
    };
    // board의 [row, col]에 value값이 있는지 확인하는 함수이다.
    function checkSquare(board, row, column, value){
      boxRow = Math.floor(row / 3) * 3;
      boxCol = Math.floor(column / 3) * 3;
      for (let r = 0; r < 3; r++){
        for (let c = 0; c < 3; c++){
          if (board[boxRow + r][boxCol + c] === value) {
            return false;
          }
        }
      }
    return true;
    };
    // value값을 확인하는 함수이다. row, col, square 모두 값이 같다면 true
    function checkValue(board, row, column, value) {
      if(checkRow(board, row, value) &&
        checkColumn(board, column, value) &&
        checkSquare(board, row, column, value)) {
        return true;
      }
    return false;
    };
  
    let emptySpot = nextEmptySpot(board);
    let row = emptySpot[0];
    let col = emptySpot[1];
    if (row === -1){
      return board;
    }
    for(let num = 1; num <= board.length; num++){
      if (checkValue(board, row, col, num)){
        board[row][col] = num;
        sudoku(board);
      }
    }
    if (nextEmptySpot(board)[0] !== -1) {
      board[row][col] = 0;
    }
    return board;
  }