스도미노 쿠

거의 1달만에 다시 글을 쓰네요, (연말, 연초라 문제풀이는 계속 했는데 블로그에 글 쓸 시간이 없어서 밀린게 20개는 되는거 같아요 ㅠㅠ)
벌써 1월 말이 다되었지만 새해복 많이 받으세요!!! 미뤄뒀던 블로그 포스팅도 다시한번 열심히 올려보도록 하겠습니다.

문제 요약

1. 게임 규칙은 유명한 스도쿠 게임처럼, 가로, 세로, 3 x 3 정사각형 내에 같은 숫자가 오면 안된다.
   | | | | | | | |
   |—|—|—| |—|—|—|
   | 1 | 2 | 3 | | 1 | 2 | 3 |
   | 4 | 5 | 6 | | 4 | 3 | 6 |
   | 7 | 8 | 9 | | 7 | 8 | 9 | <옳바른 배치=""> <유효하지 못한="" 배치="">

2. 기존 스도쿠와 달리 총 81개의 칸중 9개의 칸이 채워져 있고, 2개의 숫자가 적힌 도미노 36개를 이용하여 나머지 72개의 칸을 채워야 한다.

3. 도미노는 (1, 2), (1, 3), (1, 4) … (9, 7), (9, 8)로 구성된다.

4. 36개의 도미노중 일부는 칸을 채우는데 사용되었을 수 있다.

원본 문제 보러가기

접근법

36개의 도미노중 어떤 도미노가 사용되었고 어떤 도미노를 사용할 수 있는지 먼저 계산한다. 이후 스도쿠 빈칸에 사용할 수 있는 도미노를 전부 놓아 보는 완전탐색법을 이용하여 스도쿠를 채워나가면 쉽게 문제를 풀 수 있다.

단순히 완전 탐색법을 사용해서 문제를 풀기에는 경우의 수가 너무 많고 (도미노는 회전도 할 수 있다… 도미노 1개당 4개의 경우의 수가 생기는것) 이렇게 많은 경우의 수를 완전 탐색법으로 풀려고 하면 99.9% 시간초과가 나는 것을 확인할 수 있을 것이다. 따라서 이 문제를 풀기 위해서는 완전 탐색법 이외에도 백트래킹이라는 방법을 사용해야 한다.

백트래킹이란 모든 경우의 수를 찾아보는 것이 아니라, 현재 상태가 문제에서 제시하는 조건을 만족할 때만 다음 조건을 찾는 방법이라고 생각할 수 있다. 이번 문제에서 제시된 조건은 “가로, 세로 3 x 3 정사각형에 같은 숫자가 들어가서는 안된다” 이다. 만약 위와 같은 스도쿠판에서, C1, C2칸에 (4, 5) 도미노를 놓고자 한다면 (4, 5), (5, 4) 2가지 경우의 수를 생각해볼 수 있다. 그러나 (4, 5)의 순서로 도미노를 놓게 되면 F1에 이미 4라는 숫자가 있기 때문에 세로에 같은 숫자가 2번 등장하게 된다. 이는 문제에서 제시한 조건을 만족시킬 수 없다. 따라서 (4, 5)를 넣는 경우 아무리 다음 도미노들을 잘 놓는다고 해도 답이 될 수 없을 것이다. 이런 경우, (4, 5)는 고려하지 않고 (5, 4)만 다음 경우를 생각하므로써 경우의 수를 많이 줄일 수 있다. 이 문제에서도 이런 방법을 적용하면 시간초과 없이 문제를 풀수 있다.

Source Code

소스코드 보러가기

• 아직 주석이 달려있지 않습니다.
• pseudocode 보다는 python 코드를 올릴 예정입니다.
• Code Review는 언제나 환영합니다 (코드를 더 깔끔하게, 효율적으로 만드는걸 도와주세요!)