[알고리즘/자바스크립트]스도쿠 판별 알고리즘 (Did I Finish my Sudoku?)

-해당 문제는 codewars사이트의 level5 문제입니다. (1~8단계 중 8단계가 가장 쉬운 레벨)-

[문제] Write a function done_or_not/DoneOrNot passing a board (list[list_lines]) as parameter. If the board is valid return 'Finished!', otherwise return 'Try again!'

Sudoku rules:

Complete the Sudoku puzzle so that each and every row, column, and region contains the numbers one through nine only once.

Rows:

There are 9 rows in a traditional Sudoku puzzle. Every row must contain the numbers 1, 2, 3, 4, 5, 6, 7, 8, and 9. There may not be any duplicate numbers in any row. In other words, there can not be any rows that are identical.

In the illustration the numbers 5, 3, 1, and 2 are the "givens". They can not be changed. The remaining numbers in black are the numbers that you fill in to complete the row.

Columns:

There are 9 columns in a traditional Sudoku puzzle. Like the Sudoku rule for rows, every column must also contain the numbers 1, 2, 3, 4, 5, 6, 7, 8, and 9. Again, there may not be any duplicate numbers in any column. Each column will be unique as a result.

In the illustration the numbers 7, 2, and 6 are the "givens". They can not be changed. You fill in the remaining numbers as shown in black to complete the column.

Regions:

A region is a 3x3 box like the one shown to the left. There are 9 regions in a traditional Sudoku puzzle.

Like the Sudoku requirements for rows and columns, every region must also contain the numbers 1, 2, 3, 4, 5, 6, 7, 8, and 9. Duplicate numbers are not permitted in any region. Each region will differ from the other regions.

In the illustration the numbers 1, 2, and 8 are the "givens". They can not be changed. Fill in the remaining numbers as shown in black to complete the region.

Valid board example:

For those who don't know the game, here are some information about rules and how to play Sudoku: http://en.wikipedia.org/wiki/Sudoku and http://www.sudokuessentials.com/

[해석] 말 그대로 스도쿠 퍼즐 답이 이중 배열로 주어졌을 때 답이 맞으면 'Finished!'란 문구를 return하고 틀리면 'Try again!'을 return하는 문제이다. 스도쿠 퍼즐은 각 행, 열이 전부 1, 2, 3, 4, 5, 6, 7, 8, 9로 이루어져 있어야 하고 중복되는 숫자가 있으면 안된다. 또한 위 그림같이 3X3 박스 영역 또한 1, 2, 3, 4, 5, 6, 7, 8, 9로 이루어져 있어야 정답이 된다.

[예시]

doneOrNot([[5, 3, 4, 6, 7, 8, 9, 1, 2], 

         [6, 7, 2, 1, 9, 5, 3, 4, 8],

 [1, 9, 8, 3, 4, 2, 5, 6, 7],

 [8, 5, 9, 7, 6, 1, 4, 2, 3],

 [4, 2, 6, 8, 5, 3, 7, 9, 1],

 [7, 1, 3, 9, 2, 4, 8, 5, 6],

 [9, 6, 1, 5, 3, 7, 2, 8, 4],

 [2, 8, 7, 4, 1, 9, 6, 3, 5],

         [3, 4, 5, 2, 8, 6, 1, 7, 9]])  => return 'Finished!'

doneOrNot([[5, 3, 4, 6, 7, 8, 9, 1, 2], 

        [6, 7, 2, 1, 9, 0, 3, 4, 9],

        [1, 0, 0, 3, 4, 2, 5, 6, 0],

        [8, 5, 9, 7, 6, 1, 0, 2, 0],

        [4, 2, 6, 8, 5, 3, 7, 9, 1],

        [7, 1, 3, 9, 2, 4, 8, 5, 6],

        [9, 0, 1, 5, 3, 7, 2, 1, 4],

        [2, 8, 7, 4, 1, 9, 6, 3, 5],

        [3, 0, 0, 4, 8, 1, 1, 7, 9]])  => return 'Try again!'

내가 생각한 풀이는 다음과 같다.

1) 먼저 배열 하나 하나를 돌면서 배열이 1~9의 숫자를 모두 가지고 있는지 판별해보기로 했다.

function doneOrNot(board){
	for(var i=0; i<board.length; i++) {
		if(! verifyNum(board[i])) return 'Try again!'
	}

	function verifyNum(arr) {
		for(var i=1; i<10; i++) {
			if(! arr.includes(i)) return false
		}
		return true
	}
}

먼저 verifyNum(arr)이란 함수를 만들었다.

파라미터로 배열을 받아서 그 배열의 요소를 돌면서 배열이 1부터 9까지의 숫자를 가지고 있는지 include함수로 판단한다.

만약 하나라도 없으면 false를 return하고 모두 가지고 있으면 true를 return한다.

그리고 이중배열 board를 받아 이중배열 안의 각각의 배열을 verifyNum으로 검사한다.

하나라도 false가 return되면 바로 'Try again!'을 return 시켜 루프를 종료하고 for문을 빠져나간다.

2) 이제 세로 열을 위와 같은 방식으로 판별해야한다.

function doneOrNot(board){
	for(var i=0; i<board.length; i++) {
		if(! verifyNum(board[i])) return 'Try again!'

		var boardCol = board.map((x, j, arr) => arr[j][i])
		if(! verifyNum(boardCol)) return 'Try again!'
	}

	function verifyNum(arr) {
		for(var i=1; i<10; i++) {
			if(! arr.includes(i)) return false
		}
		return true
	}
}

나는 map()을 사용하여 세로열의 값만 뽑아내어 배열을 다시 생성하였다.

이 배열도 생성하는 즉시 verifyNum()함수를 사용하여 1~9까지의 숫자가 모두 있는지 판별한다.

3) 마지막으로 3x3 박스를 돌아가면서 판별해야한다.

function doneOrNot(board){
	for(var i=0; i<board.length; i++) {
		if(! verifyNum(board[i])) return 'Try again!'

		var boardCol = board.map((x, j, arr) => arr[j][i])
		if(! verifyNum(boardCol)) return 'Try again!'
	}

	var boardBox = []
	var box = []
	var index = 0
	var i=0
	while(i<9) {
		for(var j=index; j<index+3; j++) {
			box.push(board[j][i])
		}
		i++
		if(box.length > 8) {
			if(! verifyNum(box)) return 'Try again!'
			boardBox.push(box)
			box = []
			if(boardBox.length%3 == 0) {
				i=0
				index+=3
				if(boardBox.length>8) return 'Finished!'
			}
		}
	}
	function verifyNum(arr) {
		for(var i=1; i<10; i++) {
			if(! arr.includes(i)) return false
		}
		return true
	}
}

이 부분에서 거의 반나절 동안 헤맸다ㅜㅜ

내가 사용한 방법은 일단 

이중배열에서 위에서부터 3개까지의 배열을 돌면서

세로 값을 box라는 배열에 저장하는데

box의 길이가 8보다 커지면 9개의 숫자가 모두 배열에 들어갔다는 뜻이므로

verifyNum으로 판별한 후 true가 return되면 

boardBox에 box배열을 넣어주고 box를 다시 빈 배열로 초기화시켜준다.

그리고 이 방법을 3번 반복하면 위에서부터 3개까지의 배열은 모두 검사가 끝나므로

이번엔 index += 3을 해줘서 3번째부터 6번째까지의 배열을 검사한다.

마지막으로는 6번째 배열~9번째 배열까지 검사하고

검사가 끝날 때까지 모두 통과하면 'Finished!'를 출력한다.