数独2

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N=16;

int ones[1 << N],map[1 << N];
int state[N][N];
char str[N][N + 1];

int bstate[N * N + 1][N][N],bstate2[N * N + 1][N][N];
char bstr[N * N + 1][N][N + 1];

int lowbit(int x)
{
    return x & -x;
}



void draw(int x, int y, int c)
{
    str[x][y] = c + 'A';

    for(int i = 0; i < N; i ++ )
    {
        state[x][i] &= ~(1 << c);
        state[i][y] &= ~(1 << c);
    }

    int mx = x / 4 * 4; 
    int my = y / 4 * 4;
    for(int i = 0; i < 4; i ++ )
        for(int j = 0; j < 4; j ++ )
            state[mx + i][my + j] &= ~(1 << c);     

    state[x][y] = 1 << c;

}

bool remove(int cnt)
{
    memcpy(state, bstate[cnt], sizeof state);
    memcpy(str, bstr[cnt], sizeof str);
    return false;
}

bool dfs(int cnt)
{
    if(cnt == 0)
        return true;

    int kcnt=cnt;
    memcpy(bstate[kcnt], state, sizeof state);
    memcpy(bstr[kcnt], str, sizeof str);

    // 对于每个空格不能填返回false 只能填一个则填
    for(int i = 0; i < N; i ++ )
        for(int j = 0; j < N; j ++ )
        {
            if(str[i][j] == '-')
            {
                int s = state[i][j];

                if(s == 0)
                    return remove(kcnt);

                if(ones[s] == 1)
                {
                    draw(i, j, map[s]);
                    cnt--;
                }
            }      
        }

    // 对于每一行/列/16宫格如果有一个字母不能填返回false，某个字母只有一种填法则填
    for(int i = 0; i < N; i ++ )
    {
        int sor = 0;//记录(j之前)可选方案的并集
        int drawn = 0;//记录所有已填的字母
        int sand = (1 << N) - 1;
        //记录该行所有可选方案中只出现1或0次的字母，假设全合法筛掉不合法

        for(int j = 0; j < N; j ++ )
        {
            int s = state[i][j];
            sand &= ~ (sor & s);
            sor |= s;
            if(str[i][j]!='-')
                drawn |= state[i][j];
        }

        if(sor != (1 << N) - 1)
            return remove(kcnt);

        for(int j = sand; j; j-=lowbit(j))
        {
            int t = lowbit (j);
            if((drawn & t) == 0)
                for(int k = 0; k < N; k ++ )
                    if(state[i][k] & t)
                    {
                        draw(i, k, map[t]);
                        cnt--;
                        break;
                    }           
        }
    }

    for(int i = 0; i < N; i ++ )
        {
            int sor = 0;//记录(j之前)可选方案的并集
            int drawn = 0;//记录所有已填的字母
            int sand = (1 << N) - 1;
            //记录该行所有可选方案中只出现1或0次的字母，假设全合法筛掉不合法

            for(int j = 0; j < N; j ++ )
            {
                int s = state[j][i];
                sand &= ~ (sor & s);
                sor |= s;
                if(str[j][i]!='-')
                    drawn |= state[j][i];
            }

            if(sor != (1 << N) - 1)
                return remove(kcnt);

            for(int j = sand; j; j-=lowbit(j))
            {
                int t = lowbit (j);
                if((drawn & t) == 0)
                    for(int k = 0;k < N; k ++ )
                        if(state[k][i] & t)
                        {
                            draw(k, i, map[t]);
                            cnt--;
                            break;
                        }           
            }
        }

    for(int i = 0; i < N; i ++ )
    {
        int sor = 0;//记录(j之前)可选方案的并集
        int drawn = 0;//记录所有已填的字母
        int sand = (1 << N) - 1;
        //记录该行所有可选方案中只出现1或0次的字母，假设全合法筛掉不合法

        for(int j = 0; j < N; j ++ )
        {
            int sx = i / 4 * 4, sy = i % 4 * 4;
            // (i / 4 * 4, i % 4 * 4) 即当前 4 * 4 方格的左上角坐标
            int dx = j / 4 ,dy = j % 4;  
            int s = state[sx + dx][sy + dy];
            sand &= ~ (sor & s);
            sor |= s;
            if(str[sx + dx][sy + dy]!='-')
                drawn |= s;
        }

        if(sor != (1 << N) - 1)
            return remove(kcnt);

        for(int j = sand; j; j-=lowbit(j))
        {
            int t = lowbit (j);
            if((drawn & t) == 0)
                for(int k = 0;k < N; k ++ )
                {
                    int sx = i / 4 * 4, sy = i % 4 * 4;
                    int dx = k / 4, dy = k % 4;
                    if (state[sx + dx][sy + dy] & t)
                    {
                        draw(sx + dx, sy + dy, map[t]);
                        cnt -- ;
                        break;
                    }
                }         
        }
    }

    if(cnt == 0)
        return true;
    // 优先填最少方案数的格子

    int x,y,minv=100;
    for(int i = 0; i < N; i ++ )
        for(int j = 0; j < N; j ++)
            if(str[i][j] == '-' && ones[state[i][j]] < minv)
            {
                x = i;
                y = j;
                minv = ones[state[i][j]];
            }

    memcpy(bstate2[kcnt], state, sizeof state);

    for(int i = state[x][y]; i; i -= lowbit(i))
    {
        memcpy(state, bstate2[kcnt], sizeof state);
        draw(x, y, map[lowbit(i)]);
        if (dfs(cnt - 1)) return true;
    }

    return remove(kcnt) ;
}

int main()
{

    for(int i = 0; i < 1 << N; i ++ )
        for(int j = i; j; j -= lowbit(j))
            ones[i] ++;

    for(int i = 0; i < N; i ++ )
            map[1 << i] = i;



    while(cin >> str[0])
    {
        for(int i = 1; i < N; i ++ )
            cin >> str[i];

        for(int i = 0; i < N; i ++ )
            for(int j = 0; j < N; j ++ )
                state[i][j] = (1 << N) - 1;
        int cnt = 0;
        for(int i = 0; i < N; i ++ )
            for(int j = 0; j < N; j ++ )
            {
                if(str[i][j]!='-')
                    draw(i, j, str[i][j]-'A');
                else
                    cnt ++ ;
            }

        dfs(cnt);

        for(int i = 0; i < N; i ++ )
            cout << str[i] << endl;
        cout << endl;

    }
}