1840번 - 스도쿠
그런데 이 문제, 풀 수 있는것 맞나요? 일단 단순한 Gold 1 백트랙킹으로는 절대 못풀어야 할 것 같은데, 대다수의 분들이 이렇게 푼 것 같습니다.
왜냐하면 "못 푸는 스도쿠"임을 찾는 것이 상당히 오래 걸리기 때문입니다.
아래의 반례는 다음과 같습니다. (제 코드를 포함해 거의 다수의 코드에서 시간 초과가 날 겁니다)
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
3 4 5 6 7 8 9 1 2
6 7 8 9 1 2 3 4 5
1 9 2 3 4 5 6 7 8
5 6 7 8 9 1 2 3 4
8 9 1 2 3 4 5 6 7
2 3 4 5 6 7 8 9 1
우선 당연히 틀린 스도쿠 입니다.
채운 순서를 보면 (1,1), (4,8)과 (5,5)에 1을 채웁니다.
그리고 왼쪽 중간 박스에 (6,3), (6,2)에 수를 채움으로써 왼쪽 중간 박스에는 '1'이 들어갈 자리가 없습니다.
따라서 정답은 '6'이 되야 합니다.
재채점했습니다.
댓글을 작성하려면 로그인해야 합니다.
amel 4년 전 5
그런데 이 문제, 풀 수 있는것 맞나요? 일단 단순한 Gold 1 백트랙킹으로는 절대 못풀어야 할 것 같은데, 대다수의 분들이 이렇게 푼 것 같습니다.
왜냐하면 "못 푸는 스도쿠"임을 찾는 것이 상당히 오래 걸리기 때문입니다.
아래의 반례는 다음과 같습니다. (제 코드를 포함해 거의 다수의 코드에서 시간 초과가 날 겁니다)
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
3 4 5 6 7 8 9 1 2
6 7 8 9 1 2 3 4 5
1 9 2 3 4 5 6 7 8
5 6 7 8 9 1 2 3 4
8 9 1 2 3 4 5 6 7
2 3 4 5 6 7 8 9 1
우선 당연히 틀린 스도쿠 입니다.
채운 순서를 보면 (1,1), (4,8)과 (5,5)에 1을 채웁니다.
그리고 왼쪽 중간 박스에 (6,3), (6,2)에 수를 채움으로써 왼쪽 중간 박스에는 '1'이 들어갈 자리가 없습니다.
따라서 정답은 '6'이 되야 합니다.