Sudoku problem(9x9) solved using Backtracking Algorithm

이번 post에서는 sudoku problem(9x9)을 Backtracking Algorithm을 통해 푸는 방법에 대해서 post하겠습니다.

Wikipedia에서 Backtracking Algorithm이 어떤 방식으로 진행되는지 나와있습니다. (Description of method)

The backtracking algorithm enumerates a set of partial candidates that, in principle, could be completed in various ways to give all the possible solutions to the given problem. The completion is done incrementally, by a sequence of candidate extension steps.

The backtracking algorithm traverses this search tree recursively, from the root down, in depth-first order. At each node c, the algorithm checks whether c can be completed to a valid solution. If it cannot, the whole sub-tree rooted at c is skipped (pruned). Otherwise, the algorithm (1) checks whether c itself is a valid solution, and if so reports it to the user; and (2) recursively enumerates all sub-trees of c. The two tests and the children of each node are defined by user-given procedures.

Therefore, the actual search tree that is traversed by the algorithm is only a part of the potential tree. The total cost of the algorithm is the number of nodes of the actual tree times the cost of obtaining and processing each node. This fact should be considered when choosing the potential search tree and implementing the pruning test.

중요한 문장들로만 정리하자면, backtrace method는

1. The backtracking algorithm traverses the search tree recursively, from the root down, in depth-first order. (root step)
2. If a node c is an invalid solution, the whole subtree rooted at c is skipped(pruned). (reject step)
3. If a node c is a valid and complete solution,  reports results to the user. (accept and output step)
4. If a node c is a valid and incomplete solution, enumerates children of the tree. (candidate extension steps / first and next step)

accept step에 관해서는 Wikipedia에서 다음과 같이 설명한다.
It may assume that the partial candidate c and all its ancestors in the tree have passed the reject test.
여기서 각 step은 Wikipedia에서 pseudocode로 설명하는 step을 따왔습니다.

본격적으로 sudoku를 풀기 위해서 두 슬라이드를 가져왔습니다.
밑의 두 슬라이드는 see.standford.edu에서 CS106B의 Lecture 11의 일부분을 캡쳐한 것입니다.

위에서 설명한 backtracking의 방법대로 sudoku problem을 해결하는 C코드를 다음과 같이 작성하였습니다.


- Reference

1. Wikipedia: https://en.wikipedia.org/wiki/Backtracking
2. Slides: https://see.stanford.edu/materials/icspacs106b/Lecture11.pdf in https://see.stanford.edu/Course/CS106b