스도쿠(일본어로 '숫자 자리'라는 뜻)는 인기있는 숫자 퍼즐입니다. 그 유래는 확실치 않지만, 비슷하면서 훨씬 더 어려운 라틴 방진(Latin Squares)이라는 퍼즐을 고안했던 레온하르트 오일러의 영향을 받았음이 분명합니다. 스도쿠는 가로 9칸, 세로 9칸으로 이루어진 표에서 각 행과 열, 그리고 작은 3x3 격자 안에 모두 1부터 9까지의 숫자가 한 번씩만 들어가도록 빈 칸을 채우는 것이 목적입니다. 아래 왼쪽 그림은 퍼즐 문제의 한 예이고, 오른쪽 그림은 그 해답입니다.

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

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

잘 만들어진 스도쿠 퍼즐은 유일한 해답을 가지며 논리적인 방법으로 해결이 가능하지만, 가끔은 선택의 경우를 줄이기 위해 "찍고 맞춰보는" 과정이 필요할 수도 있습니다 (여기에 대해서는 논란이 많습니다). 퍼즐의 난이도는 이러한 탐색과정의 복잡도에 따라 결정됩니다. 위에 나온 예제는 직접적인 추론에 의해 해결이 가능해서 쉬운 편에 속합니다.

6KB의 텍스트 파일 sudoku.txt에는 다양한 난이도의 스도쿠 퍼즐이 50개 들어 있습니다. 모든 문제의 해답은 유일합니다 (위에 나온 예제가 첫번째 문제입니다).

50개의 퍼즐을 모두 푼 다음에, 각 해답지에서 맨 왼쪽 위의 숫자 3개를 이어붙인 수를 모두 더하면 얼마가 됩니까? (위 예제의 경우 483과 같은 수를 말합니다)