6010 : 백트래킹 — 스도쿠
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
빈칸이 포함된 $9 \times 9$ 크기의 스도쿠 판이 주어집니다. 빈칸을 채워 완성된 유효한 스도쿠 판을 구하십시오.
스도쿠 규칙:
1. 각각의 가로줄과 세로줄에는 $1$부터 $9$까지의 숫자가 중복 없이 한 번씩만 들어갑니다.
2. $3 \times 3$ 크기의 소구역(박스)에도 $1$부터 $9$까지의 숫자가 중복 없이 한 번씩만 들어갑니다.
백트래킹을 사용하여 빈칸(0으로 주어진 셀)에 가능한 숫자를 하나씩 채워보며, 조건에 어긋나면 즉시 이전 단계로 되돌아가는 방식으로 문제를 해결하십시오.
[제약 조건]
• 입력은 $9 \times 9$ 스도쿠 격자이며, 빈칸은 0으로 표시됩니다.
• 항상 유일한 해가 존재합니다.
스도쿠 규칙:
1. 각각의 가로줄과 세로줄에는 $1$부터 $9$까지의 숫자가 중복 없이 한 번씩만 들어갑니다.
2. $3 \times 3$ 크기의 소구역(박스)에도 $1$부터 $9$까지의 숫자가 중복 없이 한 번씩만 들어갑니다.
백트래킹을 사용하여 빈칸(0으로 주어진 셀)에 가능한 숫자를 하나씩 채워보며, 조건에 어긋나면 즉시 이전 단계로 되돌아가는 방식으로 문제를 해결하십시오.
[제약 조건]
• 입력은 $9 \times 9$ 스도쿠 격자이며, 빈칸은 0으로 표시됩니다.
• 항상 유일한 해가 존재합니다.
입력 설명
$9$개의 줄에 걸쳐 각 줄에 $9$개의 정수가 공백으로 구분되어 주어집니다. (0은 빈칸을 나타내며, 1부터 9까지의 정수가 주어집니다)
출력 설명
완성된 $9 \times 9$ 크기의 스도쿠 판을 $9$개의 줄에 걸쳐 공백으로 구분하여 출력합니다.
답이 여러 개인 경우 그중 하나만 출력합니다. (항상 완성 가능한 스도쿠 판만 입력으로 주어집니다)
답이 여러 개인 경우 그중 하나만 출력합니다. (항상 완성 가능한 스도쿠 판만 입력으로 주어집니다)
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 3 0 0 7 0 0 0 0
6 0 0 1 9 5 0 0 0
0 9 8 0 0 0 0 6 0
8 0 0 0 6 0 0 0 3
4 0 0 8 0 3 0 0 1
7 0 0 0 2 0 0 0 6
0 6 0 0 0 0 2 8 0
0 0 0 4 1 9 0 0 5
0 0 0 0 8 0 0 7 9
출력 예시
COPY
복사되었습니다!
복사되었습니다!
5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9도움
빈칸의 좌표들을 리스트에 수집하고, 첫 번째 빈칸부터 시작하여 1~9 중 유효한 숫자를 차례대로 넣어보고 다음 빈칸으로 재귀 호출합니다. 실패하면 0으로 원복하고 백트래킹합니다.