2014年9月21日 星期日

2014/09/21 TIOJ 1025 . 數獨問題

/*
    以前感覺數獨很難寫的啊xDDD

    現在居然很快 又很輕鬆 
    然後越來越精煉了 xDDD
*/
// http://tioj.ck.tp.edu.tw/problems/1025
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

int Num[100];
vector<int> v;

bool O[10][10], P[10][10], B[10][10]; int cnt;

void DFS(int Q)
{
    if( v[Q] == 81 )
    {
        for(int i = 0; i < 81; i++)
        {
            printf("%d", Num[i]);
            if( i%9 == 8 ) puts("");
            else printf(" ");
        }
        puts("");
        cnt++; return;
    }

    int t = v[Q];

    int o = t/9;
    int p = t%9;
    int b = o/3*3+p/3;

    for(int i = 1; i <= 9; i++)
        if( !O[o][i] && !P[p][i] && !B[b][i] )
        {
            O[o][i] = true;
            P[p][i] = true;
            B[b][i] = true;
            Num[t] = i;
            DFS(Q+1);
            O[o][i] = false;
            P[p][i] = false;
            B[b][i] = false;
        }
}

int main()
{
    for(int i = 0; i < 81; i++)
    {
        scanf("%d", &Num[i]);

        if( Num[i] == 0 ) v.push_back(i);
        else
        {
            int o = i/9;
            int p = i%9;
            int b = o/3*3+p/3;

            O[o][Num[i] ] = true;
            P[p][Num[i] ] = true;
            B[b][Num[i] ] = true;
        }
    }

    v.push_back(81);

    cnt = 0;
    DFS(0);

    printf("there are a total of %d solution(s).\n", cnt);
}

1 則留言: