코딩테스트 문제 6

문제

스도쿠는 숫자 퍼즐로, 가로 9칸, 세로 9칸으로 이루어져 있는 표에 1부터 9까지의 숫자를 채워 넣는 퍼즐입니다. 퍼즐을 푸는 방법은 아홉 가로줄, 세로줄, 3X3 칸에 1에서 9까지의 숫자를 중복되지 않게 한 번씩만 넣으면 됩니다. 일부 칸이 비어있는 상태인 스도쿠 보드를 입력받아 스도쿠 퍼즐이 완성된 보드를 리턴해야 합니다.

입력

• 인자 1 : board
  • 가로 길이(board[i].length)와 세로 길이(board.length)가 모두 9인 2차원 배열
  • matrix[i][j]는 1 이상 9 이하의 자연수

출력

• 가로와 세로의 길이가 모두 9인 2차원 배열을 리턴해야 합니다.

주의사항

• 입력으로 주어지는 board를 직접 수정해도 상관없습니다.
• 입력으로 주어지는 board 가지고 완성시킬 수 있는 보드는 유일(unique)합니다.
• 숫자가 입력되지 않은 칸은 편의상 0이 입력되어 있습니다.

입출력 예시

let board = [
  [0, 3, 0, 2, 6, 0, 7, 0, 1],
  [6, 8, 0, 0, 7, 0, 0, 9, 0],
  [1, 9, 0, 0, 0, 4, 5, 0, 0],
  [8, 2, 0, 1, 0, 0, 0, 4, 0],
  [0, 0, 4, 6, 0, 2, 9, 0, 0],
  [0, 5, 0, 0, 0, 3, 0, 2, 8],
  [0, 0, 9, 3, 0, 0, 0, 7, 4],
  [0, 4, 0, 0, 5, 0, 0, 3, 6],
  [7, 0, 3, 0, 1, 8, 0, 0, 0],
];
let output = sudoku(board);
console.log(output); // -->
/* 
[
  [4, 3, 5, 2, 6, 9, 7, 8, 1],
  [6, 8, 2, 5, 7, 1, 4, 9, 3],
  [1, 9, 7, 8, 3, 4, 5, 6, 2],
  [8, 2, 6, 1, 9, 5, 3, 4, 7],
  [3, 7, 4, 6, 8, 2, 9, 1, 5],
  [9, 5, 1, 7, 4, 3, 6, 2, 8],
  [5, 1, 9, 3, 2, 6, 8, 7, 4],
  [2, 4, 8, 9, 5, 7, 1, 3, 6],
  [7, 6, 3, 4, 1, 8, 2, 5, 9],
];
 */

작성코드 1

const sudoku = function (board) {
const N = board.length; // 9개
// 임의로 초기 상태를 만든다
const boxes = [
  [0, 0, 0, 1, 1, 1, 2, 2, 2],
  [0, 0, 0, 1, 1, 1, 2, 2, 2],
  [0, 0, 0, 1, 1, 1, 2, 2, 2],
  [3, 3, 3, 4, 4, 4, 5, 5, 5],
  [3, 3, 3, 4, 4, 4, 5, 5, 5],
  [3, 3, 3, 4, 4, 4, 5, 5, 5],
  [6, 6, 6, 7, 7, 7, 8, 8, 8],
  [6, 6, 6, 7, 7, 7, 8, 8, 8],
  [6, 6, 6, 7, 7, 7, 8, 8, 8],
];
// 박스 배열의 각 요소
const getBoxNum = (row, col) => boxes[row][col];
const blanks = [];
const rowUsed = [];
const colUsed = [];
const boxUsed = [];
// 수도쿠는 1부터 시작이지만 배열의 인덱스는 0이 존재하기 때문에 더미 데이터로 false를 0번째 인덱스에 넣어준다.
for (let row = 0; row < N; row++) {
  rowUsed.push(Array(N + 1).fill(false)); // [false, false, false, false, false, false, false, false, false, false]
  colUsed.push(Array(N + 1).fill(false)); // [false, false, false, false, false, false, false, false, false, false]
  boxUsed.push(Array(N + 1).fill(false)); // [false, false, false, false, false, false, false, false, false, false]
}
// 만약 매개변수의 요소 값이 0이라면 빈 배열에 배열 요소([row, col])를 넣어준다.
for (let row = 0; row < N; row++) {
  for (let col = 0; col < N; col++) {
    if (board[row][col] === 0) {
      blanks.push([row, col]);
      }
      // 0이 아니라면 false에서 true로 바꿔준다.
      else {
        const num = board[row][col];
        const box = getBoxNum(row, col);
        rowUsed[row][num] = true;
        colUsed[col][num] = true;
        boxUsed[box][num] = true;
      }
  }
}
// true인지 아닌지를 찾는다. 즉 행, 열, 박스에 같은 숫자(num)가 있는지 체크하는 함수
const isValid = (row, col, num) => {
  const box = getBoxNum(row, col);
  return (
    rowUsed[row][num] === false &&
    colUsed[col][num] === false &&
    boxUsed[box][num] === false
    );
};
// aux함수를 실행시켰을 때 isValid에 대입했던 값이 맞으면 true, 틀리면 false로 변경해주는 함수
const toggleNum = (row, col, num) => {
  const box = getBoxNum(row, col);
  board[row][col] = num;
  rowUsed[row][num] = !rowUsed[row][num];
  colUsed[col][num] = !colUsed[col][num];
  boxUsed[box][num] = !boxUsed[box][num];
};
const aux = (idx, blanks, board) => {
  if (idx === blanks.length) {
    return true;
  }
  const [row, col] = blanks[idx];
  for (let num = 1; num <= 9; num++) {
    if (isValid(row, col, num) === true) {// 해답이 있으면 보드의 상태를 유지해야 하므로 false값을 true로 바꿔줍니다.
    toggleNum(row, col, num);
// idx번째에 숫자를 하나 넣었으므로 처음 빈칸의 인덱스는 idx+1이 되었습니다.
// 이 상태에서 보드의 해답이 존재하면 aux(idx + 1)은 보드를 완성하면서 true를 리턴하고
// 해답이 없으면 보드를 현재 상태로 유지하면서 false를 리턴합니다.
    if (aux(idx + 1, blanks, board) === true) {
      return true;
    }
// aux(idx + 1)이 false를 리턴했을 때 실행됩니다.
// 해답이 없으면 보드의 상태를 유지해야 하므로 true값을 false로 바꿔줍니다.
  toggleNum(row, col, num);
  }
 }
 return false;
};
aux(0, blanks, board);
return board;
};