数独是源自18世纪瑞士的一种数学游戏。玩家需要根据 9×9 盘面上的已知数字,推理出所有剩余空格的数字,并满足每一行、每一列、每一个粗线宫 3×3 内的数字均含 1∼9,不重复。数独盘面是个九宫,每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件,利用逻辑和推理,在其他的空格上填入 1∼9 的数字,使 1∼9 每个数字在每一行、每一列和每一宫中都出现且只出现一次,所以又称“九宫格”。
小 T 正在玩数独游戏。小 T 好不容易填完了一个数独,但他实在太粗心了,在 9×9 的盘面上居然有一个小格的数字是错误的!
聪明的你,能帮助小 T 纠正那个被填错的数字吗?
输入数据共 9 行,每行 9 个用空格隔开的正整数,表示小 T 填写的数独方阵。
保证有且仅有一个位置的数字是错误的,且纠正这个数字后可以形成一个合法的数独方阵。
输出一行 3 个用空格隔开的正整数 row,col,num,表示错误数字的行号、列号以及纠正后的数字。
输入样例 1:
5 9 4 3 1 8 7 2 6
1 3 8 2 6 7 9 4 5
6 2 7 5 4 8 3 1 8
7 6 1 9 3 2 5 8 4
4 5 2 7 8 6 1 9 3
9 8 3 4 5 1 2 6 7
2 7 5 8 9 4 6 3 1
8 1 9 6 7 3 4 5 2
3 4 6 1 2 5 8 7 9
输出样例 1:
3 6 9