[JS 알고리즘] Toy 6 - sudoku 스도쿠

노션에서 마이그레이션 중이며, 순서는 랜덤하게 업로드하고 있습니다.

 

해당 문제는 코드스테이츠의 Toy problem을 출처로 합니다.
2022.04.07

 

문제

스도쿠는 숫자 퍼즐로, 가로 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. 스도쿠의 빈칸을 파악한다.

    1-1. 스도쿠 배열의 [row][col] 이 0인 것들만 골라 blanks 라는 배열에 담는다.

2. 스도쿠 빈칸에 넣을 수 있는 숫자들을 파악한다.

    2-1. 스도쿠 배열의 rowUsed[row][i] 행에 위치한 숫자들 파악

    2-2. 스도쿠 배열의 colUsed[col][i] 열에 위치한 숫자들 파악

    2-3. 스도쿠 배열 내 boxUsed[box][i] 3x3 사각형 안에 있는 숫자들 파악

3. 2번 과정에서 겹치지 않은 숫자를 빈칸에 넣음

4. 이 과정을 재귀로 계속 반복하여 빈칸을 채움

 

 스도쿠 배열 내 모든 빈칸을 다 채우면 스도쿠를 출력(스도쿠가 여러개 출력될 시) 하나만 출력하면 되므로 프로세스 강제 종료 시 '0'으로 표기된 빈자리가 발견될 때 마다 해당 자리에 1부터 9까지의 수를 모두 넣어보면서 정답이 나올때 까지 찾아보면된다.

 스도쿠 게임판을 탐색하다가 0을 발견하면 해당자리에 1부터 9의 수를 차례로 넣어가면서 해당자리에 적합한 숫자인지 check라는 함수로 확인한다. 이때 check 함수는 가로, 세로, 사각형을 모두 검사한다. 사각형을 확인할때는 0이 발견된 좌표를 다음과 같이 처리한다.

  // 사각형 확인.
  x = parseInt((x / 3)) * 3;
  y = parseInt((y / 3)) * 3;

 만약 check라는 함수를 통해서 해당 숫자가 부적합하다는 결과가 return된다면 해당자리를 다시 0으로 되돌려놓고 다음숫자를 넣어본다.

 

 만약 9까지 넣어봤는데도 실패했다면 해당칸 이전에 넣었던 숫자가 옳지않은 숫자인것이다. 따라서 9까지 실패했다면 즉시 return 하여 이전단계의 숫자를 바꿔주는 과정을 거친다.

 

 스도쿠 게임판을 입력받을때 0의 개수를 세어서 총 몇개의 자리를 채워넣어야 스도쿠가 완성되는지 확인하기로 하였다. 그래서 blank 라는 변수를 사용해서 0의 개수를 세어주었다. 그리고 blank가 0이되면 스도쿠 게임판을 출력해주고 end라는 변수를 true로 바꿔줌으로써 여러가지 경우의 완성된 게임판이 출력되는것을 방지하였다. (end 변수를 통하여 제어해주지 않으면 모든 칸이 0 으로 이루어진 스도쿠 게임판이 입력으로 들어올때 매우 많은 완성된 스도쿠들을 출력하게 된다.)

 

작성 코드

const sudoku = function (board) {
  const N = board.length;
  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 = [];
  for (let row = 0; row < N; row++) {
    rowUsed.push(Array(N + 1).fill(false));
    colUsed.push(Array(N + 1).fill(false));
    boxUsed.push(Array(N + 1).fill(false));
  }

  for (let row = 0; row < N; row++) {
    for (let col = 0; col < N; col++) {
      if (board[row][col] === 0) {
        blanks.push([row, col]);
      } else {
        const num = board[row][col];
        const box = getBoxNum(row, col);
        rowUsed[row][num] = true;
        colUsed[col][num] = true;
        boxUsed[box][num] = true;
      }
    }
  }

  const isValid = (row, col, num) => {
    const box = getBoxNum(row, col);
    return (
      rowUsed[row][num] === false &&
      colUsed[col][num] === false &&
      boxUsed[box][num] === 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) {
        toggleNum(row, col, num);
        if (aux(idx + 1, blanks, board) === true) {
          return true;
        }
        toggleNum(row, col, num);
      }
    }
    return false;
  };

  aux(0, blanks, board);
  return board;
};

 

Reference Code

const sudoku = function (board) {
  const N = board.length;
  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];

// 세로 가로 3*3 박스 false로 채워 넣음
  const blanks = [];
  const rowUsed = [];
  const colUsed = [];
  const boxUsed = [];
  for (let row = 0; row < N; row++) {
    rowUsed.push(Array(N + 1).fill(false));
    colUsed.push(Array(N + 1).fill(false));
    boxUsed.push(Array(N + 1).fill(false));
  }
  
// 0이면 값을 blanks에 좌표 표시, 아니면 ture 표시
  for (let row = 0; row < N; row++) {
    for (let col = 0; col < N; col++) {
      if (board[row][col] === 0) {
        blanks.push([row, col]);
      } else {
        const num = board[row][col];
        const box = getBoxNum(row, col);
        rowUsed[row][num] = true;
        colUsed[col][num] = true;
        boxUsed[box][num] = true;
      }
    }
  }

// 가로 세로 3*3이 모두 false일때 (사용되지 않았을 때)
  const isValid = (row, col, num) => {
    const box = getBoxNum(row, col);
    return (
      rowUsed[row][num] === false &&
      colUsed[col][num] === false &&
      boxUsed[box][num] === false
    );
  };

// num을 주어진 원본 보드에 넣고 가로 세로 3*3 boolean 값 뒤집기
  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];
  };


 // 스도쿠 값 넣기 (함수 실행), idx는 0 고정
    const aux = (idx, blanks) => {
    
      if (idx === blanks.length) { // 보드에 있는 모든 0에 대한 값을 넣었을 때 빠져나옴
        return true;
      }
  
      const [row, col] = blanks[idx]; // 좌표를 실체화(표현)
      
      for (let num = 1; num <= 9; num++) {
        if (isValid(row, col, num)) {  // 가로 세로 3*3 박스가 false 일때(num과 겹치는 숫자X)
          toggleNum(row, col, num);    // num값 보드에 넣고 트루로 변경
          if (aux(idx + 1, blanks)) {  // 재귀함수로 blanks 값인 다음 0인 좌표로 넘어감
            return true;
          }
          toggleNum(row, col, num); // 부적합한 숫자라 사용하지 않았으므로 다시 되돌려놓음
        }
      }
      return false; // 9까지 돌았는데도 적합한 숫자가 없으면 다시 이전 자리로 돌아가기 위함
    };
  
    aux(0, blanks);
    
    return board;
  };

 

 

---

 

 

구현하는 게 어려웠던 문제ㅠㅠ 레퍼런스 코드와 참고링크를 이해하는 것도 시간이 오래 걸렸다.

나중에 알고리즘 경험이 좀 더 쌓였을 때 다시 한 번 더 풀어보면 좋을 것 같다.

 

참고

Backtracking Algorithm to Solve Sudoku Puzzle in JavaScript