JavaScript Algorithm - sudoku

 

 

문제 설명 : 

스도쿠는 숫자 퍼즐로, 가로 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],
];
 */

 

 

풀이코드 설명

구글링으로 답지를 봐서 알게된 코드로 아직 소화가 안됐다 다른 풀이가 있는지 좀 더 생각해봐야한다. 

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];
  console.log("getBoxNum", getBoxNum);
  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));
  }
  console.log("rowUsed", rowUsed); //[false,false .... false ] false가 10개
  // console.log("colUsed", colUsed); //[false,false .... false ] false가 10개
  // console.log("boxUsed", boxUsed); //[false,false .... false ] false가 10개

  for (let row = 0; row < N; row++) {
    for (let col = 0; col < N; col++) {
      console.log("row", row, "col", 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;
      }
    }
  }
  console.log("rowUsed true", rowUsed); //[false,false .... false ] false가 10개
  console.log("blanks", blanks);

  const isValid = (row, col, num) => {
    const box = getBoxNum(row, col);
    //전부 false면 true
    //하나라도 다르면 false 반환
    return (
      rowUsed[row][num] === false &&
      colUsed[col][num] === false &&
      boxUsed[box][num] === false
    );
  };

  //box에 getBoxNum 값을 할당한다.
  //board[row][col]에 입력 받은 num을 할당한다.
  //rowUsed, colUsed, boxUsed 의 정반대값을 넣어준다.
  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와 blanks의 길이가 같으면 true 반환
  const aux = (idx, blanks, board) => {
    if (idx === blanks.length) {
      return true;
    }

    //row, col에 블랭크 인덱스를 할당한다.
    const [row, col] = blanks[idx];

    //1부터 9까지 순회
    for (let num = 1; num <= 9; num++) {
      //isValid 값이 true면
      if (isValid(row, col, num) === true) {
        //toggleNum 실행
        toggleNum(row, col, num);

        //인덱스+1, blanks, board를 인자로 넣었을 때 반환값이 true면 true
        if (aux(idx + 1, blanks, board) === true) {
          return true;
        }
        toggleNum(row, col, num);
      }
    }
    return false;
  };

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

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("answer", 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],
  ];
   */

 

 

console.log로 출력된 값들

getBoxNum [Function: getBoxNum]
rowUsed [
  [
    false, false, false,
    false, false, false,
    false, false, false,
    false
  ],
  [
    false, false, false,
    false, false, false,
    false, false, false,
    false
  ],
  [
    false, false, false,
    false, false, false,
    false, false, false,
    false
  ],
  [
    false, false, false,
    false, false, false,
    false, false, false,
    false
  ],
  [
    false, false, false,
    false, false, false,
    false, false, false,
    false
  ],
  [
    false, false, false,
    false, false, false,
    false, false, false,
    false
  ],
  [
    false, false, false,
    false, false, false,
    false, false, false,
    false
  ],
  [
    false, false, false,
    false, false, false,
    false, false, false,
    false
  ],
  [
    false, false, false,
    false, false, false,
    false, false, false,
    false
  ]
]
row 0 col 0
row 0 col 1
row 0 col 2
row 0 col 3
row 0 col 4
row 0 col 5
row 0 col 6
row 0 col 7
row 0 col 8
row 1 col 0
row 1 col 1
row 1 col 2
row 1 col 3
row 1 col 4
row 1 col 5
row 1 col 6
row 1 col 7
row 1 col 8
row 2 col 0
row 2 col 1
row 2 col 2
row 2 col 3
row 2 col 4
row 2 col 5
row 2 col 6
row 2 col 7
row 2 col 8
row 3 col 0
row 3 col 1
row 3 col 2
row 3 col 3
row 3 col 4
row 3 col 5
row 3 col 6
row 3 col 7
row 3 col 8
row 4 col 0
row 4 col 1
row 4 col 2
row 4 col 3
row 4 col 4
row 4 col 5
row 4 col 6
row 4 col 7
row 4 col 8
row 5 col 0
row 5 col 1
row 5 col 2
row 5 col 3
row 5 col 4
row 5 col 5
row 5 col 6
row 5 col 7
row 5 col 8
row 6 col 0
row 6 col 1
row 6 col 2
row 6 col 3
row 6 col 4
row 6 col 5
row 6 col 6
row 6 col 7
row 6 col 8
row 7 col 0
row 7 col 1
row 7 col 2
row 7 col 3
row 7 col 4
row 7 col 5
row 7 col 6
row 7 col 7
row 7 col 8
row 8 col 0
row 8 col 1
row 8 col 2
row 8 col 3
row 8 col 4
row 8 col 5
row 8 col 6
row 8 col 7
row 8 col 8
rowUsed true [
  [
    false, true,  true,
    true,  false, false,
    true,  true,  false,
    false
  ],
  [
    false, false, false,
    false, false, false,
    true,  true,  true,
    true
  ],
  [
    false, true,  false,
    false, true,  true,
    false, false, false,
    true
  ],
  [
    false, true,  true,
    false, true,  false,
    false, false, true,
    false
  ],
  [
    false, false, true,
    false, true,  false,
    true,  false, false,
    true
  ],
  [
    false, false, true,
    true,  false, true,
    false, false, true,
    false
  ],
  [
    false, false, false,
    true,  true,  false,
    false, true,  false,
    true
  ],
  [
    false, false, false,
    true,  true,  true,
    true,  false, false,
    false
  ],
  [
    false, true,  false,
    true,  false, false,
    false, true,  true,
    false
  ]
]
blanks [
  [ 0, 0 ], [ 0, 2 ], [ 0, 5 ], [ 0, 7 ],
  [ 1, 2 ], [ 1, 3 ], [ 1, 5 ], [ 1, 6 ],
  [ 1, 8 ], [ 2, 2 ], [ 2, 3 ], [ 2, 4 ],
  [ 2, 7 ], [ 2, 8 ], [ 3, 2 ], [ 3, 4 ],
  [ 3, 5 ], [ 3, 6 ], [ 3, 8 ], [ 4, 0 ],
  [ 4, 1 ], [ 4, 4 ], [ 4, 7 ], [ 4, 8 ],
  [ 5, 0 ], [ 5, 2 ], [ 5, 3 ], [ 5, 4 ],
  [ 5, 6 ], [ 6, 0 ], [ 6, 1 ], [ 6, 4 ],
  [ 6, 5 ], [ 6, 6 ], [ 7, 0 ], [ 7, 2 ],
  [ 7, 3 ], [ 7, 5 ], [ 7, 6 ], [ 8, 1 ],
  [ 8, 3 ], [ 8, 6 ], [ 8, 7 ], [ 8, 8 ]
]
answer [
  [
    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
  ]
]

 

 

출처 : 코드스테이츠