백준 12095 - 가장 오래 걸리는 스도쿠

https://www.acmicpc.net/problem/12095

 

스도쿠는 백트래킹으로 풀기 힘들다는 사실을 배우는 문제이다. 스도쿠를 결정적으로 빨리 푸려면 크누스 X 알고리즘을 사용해야 한다.

 

밑의 스택 오버플로우 링크에서 백트래킹에 의한 스도쿠 풀이가 느린 경우를 제시하니 살펴보면 좋을 것이다.

 

https://stackoverflow.com/questions/24682039/whats-the-worst-case-valid-sudoku-puzzle-for-simple-backtracking-brute-force-al

What's the worst-case valid sudoku puzzle for simple backtracking brute force algorithm?