스도쿠 문제는 예전에는 꿈도 안꾼 문제였는데 도전해서 겨우 풀어냈다.
우선 로직은
0으로 입력된 자리에 들어가서 좌우방향 체크하고, 위아래 방향 체크하고, 네모난 사각형 방향 체크해서
스도쿠판에 현재 자리에 들어 갈 수 있는 후보군을 정한다.
0 3 5 4 6 9 2 7 8 7 8 2 1 0 5 6 0 9 0 6 0 2 7 8 1 3 5 3 2 1 0 4 6 8 9 7 8 0 4 9 1 3 5 0 6 5 9 6 8 2 0 4 1 3 9 1 7 6 5 2 0 8 0 6 0 3 7 0 1 9 5 2 2 5 8 3 9 4 7 6 0
예를 들어 설명하면
위의 입력에서
(1, 1)의 자리에 들어 갈 수 있는 후보군은 {1}이 되겠다.(좌우체크, 상하체크, 사각형 체크)
(2, 5)의 자리에 들어 갈 수 있는 후보군은 {3, 4}가 되겠다.
...
만약 후보군이 한 개라면 비교적 쉽게 도출 되겠지만 후보군이 여러개라면 원하는 답을 위해 많은 재귀함수를
수행 할 수도 있을 것이다.
어쨌든 재귀함수를 수행하면서 스도쿠 판에 0이 없을 때까지 값들을 채워나가면서
다 채워졌을 때 조건에 맞는 스도쿠가 완성되는 것을 판별해주면 되는데(백트래킹)
만약 0을 채워야 되는데 조건에 앞조건에 맞물린 후보군이 없을 경우,
다시 앞으로 회귀해서 다른 값을 대입해보고 또 재귀를 수행하면 되는데,
(백트래킹)
그렇게 해서 모든 배열을 다 채우면서
조건을 만족하는 답이 나왔을 때는 더 이상 백트래킹 재귀를 수행 할 수 없으므로
기존에 동작하는 재귀함수들을 다 끄면된다(전역으로 flag만들어놓고 완성되면 모든 스택의 재귀함수 다 종료시키면 된다)
그리고! 중요한 것이자 내가 계속 답을 못 냈던 이유 중에 하나가
2차원 배열에 모든 경우의 수를 구하는데 어려움이 있어서였다.
2차원 배열을 돌면서 0을 만나면 답을 자기 자신의 재귀함수를 호출하는데, 이 코딩에서 잘 못 된 점이 있었다.
2차원 배열을 순회하면서 0을 찾고 재귀를 수행한 후에 바로 break 두번 걸어서 for문을 완전히 빠져나와야 한다.
그렇지 않으면 무한 루프에 빠지게 된다.
이 개념에 대해서 부족해서 제대로 된 경우의 수를 못 구한 것이었다.
이 부분에 대해서는 따로 정리해야겠다.
