Toy06 - Sudoku

으아... 자바스크립트... STL...해.줘...

레퍼런스 코드 분석입니다.

//대충 어떤느낌이냐면
//우리는 board에서 0인 부분만 채워넣으면 되잖아요?
//그니까 [0,0]부분부터 보면
//[0,0]부분이 4랑 5가 가능 하잖아요
//그러면 일단 [0,0]을 4로 가정하고
//이제 [0,2]로 가보는거에요
//그럼 [0,0]은 4니까 [0,2]는 5밖에 안되는거죠?
//그럼 이제 [0,0]은 4, [0,2]는 5
//이제 [0,5]로 향하는거에요
//aux가 재귀인데 이렇게 돌아간다고 생각하면 됩니다.

//근데 만~~약에 [0,0]부분이 4가 아니였어요!
//그러면 4를 사용했다는 흔적을 싹 지워버리고
//[0,0]가 5라고 생각하고 또 프로그램을 돌리는거에요

const sudoku = function (board) {
  const N = board.length;
  //boxes의 해당 값은 3*3의 자리를 표시
  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],
  ];
  //getBoxNum = boxes의 row,col에 해당하는 값을 가져오는 함수
  //즉, 3*3의 위치를 가져옴
  const getBoxNum = (row, col) => boxes[row][col];
  const blanks = []; //0인 숫자들을 배열에 넣은것
  const rowUsed = []; //해당 행에서 숫자를 사용했는지 여부 
  const colUsed = []; //해당 열에서 숫자를 사용했는지 여부 
  const boxUsed = []; //3*3박스에서 숫자를 사용했는지 여부
  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));
  }
  //여기서rowUsed, colUsed, boxUsed는
  //false, true, true, true, true ~~~~  
  //false, true, true, true, true~~~~
  //이런 형식으로 됨.
  //맨앞이 false인 이유는 0은 딱히 의미가 없으니까요!

  //0인 숫자는 blanks배열에 넣어주고
  //0이 아닌 숫자는 행, 열, 박스에서 사용되었다고 true로 표시해주기
  for (let row = 0; row < N; row++) {
    for (let col = 0; col < N; col++) {
      if (board[row][col] === 0) { //입력된 배열의 값이 0이면
        blanks.push([row, col]); //0에 해당하는 row와 col을 blanks배열에 넣음
      } 
      else { //입력된 배열의 값이 0이 아니면
        const num = board[row][col]; //num에 입력된 배열에 해당하는 값 넣어주고
        const box = getBoxNum(row, col); //boxes에 해당하는 값을 넣어줌
        rowUsed[row][num] = true; //해당 행에서 숫자를 사용했다고 표시
        colUsed[col][num] = true; //해당 열에서 숫자를 사용했다고 표시
        boxUsed[box][num] = true; //3*3작은 박스 기준에서 숫자를 사용했다고 표시
      }
    }
  }

  //이 함수는 num이 사용됐는지 안됐는지 확인하는 함수
  const isValid = (row, col, num) => {
    const box = getBoxNum(row, col);
    return (
      rowUsed[row][num] === false && //해당 행에서 숫자가 사용됐는지
      colUsed[col][num] === false && //해당 열에서 숫자가 사용됐는지
      boxUsed[box][num] === false //3*3의 박스에서도 숫자가 사용됐는지 판단
      //어디서도 사용되지 않았으면 return true~
      //잘 기억하셈. !!사용되지 않았으면!! true임
    );
  };
  //단순히 배열들을 다시 초기화해주는 함수
  const toggleNum = (row, col, num) => {
    const box = getBoxNum(row, col);
    board[row][col] = num;
    rowUsed[row][num] = !rowUsed[row][num]; //행을 false <-> true
    colUsed[col][num] = !colUsed[col][num]; //열을 false <-> true
    boxUsed[box][num] = !boxUsed[box][num]; //박스를 false <-> true
  };
  
  //이 함수가 실제로 스도쿠 돌아가는 재귀함수여요
  const aux = (idx, blanks, board) => {//인덱스, 0들이 있는 배열, 입력배열
    //이 if문은 탈출문.
    //입력된 배열의 0인 숫자의 개수만큼 돌았으면 끝나게 구현됐음
    //이게 어떤 의미냐면
    //[0,0]이 4라고 가정하고, [0,2]가 5라고 가정하고~~~~
    //이걸 계속 해서 마지막 [8,8]까지 한번 다 돌았다는 뜻임.
    if (idx === blanks.length) {
      return true;
    }

    const [row, col] = blanks[idx]; //행,열은 blanks의 idx
    for (let num = 1; num <= 9; num++) { //1부터 9까지 돌면서
      if (isValid(row, col, num) === true) { //행과 열에서 숫자가 쓰이지 않았으면
        toggleNum(row, col, num); //사용되었다고 바꾸고
        //이 아래 if문과 그 밑줄의 toggleNum의 역할은
        //만약에 첫번째 예시처럼 [0,0]자리에 들어갈 수 있는 숫자가 4,5라고 치면
        //[0,0]자리를 4로 가정하고 나머지 자리를 돌린다음에
        //그게 안되면 다시 [0,0]으로 돌아와서 
        //[0,0]이 5일때를 가정하고
        //다시 들어가는 느낌임!
        if (aux(idx + 1, blanks, board) === true) {
          return true;
        }
        //이 자리가 4가 아니라면 다시 4를 사용하지 않았다고 해줘야하니까
        //이 toggleNum으로 사용하지 않았다고 바꿔주는거
        toggleNum(row, col, num);
      }
    }
    return false;
  };

  aux(0, blanks, board); //위에는 어찌보면 다 세팅이고 이게 정말 함수들을 돌리는거.
  return board;
};