Sudoku
in Coding Test on Coding Test
Back tracking을 이용한 스도쿠 문제풀이
Problem
가로 9칸, 세로 9칸으로 이루어져 있는 표에 1부터 9까지의 숫자를 가로줄, 세로줄, 3X3 칸에 중복되지 않게 한 번씩만 넣으면 해결
- 주의사항 : 숫자가 입력되지 않은 칸은 편의상 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],
];
*/
유효한지 (스도쿠 해결이 가능한 지) 판별하여 불가능하면 false를 반환, 가능하면 해결된 보드를 반환하도록 작성.
Solution
// file:'Sudoku.js'
// 메인이 되는 solve 함수 작성
function solve(board) {
// 다 해결됐다면 현재 보드를 리턴
if (solved(board)) {
return board
} else {
// 빈 자리 한 곳에 숫자 1..9를 각각 채운 9개의 보드를 담는다.
const possibilities = nextBoards(board)
// 그 중 가로,세로,박스 중복 검사로 유효한 보드만 남긴다.
const validBoards = keepOnlyValid(possibilities)
// 백트래킹 함수를 호출하고 이 과정을 반복한다.
return searchForSolution(validBoards)
}
}
// 해결이 안되었다면 백트래킹
function searchForSolution(boards) {
// 빈 자리에 1..9를 모두 채워봤음에도 유효한 보드가 없다면 해결이 불가능한
// 보드임으로 false를 반환한다.
if (boards.length < 1) {
return false
} else {
let first = boards.shift()
// 각 빈자리마다 1..9를 채우고 유효한 보드만 남긴다.
const tryPath = solve(first)
if (tryPath != false) {
return tryPath
// 빈 자리를 채워가다 유효하지 않게 되면 (백트래킹 해야 할 시점)
// solve(first)는 false를 반환하고,
// 더 이상 유효하지 않은 보드를 제외한 나머지(shift된 board)로 다시 탐색을
// 시작한다.
} else {
return searchForSolution(boards)
}
}
}
// 해결된(모든 칸이 채워진) 스도쿠인지 검사
function solved(board){
for (let i = 0; i < 9; i++){
for (let j = 0; j < 9; j++){
if (board[i][j] == 0){
return false
}
}
}
return true
}
// 첫 번째 빈 자리를 찾고 해당 자리를 숫자 1...9로 채우는 9개의 다른 보드를 생성
function nextBoards(board){
let res = []
const firstEmpty = findEmptySquare(board)
if (firstEmpty != undefined){
const y = firstEmpty[0]
const x = firstEmpty[1]
for (let i = 1; i <= 9; i++){
let newBoard = [...board]
let row = [...newBoard[y]] // 찾은 빈 자리가 있는 행
row[x] = i // 빈 자리(row[x])에 1..9를 넣어보기
newBoard[y] = row // 빈 자리에 1..9를 넣은 행을 다시 보드에 넣기
res.push(newBoard) // 빈 자리에 1..9를 넣은 행을 넣은 보드를
// res에 다시 담기. (3차원 배열)
}
}
return res
}
// 첫 번째 빈 자리에 대한 i(y) j(x) 좌표 가져오기)
function findEmptySquare(board){
for (let i = 0; i < 9; i++){
for (let j = 0; j < 9; j++){
if (board[i][j] == 0) {
return [i, j]
}
}
}
}
// 목록에서 유효한 보드만 담고 잘못된 보드를 모두 필터링.
function keepOnlyValid(boards){
let res = []
for (let i = 0; i < boards.length; i++){
if (validBoard(boards[i])){
res.push(boards[i])
}
}
return res
}
// 주어진 보드가 유효한지 확인
function validBoard(board){
return rowsCheck(board) && columnsCheck(board) && boxesCheck(board)
}
// 각 행(가로줄)에 반복되는 숫자가 없는지 검사
function rowsCheck(board){
for (let i = 0; i < 9; i++){
let cur = []
for (let j = 0; j < 9; j++){
if (cur.includes(board[i][j])){
return false
}
else if (board[i][j] != 0){
cur.push(board[i][j])
}
}
}
return true
}
// 각 열(세로줄)에 반복되는 숫자가 없는지 검사
function columnsCheck(board){
for (let i = 0; i < 9; i++){
let cur = []
for (let j = 0; j < 9; j++){
if (cur.includes(board[j][i])){
return false
}
else if (board[j][i] != 0){
cur.push(board[j][i])
}
}
}
return true
}
// 각 박스(3x3)에 반복되는 숫자가 없는지 검사
function boxesCheck(board){
const boxCoordinates = [[0, 0], [0, 1], [0, 2],
[1, 0], [1, 1], [1, 2],
[2, 0], [2, 1], [2, 2]]
for (let y = 0; y < 9; y += 3){
for (let x = 0; x < 9; x += 3){
// 순회는 각 상자를 검사해야 한다.
let cur = []
for (let i = 0; i < 9; i++){
let coordinates = [...boxCoordinates[i]]
coordinates[0] += y
coordinates[1] += x
if (cur.includes(board[coordinates[0]][coordinates[1]])){
return false
}
else if (board[coordinates[0]][coordinates[1]] != 0){
cur.push(board[coordinates[0]][coordinates[1]])
}
}
}
}
return true
}