poj2676

搜索

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;

#define maxn 15

int n;
int map[maxn][maxn];
bool visr[maxn][maxn], visc[maxn][maxn], visb[maxn][maxn][maxn];
bool found;

void make(int x, int y, int a, bool v)
{
    visr[x][a] = v;
    visc[y][a] = v;
    visb[x / 3][y / 3][a] = v;
}

void input()
{
    char st[maxn];
    for (int i = 0; i < 9; i++)
    {
        scanf("%s", st);
        for (int j = 0; j < 9; j++)
        {
            map[i][j] = st[j] - '0';
            make(i, j, map[i][j], true);
        }
    }
}

bool ok(int x, int y, int a)
{
    return !visr[x][a] && !visc[y][a] && !visb[x / 3][y / 3][a];
}

void print()
{
    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
            printf("%d", map[i][j]);
        putchar('
');
    }
}

void dfs(int pos)
{
    if (found)
        return;
    if (pos == 9 * 9)
    {
        found = true;
        print();
        return;
    }
    int x = pos / 9;
    int y = pos % 9;
    if (map[x][y])
    {
        dfs(pos + 1);
        return;
    }
    for (int i = 1; i <= 9; i++)
        if (ok(x, y, i))
        {
            make(x, y, i, true);
            map[x][y] = i;
            dfs(pos + 1);
            map[x][y] = 0;
            make(x, y, i, false);
        }
}

int main()
{
    //freopen("t.txt", "r", stdin);
    int t;
    scanf("%d", &t);
    while (t--)
    {
        memset(visr, 0, sizeof(visr));
        memset(visc, 0, sizeof(visc));
        memset(visb, 0, sizeof(visb));
        input();
        found = false;
        dfs(0);
    }
    return 0;
}