문제
스도쿠(sudoku) 는 9x9 로 이뤄진 퍼즐에 1 부터 9 까지 숫자를 입력하는 게임이다. 조건은 가로줄과 세로줄 그리고 각 9칸의 숫자 중 중복이 있어서는 안된다. 일부 비어있는 칸의 배열을 입력받아 스도쿠를 완성하라.
풀이
스도쿠에서 찾아야 하는 숫자는 크게 3개의 조건을 가지고 있다. 먼저 3가지 조건을 비교할 수 있는 2차원 배열을 생성한다. 숫자를 찾는 로직은 유효성 검사 함수와 토글 함수를 사용해서 1부터 9까지 순회하면서 가능한 모든 경우의 수를 비교한다.
만약 숫자를 찾는 과정에서 진행이 불가능한 경우(중복 숫자가 발견되는 경우) 토글 함수를 호출해서 이전상태로 백트래킹을 하면서 새로운 숫자를 찾는 과정을 반복한다.
① 조건 필터 2차원 배열 생성
숫자가 포함된 3x3 박스내에 중복값이 존재해서는 안된다. 박스 내 중복값을 확인하기 위해서 박스의 위치를 임의로 표시한 2차원 배열을 생성한다. 좌표값을 통해 박스의 위치를 확인할 수 있는 getBoxNum 함수를 생성한다.
// 박스의 위치를 특정함
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];
가로줄, 세로줄, 박스의 중복값을 확인하기 위한 boolean 값을 담은 2차원 배열을 생성한다.
const N = board.length;
const rowUsed = [];
const colUsed = [];
const boxUsed = [];
// rowUsed, colUsed, boxUsed 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));
}
입력값으로 주어진 2차원 배열을 순회하면서 비어있는 위치를 확인한다. 만약 비어있는 경우 blanks 배열에 좌표값을 추가하고, 0이 아닌 경우 가로줄, 세로줄, 박스의 해당 위치를 true로 반전시킨다.
const blanks = [];
// 입력 배열 순회
for (let row = 0; row < N; row++) {
for (let col = 0; col < N; col++) {
// 0인 경우 blanks 추가
// 모든 sudoku 배열이 완성되면 길이 0으로 전환됨
if (board[row][col] === 0) {
blanks.push([row, col]);
}
// 0이 아닌 경우 rowUsed, colUsed, boxUsed visit check
else {
const num = board[row][col];
const box = getBoxNum(row, col);
rowUsed[row][num] = true;
colUsed[col][num] = true;
boxUsed[box][num] = true;
}
}
}
② 유효성 검사 함수
유효성 검사 함수를 생성한다. 인자로 좌표값과 숫자를 입력받아 해당 좌표에 입력가능한 숫자인지 boolean 값을 반환하는 함수다. 가로줄, 세로줄, 박스 내 중복값이 존재하는 경우 false를 반환한다.
// 유효성 검사 함수
// 방문하지 않고, 사용하지 않은 수인 경우 true
// 즉 sudoku에서 사용 가능한 숫자이면 true
const isValid = (row, col, num) => {
const box = getBoxNum(row, col);
return (
rowUsed[row][num] === false &&
colUsed[col][num] === false &&
boxUsed[box][num] === false
);
};
③ 토글 함수 생성
토글 함수를 생성한다. 입력값으로 받은 2차원 배열의 값을 변경한 후 가로줄, 세로줄, 박스의 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];
};
④ DFS 알고리즘
DFS 알고리즘을 사용해서 리프 노드까지 가장 빠른 시간안에 도달한다. blanks의 인자를 순회하는 재귀함수다. 1부터 9까지 숫자를 입력하면서 유효성 검사를 통과하는 경우 toggleNum() 함수를 호출하여 스도쿠 숫자를 입력하고 다음 재귀 함수를 호출한다.
만약 끝까지 스도쿠 숫자를 찾는데 성공하면 바로 종료되겠지만, 숫자를 입력하는 과정에서 가로줄, 세로줄, 박스값 조건을 충족하지 못하고 false를 반환하는 경우가 발생한다. 이 때는 toggleNum() 함수를 한번더 호출하여 이전 상태값으로 돌린 후 다시 새로운 숫자를 찾는 과정을 반복한다.
// sudoku 재귀함수
const recur = (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 (recur(idx + 1, blanks, board) === true) {
return true;
}
toggleNum(row, col, num);
}
}
return false;
};
최종 소스
function sudoku(board) {
let count = 0;
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 = [];
// rowUsed, colUsed, boxUsed 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));
}
// 입력 배열 순회
for (let row = 0; row < N; row++) {
for (let col = 0; col < N; col++) {
// 0인 경우 blanks 추가
// 모든 sudoku 배열이 완성되면 길이 0으로 전환됨
if (board[row][col] === 0) {
blanks.push([row, col]);
}
// 0이 아닌 경우 rowUsed, colUsed, boxUsed visit check
else {
const num = board[row][col];
const box = getBoxNum(row, col);
rowUsed[row][num] = true;
colUsed[col][num] = true;
boxUsed[box][num] = true;
}
}
}
// 유효성 검사 함수
// 방문하지 않고, 사용하지 않은 수인 경우 true
// 즉 sudoku에서 사용 가능한 숫자이면 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];
};
// sudoku 재귀함수
const recur = (idx, blanks, board) => {
count++;
//재귀 탈출 조건
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 (recur(idx + 1, blanks, board) === true) {
return true;
}
toggleNum(row, col, num);
}
}
return false;
};
recur(0, blanks, board);
console.log(count);
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 board_hard=[
[0, 4, 0, 0, 6, 0, 0, 2, 0],
[0, 0, 0, 0, 8, 0, 0, 0, 0],
[9, 6, 0, 0, 4, 0, 0, 8, 7],
[3, 9, 0, 8, 0, 7, 0, 4, 1],
[0, 0, 0, 0, 9, 0, 0, 0, 0],
[8, 0, 0, 3, 0, 6, 0, 0, 2],
[7, 0, 0, 0, 0, 0, 0, 0, 9],
[0, 0, 5, 0, 0, 0, 3, 0, 0],
[6, 0, 0, 1, 0, 5, 0, 0, 4],
]
let output = sudoku(board_hard);
console.log(output);
성능 테스트
생각보다 성능이 괜찮다. 리눅스에서 제공하는 스도쿠 문제를 풀어보니 가장 어려운 단계 문제를 푸는데 재귀 함수 호출이 1302번 수행되었다. 꽤 괜찮은 성능이다. 쉬운 난이도로 했을 때 54번 호출만에 전체 답을 풀 수 있었다. DFS 알고리즘으로 가장 먼저 리프 노드에 도착하는 알고리즘이 가장 효율적으로 보인다.
다른 알고리즘 로직
처음 문제를 접하고 풀어갔던 로직이다. 특정 숫자를 찾아야 하는 반복적인 작업에서 DFS 혹은 BFS 알고리즘을 사용해서 유효성 검사, 토글 함수를 구현하는 것이 소스코드를 해석하고 구현하는데 더욱 명시적이다.
function sudoku(board) {
// TODO: 여기에 코드를 작성합니다.
/* 풀이과정 */
/*
1. 0인 지점을 순회한다.
2. 0인 경우 가로 세로 현재 3x3 위치에 0이 아닌 숫자를 모두 가져온다.
3. 1~9까지 겹치지 않는 available 배열을 만든다.
4. 만약 available이 1개만 존재하는 경우 현재 0을 available로 변경
5. 모든 숫자가 0이 아닌 지점이 될때 까지 무한 반복
*/
const numberArr = [1,2,3,4,5,6,7,8,9];
let count = true;
while(count){
count = false;
for(let i=0; i<board.length; i++){
for(let j=0; j<board[i].length; j++){
let available_row = [];
let available_col = [];
let available_matrix = [];
let current_loc = [];
let available_final = [];
if(board[i][j] === 0){
count = count || true;
// 가로 줄 확인
available_row = numberArr.filter((item)=>!board[i].includes(item))
// 세로 줄 확인
for(let key of board){
available_col = numberArr.filter((item)=>item!==key[j]);
}
// 3x3 매트릭스 확인
current_loc = [Math.floor((i+1)/3), Math.floor((j+1)/3)];
for(let ii = current_loc[0]*3 ; ii<current_loc[0]*3+3; ii++){
for(let jj= current_loc[1]*3; jj<current_loc[1]*3+3; jj++){
available_matrix.push(board[ii][jj])
}
}
available_matrix = numberArr.filter((item=>!available_matrix.includes(item)))
available_final = [...available_col, ...available_row, ...available_matrix]
if(available_final.length === 1)
board[i][j] = available_final.shift();
}
}
}
}
// const temp = [6, 8, 0, 0, 7, 0, 0, 9, 0];
// console.log(numberArr.filter((item)=>!temp.includes(item)));
return board;
};
[Algorithm] 동적 계획법 타일링 알고리즘 문제 Javascript
동적 계획법(Dynamic Programming) 동적 계획법은 어떤 문제를 해결하기 위해 그 문제를 더 작은 문제의 연장선으로 생각한다. 가장 하위의 케이스의 해를 구하고 큰 문제의 해를 구해나가는 Bottom-up
about-tech.tistory.com
'Algorithm' 카테고리의 다른 글
| [Algorithm] 분할정복 거듭제곱 분할제곱 알고리즘 Javascript (0) | 2022.06.02 |
|---|---|
| [Algorithm] DFS Tree 순회 알고리즘 (0) | 2022.05.30 |
| [Algorithm] 동적 계획법 타일링 알고리즘 문제 Javascript (0) | 2022.05.26 |
| [Algorithm] 바코드 문제 DFS 알고리즘 기초 Javascript (0) | 2022.05.25 |
| [Algorithm] Advanced Bubble Sort 알고리즘 Javascript (0) | 2022.05.25 |
댓글