Solution

按照题意搜索就行了。

Code

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 30;
int a[N][N][5];
int bel[N][N];
int l1[N][N];
int l2[N][N];
int used[N][N];
int ans[N][N];
void dfs(int x, int y) {
    if(y > 9) x++, y=1;
    if(x == 10) {
        for(int i=1; i<=9; i++) {
            for(int j=1; j<=9; j++) {
                printf("%d%c", ans[i][j], j==9?'\n':' ');
            }
        }
        exit(0);
    }
    int l = 1, r = 9;
    if(ans[x][y-1] && (y-1) % 3) {
        if(a[x][y][4]) l = max(l, ans[x][y-1] + 1);
        else r = min(r, ans[x][y-1] - 1);
    }
    if(ans[x-1][y] && (x-1) % 3) {
        if(a[x][y][1]) l = max(l, ans[x-1][y] + 1);
        else r = min(r, ans[x-1][y] - 1);
    }
    for(int i=l; i<=r; i++) {
        if(l1[x][i] || l2[y][i] || used[bel[x][y]][i]) continue;
        l1[x][i] = l2[y][i] = used[bel[x][y]][i] = true;
        ans[x][y] = i;
        dfs(x, y+1);
        ans[x][y] = 0;
        l1[x][i] = l2[y][i] = used[bel[x][y]][i] = false;
    }
}
int main() {
    for(int i=1; i<=3; i++) {
        for(int j=1; j<=5; j++) {
            if(j % 2) {
                for(int k=1; k<=6; k++) {
                    int x = (i - 1) * 3 + (j + 1) / 2;
                    int y = k + (k - 1) / 2;
                    char c; cin >> c;
                    a[x][y][2] = (c == '>');
                    a[x][y+1][4] = (c == '<');
                }
            } else {
                for(int k=1; k<=9; k++) {
                    int x = (i - 1) * 3 + (j + 1) / 2;
                    int y = k;
                    char c; cin >> c;
                    a[x][y][3] = (c == 'v');
                    a[x+1][y][1] = (c == '^');
                }
            }
        }
    }
    for(int i=1; i<=9; i++) {
        int x = (i - 1) / 3 + 1;
        for(int j=1; j<=9; j++) {
            int y = (j - 1) / 3 + 1;
            bel[i][j] = (x - 1) * 3 + y;
        }
    }
    dfs(1, 1);
    return 0;
}

Description

1(5).jpg.gif

Input

输入一共15行,包含一个新数独的实例。第奇数行包含左右方向的符号(<和>),第偶数行包含上下方向的符号(^和v)。

Output

输出包含9行,每行9个1~9的数字,以单个空格隔开。输入保证解惟一。

Sample Input

 < >   > <   > < 
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
 < >   < >   < > 

Sample Output

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