시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 80 4 3 25.000%

문제

  스도쿠는 18세기 스위스 수학자가 만든 ‘라틴 사각형’이란 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이루어진다. 왼쪽 위 칸은 (1, 1), 오른쪽 아래 칸은 (9, 9)로 생각한다.

  이 판에 수를 채우는 규칙은 다음과 같다.

  (1) 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
  (2) 굵은 선으로 구분되어 있는 3×3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

  예를 들어 아래와 같은 경우, 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 빈칸에는 1이 들어가야 한다.

  또한 다음과 같은 3×3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여 있으므로 가운데 빈 칸에는 3이 들어가야 한다.

  이와 같이 81개의 칸을 차례로 채워 나가면 조건을 만족시키도록 퍼즐을 풀 수 있다. 하지만 숫자를 채워 나가는 도중에 실수가 있었다면 퍼즐을 완성하지 못하게 될 수도 있다. 예를 들어 29개의 칸을 채운 후 스도쿠 판이 다음과 같았다고 하자.

 

    만일 30번째로 수 5를 (4, 6) 칸에 넣는다면, 현재 단계에서는 규칙에 위배되지 않지만 나머지 51개의 수를 어떻게 채워 넣는다고 해도 이 퍼즐은 풀 수 없는 퍼즐이 된다. 이처럼 가장 먼저 실수한 단계의 번호를 구하는 프로그램을 작성하시오.

입력

  81개의 줄에 걸쳐 각 단계에서 숫자를 채울 칸의 좌표를 나타내는 두 정수와 그 칸에 적을 숫자가 빈 칸을 사이에 두고 순서대로 주어진다. 입력되는 모든 숫자는 1 이상 9 이하의 자연수이다.

출력

  첫 줄에 가장 먼저 실수한 단계가 몇 번째인지 출력한다. 만일 실수한 곳이 없다면 -1을 출력한다.

예제 입력

1 1 5
1 3 3
1 4 7
1 7 1
2 3 2
2 4 8
2 5 6
3 2 6
3 8 2
3 9 5
7 1 9
7 2 4
7 8 5
8 1 7
8 5 9
8 6 6
8 7 4
9 3 1
9 6 4
9 7 9
4 3 9
4 8 1
4 9 3
6 2 1
6 4 3
6 5 2
6 7 7
6 8 9
6 9 4
4 6 5
1 2 8
2 1 1
2 2 9
3 1 4
3 3 7
7 3 6
8 2 5
8 3 8
9 1 2
9 2 3
1 8 6
1 9 9
2 7 3
2 8 4
2 9 7
3 7 8
7 7 2
7 9 8
8 8 3
8 9 1
9 8 7
9 9 6
5 1 3
5 2 7
5 3 4
6 1 6
6 3 5
5 7 5
5 8 8
5 9 2
3 4 9
4 4 4
5 4 6
7 4 1
8 4 2
9 4 5
4 1 8
4 2 2
4 7 6
1 5 4
1 6 2
3 5 3
3 6 1
5 5 1
5 6 9
6 6 8
7 6 3
9 5 8
4 5 7
2 6 7
7 5 5

예제 출력

30

힌트

출처