Sumdoku
면접 대비시간 제한2초메모리 제한512 MB
9x9 스도쿠 격자를 채우되 같은 3x3 블록 안에서 인접한 두 칸의 합이 10보다 작은지, 같은지, 큰지를 나타내는 부등호 제약을 만족해야 하며, 사전순으로 가장 작은 해를 출력한다.
문제
Sumdoku는 스도쿠의 변형이다. 스도쿠처럼 격자를 1부터 9까지의 숫자로 채우되, 각 숫자가 모든 행에 정확히 한 번, 모든 열에 정확히 한 번, 9개의 작은 사각형 각각에 정확히 한 번 나와야 한다. 스도쿠는 몇몇 칸의 값을 미리 고정하지만, Sumdoku는 같은 사각형 안에서 맞닿은 두 칸의 합에 조건을 건다.
두 칸 사이에 놓인 기호 <, =, >는 그 양쪽 두 값의 합이 각각 10보다 작다, 10과 같다, 10보다 크다는 뜻이다. 가로로 맞닿은 쌍이면 왼쪽과 오른쪽 값의 합이고, 세로로 맞닿은 쌍이면 위와 아래 값의 합이다. 조건은 같은 사각형 안에서 맞닿은 칸 쌍에만 붙고, 사각형 경계를 넘는 쌍에는 붙지 않는다.
아래 그림은 기호가 격자에 놓이는 방식을 보여 준다.
조건이 주어지면 격자를 채워라.
입력
첫 줄에 데이터 집합의 개수 가 주어진다 (). 데이터 집합은 서로 독립이고 똑같은 방식으로 처리한다.
데이터 집합 하나는 16줄이다. 첫 줄에는 데이터 집합 번호 가 있고, 는 1부터 까지 순서대로 증가한다. 이어지는 15줄은 문자 <, =, >로만 이루어진다.
1, 3, 5, 6, 8, 10, 11, 13, 15번째 줄은 각각 6글자이고, 순서대로 격자 1행부터 9행까지 가로로 맞닿은 칸 쌍의 조건이다. 한 줄의 6글자는 열 쌍 (1, 2), (2, 3), (4, 5), (5, 6), (7, 8), (8, 9)의 조건이다.
2, 4, 7, 9, 12, 14번째 줄은 각각 9글자이고, 순서대로 행 쌍 (1, 2), (2, 3), (4, 5), (5, 6), (7, 8), (8, 9)에서 세로로 맞닿은 칸 쌍의 조건이다. 한 줄의 9글자는 1열부터 9열까지의 조건이다.
모든 데이터 집합에는 조건을 만족하는 격자가 적어도 하나 있다.
출력
데이터 집합마다 10줄을 출력한다. 첫 줄에는 데이터 집합 번호 를 출력하고, 이어지는 9줄에는 격자의 각 행을 출력한다. 그 9줄 중 번째 줄의 번째 수는 행 열의 값이고, 한 줄의 아홉 수는 공백 한 칸으로 구분한다.
조건을 만족하는 격자가 여럿이면, 81개의 값을 1행 1열부터 행 우선 순서로 읽었을 때 사전순으로 가장 앞서는 격자를 출력한다.