#10615. 新数独

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Turing001

题目描述

下面是一个没有数字,只有大小关系(没错,那些尖角都是“大于符号”)!的数独:

除了大小关系外(注意相邻格子不能相同),还需要满足通常的数独规则:

  • 每个格子都是 1\sim 9 的数字
  • 每行都是 1 \sim 9 的排列
  • 每列都是 1 \sim 9 的排列
  • 每个 3\times 3 的子矩阵(上图中用粗线隔开,一共有 3\times 3 个这样的子矩阵)都是 1\sim 9 的排列

为了美观,每个 3\times 3 子矩阵的所有 12 相邻格子的大小关系都将给出。

输入格式

一共 15 行,包含一个新数独的实例。第 1,3,5,6,8,10,11,13,15 行包含左右方向的符号(< 和 >),其余行包含上下方向的符号(^ 和 v)

输出格式

包含 9 行,每行 9 1\sim 9 的数字,以空格隔开。输入保证唯一解。

样例

样例输入 #1

< > > < > < 
v v ^ ^ v v ^ ^ ^
< < > < > < 
^ ^ ^ v ^ ^ ^ v v
< < < < > > 
> < > > > > 
v ^ ^ ^ ^ v v v ^
> > > > < > 
v v ^ v ^ v ^ v ^
> < < > > > 
< < < < > < 
v ^ v v v v ^ ^ v
< > > < < > 
^ v v v ^ v ^ v v
< > < > < >

样例输出 #1

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

数据范围与提示

P4573 [CQOI2013]