문제
스도쿠는 숫자 퍼즐로, 가로 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~9 중복 없이 하나씩 들어갈 수 있다.
- 각 열(세로줄)에는 숫자 1~9 중복 없이 하나씩 들어갈 수 있다.
- 각 3 x 3칸 숫자 1~9 중복 없이 하나씩 들어갈 수 있다.
이 각 규칙의 어떤 숫자가 사용되었는지 여부를 boolean으로 갖고 있는 10x9배열을 만든다.
- rowUsed
- colUsed
- boxUsed
0번째 인덱스는 더미이다.
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
1, 2, 3, 6, 7이 사용되있다.( 인자 board의 해당위치에 숫자가 들어가있다.)
[false, true, true, true, false, false, true, true, false, false]
boxUsed 배열을 만들기 위해 3 x 3박스마다 숫자를 붙여줘야한다.
3 x 3 박스를 구분 짓기 위해 배열을 만든다.
해당위치에 rowUsed, colUsed, boxUsed 조건을 모두 충족하는 숫자를 인자 board의 해당위치에 넣어준다.
변경된 board를 리턴한다.
코드 + 설명
const sudoku = function (board) {
// 인자 board의 길이를 변수 N에 할당
const N = board.length;
// 3 x 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],
];
//boxes의 [row][col]위치의 수를 리턴하는 함수 (3x3박스의 위치를 리턴하는 함수)
const getBoxNum = (row, col) => boxes[row][col];
const blanks = []; // 입력되지 않은 빈칸의 위치를 담을 배열
const rowUsed = []; //row에 어떤 숫자가 사용됬는지 여부를 담을 배열
const colUsed = []; //col에 어떤 숫자가 사용됬는지 여부를 담을 배열
const boxUsed = []; // 3 x 3 박스에 어떤 숫자가 사용됬는지 여부를 담을 배열
// rowUsed, colUsed, boxUsed 에
// board의 길이 + 1 길이
// ([0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 첫번째 인덱스는 더미)
// x board의 길이(9)의 모든 요소가 false인 배열 생성
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));
}
// blanks에
// 인자 board의 입력되지 않은칸(0)의 위치(row, col)를 담은 배열을 생성
// 사용된 숫자는 그 위치에 true 할당
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;
}
}
}
// row, col, num를 입력받아
// row, col 위치에 num이 들어갈수 있는지 boolean값으로 리턴하는 함수
const isValid = (row, col, num) => {
const box = getBoxNum(row, col);
return (
rowUsed[row][num] === false &&
colUsed[col][num] === false &&
boxUsed[box][num] === false
);
};
// row, col, num를 입력받아
// row, col 위치에 num을 넣어주고
// rowUsed, colUsed, boxUsed의 row, col 위치의 boolean값을 toggle해주는 함수
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];
};
// sudoku함수를 보조(auxiliary)해주는 aux함수
// 인자로 들어온 board의 빈칸을 채워주는 함수
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;
};