개발 기록 : 가볍게 스도쿠 퍼즐을 생성하고 게임을 만드려고 했으나
스도쿠 규칙에 맞게 숫자를 생성하는 것이 생각보다 복잡하고 정적 페이지라는 제한으로 한계를 느꼈다.
1. Math.floor(Math.random() * 9) + 1 을 사용하여 1~9 까지의 수를 임의로 생성하고 정수[9][9] 배열에 차례로 넣으면서 전체 81 개 숫자 생성
2. 각 숫자 셀(Cell)의 행, 열, 박스의 위치를 계산하여 useState 또는 로컬 스토리지를 사용, 숫자의 데이터를 그룹별로 저장
3. 저장된 데이터를 사용하여 차례대로 중복된 숫자를 제거하고 새로운 숫자를 배치하여 스도쿠 퍼즐 완성
본래는 이렇게 간단하게 구현이 될 거라 생각했지만 다음과 같은 문제가 생겼다.
1. 스도쿠 셀이 채워질 수록 반복해서 체크해야하는 행,렬,박스 데이터가 많아진다. => 불필요하고 중복된 작업 계속해서 증가
2. 이전에 배치된 숫자가 어떻게 되는지에 따라 이후 숫자 배치가 불가능해지는 경우의 수가 많다. => 무한 루프에 갇힘
이를 해결하기 위해 아예 스도쿠 풀이 알고리즘을 공부하기로 결정하였다. 이를 위해 고려한 생각들은 이렇다.
1. 숫자가 정해지면 같은 그룹의 행, 열, 박스에 영향을 미친다. 따라서 이전 숫자들의 정보를 작업 중인 프로세스가 알고 있어야 한다.
2. 이전에 배치된 숫자들에 의해 불가능한 경우의 수가 생기므로 스도쿠 규칙에 대한 수학적 지식을 공부하여 구조적인 해결책을 찾아야 한다.
3. 1 과 2 를 고려하면 스도쿠 보드를 이진 트리와 같은 데이터 구조로 변환하여 저장 위치 자체로 행, 열, 박스를 나타내고 빠르게 탐색, 수정이 가능하도록 한다.
4. 노드를 사용하여 이전 숫자들의 상태를 저장하고 자식 노드에 이를 전파한다.
5. 알고리즘은 전체가 자바스크립트를 통해 한꺼번에 정적 페이지에 담겨야 한다.
이러한 생각들을 기초로 스도쿠 알고리즘에 대한 탐색을 시작하였다. 그리고 이미 깊이있는 연구들이 많이 이루어졌다는 것을 알게 되었다.
1. 스도쿠 문제는 NP-완전 문제라고 한다. 또한 규칙을 수학적 성질로 변환시키면 유명한 수학적 난제인 색깔 칠하기 문제와 동일해진다.
=> 사실 NP-완전 에 대한 정의를 이해하지 못하였다. 그러나 스도쿠 보드 구조가 수학적인 그래프로 변환 가능하다는 것을 알았다.
2. 스도쿠 풀이 알고리즘의 종류가 매우 많다.
=> 초기에는 스도쿠 풀이 방법을 몇가지 규칙으로 정한 후 이를 차례대로 대입하여 문제를 풀이하는 알고리즘이 많이 개발되었다.
그러나 대부분 케이스 제한적인 해결법을 가진 2 ~ 3 종류의 알고리즘을 실행시키고 결과를 비교하여 판단하는 방법들이었다.
따라서 유일한 정답이 있는 경우에만 해답을 반환한다던지 아니면 풀이마다 해답이 달라진다던지 하는 문제가 생기는 것으로 보였다.
그러다가 점점 스도쿠에 대한 수학적 연구가 이루어지면서 이미 존재하는 수학 난해 알고리즘을 적용시키는 방법들이 생겨났다.
그 결과 스도쿠 문제를 완전 피복 문제로 변환하고 이를 해결하는데 욕심쟁이 알고리즘과 이진 트리 구조를 사용하여
가능한 모든 경우의 수를 분기별로 나누고 각 분기를 깊이 우선으로 탐색, 해답이 없을 시 현재 분기를 파기하고 다음 분기로 넘어가는
알고리즘이 개발되었다는 것을 알게 되었다. 이를 밴치마킹하여 자바스크립트로 바꾸어 작성한 후 잘 작동하는지 확인해 보았다.
아래는 puzzle = [
0, 8, 0, 0, 0, 0, 0, 0, 0,
0, 6, 0, 0, 0, 5, 3, 0, 0,
0, 0, 0, 0, 9, 0, 5, 6, 0,
0, 0, 0, 0, 0, 0, 8, 0, 2,
0, 0, 0, 0, 0, 0, 0, 4, 0,
3, 0, 7, 0, 2, 0, 0, 0, 0,
0, 0, 5, 0, 6, 0, 9, 8, 0,
7, 0, 0, 4, 0, 0, 0, 0, 3,
0, 4, 0, 0, 0, 1, 0, 0, 0
] 의 예제를 넣고 실행한 결과이다.