数独の生成
試作ちう。
出力例
これがどれくらい難しいか誰か教えて
|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; }