数独の生成

試作ちう。

出力例

これがどれくらい難しいか誰か教えて

|9|3|5| | |7| |8| |
| | |4|5| | | | | |
| | |2| |9| |6| | |
|6| | |3| | |2| | |
| |2|7| | |4| | | |
|4| | | |7| | |1| |
| | |1|2|4| |9|6| |
|2| | |7| | |4| | |
| |4| |8|3|9| | | |

|6|3|7|5|9| |2| |4|
| |8|9| | | | | |3|
| | |1| | | |6| | |
| | | | | | | |5| |
| | | | |1| |4| |2|
| | | |7|5| |9| |1|
|2| |4|8| |7| | |9|
| |1| | | | | | | |
| | |3|1|4| |7| | |

source

#include <vector>
#include <cstdio>
using namespace std;

typedef unsigned int uint;
typedef unsigned long long int ullint;
typedef long long int lint;
typedef vector<int> vint;
typedef vector<vint> vvint;
typedef pair<int, int> pint;
typedef pair<pint, int> ppint;
typedef pair<int, pint> pintp;
#define pb push_back
#define mp make_pair
#define REP(i,s) for(int i=0; i<(int)(s); i++)
#define RREP(i,s) for(int i=(int)(s)-1; i>=0; i--)
#define FOREACH(i,v) for(typeof(v)::iterator i=v.begin();i!=v.end();i++)

#define SUDOKU_MAXRESULT 100

struct AlgoX {
    struct Node;
    struct Node {
        int x,y;
        Node *u, *d, *l, *r;
        Node(int x, int y) : x(x),y(y),u(this),d(this),l(this),r(this) {}
    };

    ~AlgoX() {
        REP(i,heads.size()) {
            for(Node* j=heads[i]->d;j!=heads[i];j=j->d) {
                delete j;
            }
            delete heads[i];
        }
    }
    vint cnt;

    vector<Node*> dels;
    void del(Node* n, bool horizon) {
        n->u->d=n->d; n->d->u=n->u;
        if(horizon) {
            n->l->r=n->r; n->r->l=n->l;
        }
        dels.pb(n);
        cnt[n->x]--;
    }

    int w,h;
    Node* head;
    vector<Node*> heads;

    Node* col_curr;
    void addCol() { h++; col_curr = NULL; }
    void add(int x) {
        Node* n = new Node(x,h-1);
        n->d = heads[x];
        n->u = n->d->u;
        if(col_curr) {
            n->l = col_curr;
            n->r = n->l->r;
        }
        col_curr = n;
        n->u->d = n->d->u = n->l->r = n->r->l = n;
        cnt[x]++;
    }
    AlgoX(int w): w(w), h(0) {
        cnt.resize(w);
        heads.resize(w+1);
        REP(x,w+1) {
            heads[x] = new Node(x,-1);
        }
        REP(x,w+1) {
            heads[(x+1)%(w+1)]->l = heads[x];
            heads[x]->r = heads[(x+1)%(w+1)];
        }
        head = heads.back();
        max_smul = -1;
    }

    vvint results;
    int max_smul;
    vint cur;
    void search(int smul) {
        if(head->r == head) {
            results.pb(cur);
            max_smul=max(max_smul,smul);
            return;
        }
        Node *targX = NULL;
        int targX_cnt = h;
        for(Node* j=head->r; j!=head; j=j->r) {
            if(cnt[j->x]<=targX_cnt) {
                targX_cnt = cnt[j->x];
                targX = j;
            }
        }
        //if(smul*targX_cnt==1)return;
        for(Node* i=targX->d; i!=targX; i=i->d) {
            uint mark = dels.size();
            for(Node *j=i; ; ) {
                Node *delX = heads[j->x];
                for(Node* k=delX->d; k!=delX; k=k->d) {
                    for(Node* l=k->r; l!=k; l=l->r) {
                        del(l,false);
                    }
                    del(k,false);
                }
                del(delX,true);
                j=j->r;
                if(j==i)break;
            }

            cur.pb(i->y);
            search(smul*targX_cnt);
            cur.pop_back();
            while(mark<dels.size()) {
                Node *n = dels.back();dels.pop_back();
                n->u->d = n->d->u = n->l->r = n->r->l = n;
                cnt[n->x]++;
            }
            if(results.size()>SUDOKU_MAXRESULT)return;
            //if(results.size()>1)return;
        }
    }
};

#define SX 3
int main(int argc, char **argv)
{
    int min_smul = 2;
    srand((unsigned)time(NULL));
    vint table(SX*SX*SX*SX, -1);
    vint prev = table;
    //int prev_type = -1;
    while(true) {
        AlgoX ax(SX*SX*SX*SX*4);
        vector<pint> result_tbl;
        vvint f;
        for(int y = 0; y < SX*SX; y++) {
            for(int x = 0; x < SX*SX; x++) {
                for(int i = 0; i < SX*SX; i++) {
                    int z=(x/SX)+(y/SX)*SX;
                    if(table[y*SX*SX+x]!=-1 && table[y*SX*SX+x]!=i)continue;
                    ax.addCol();
                    ax.add(i+y*SX*SX+0*SX*SX*SX*SX);
                    ax.add(i+x*SX*SX+1*SX*SX*SX*SX);
                    ax.add(i+z*SX*SX+2*SX*SX*SX*SX);
                    ax.add(x+y*SX*SX+3*SX*SX*SX*SX);
                    result_tbl.pb(mp(x+y*SX*SX,i));
                }
            }
        }
        ax.search(1);
        if(ax.results.size()==0){
            table = prev;
            int a;
            do {
                a = rand()%table.size();
            } while(table[a]!=-1);
            table[a]=rand()%(SX*SX);
        } else if(0<ax.max_smul && ax.max_smul<min_smul) {
            //prev = table;
            int a;
            do {
                a = rand()%table.size();
            } while(table[a]==-1);
            table[a]=-1;
        } else if(ax.results.size()>SUDOKU_MAXRESULT) {
            prev = table;
            //prev_type = 1;
            int a;
            do {
                a = rand()%table.size();
            } while(table[a]!=-1);
            table[a]=rand()%(SX*SX);
        } else if(ax.results.size()>=2) {
            prev = table;
            int a;
            do {
                a = rand()%table.size();
            } while(table[a]!=-1);
            vector<int>& r = ax.results[rand()%ax.results.size()];
            REP(i,r.size()) {
                pint val = result_tbl[r[i]];
                if(a==val.first) {
                    table[a]=val.second;
                }
            }
        } else {
            printf("max_smul = %d\n",ax.max_smul);
            for(int y = 0; y < SX*SX; y++) {
                for(int x = 0; x < SX*SX; x++) {
                    if(table[y*SX*SX+x]==-1) {
                        printf("| ");
                    } else {
                        printf("|%d", table[y*SX*SX+x]+1);
                    }
                }
                printf("|\n");
            }

            vector<int>& r = ax.results[rand()%ax.results.size()];
            vector<int> rtable(SX*SX*SX*SX);
            REP(i,r.size()) {
                pint val = result_tbl[r[i]];
                rtable[val.first]=val.second;
            }
            printf("sol:\n");
            for(int y = 0; y < SX*SX; y++) {
                for(int x = 0; x < SX*SX; x++) {
                    if(rtable[y*SX*SX+x]==-1) {
                        printf("| ");
                    } else {
                        printf("|%d", rtable[y*SX*SX+x]+1);
                    }
                }
                printf("|\n");
            }
            printf("\n\n");
            min_smul = ax.max_smul+1;
            prev = table = vint(SX*SX*SX*SX, -1);
        }
    }
    return 0;
}