Created
April 22, 2012 16:27
-
-
Save anonymous/2465071 to your computer and use it in GitHub Desktop.
Sudoku solver
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <map> | |
#include <assert.h> | |
#include <bitset> | |
#include <string> | |
#include <queue> | |
#include <stack> | |
#include <iostream> | |
#include <fstream> | |
//#define DBG | |
using namespace std; | |
typedef map<string, bool> MSB; | |
typedef vector<int> VI; | |
#define pb push_back | |
void sdkprint(string a, ostream & out){ | |
out <<endl; | |
for (int i=0;i<9;i++){ | |
if(i%3==0) out << "_____________" <<endl; | |
for (int j=0;j<9;j++){ | |
if (j%3==0) out <<"|"; | |
out << a[i*9+j] ; | |
} | |
out <<"|" << endl; | |
} | |
out << "_____________" <<endl; | |
} | |
class Sudoku{ | |
private: | |
string start; | |
string sol; | |
MSB done; | |
vector<VI> nlist; | |
VI workspace; | |
bitset <81> assigned; | |
bool check(string &); | |
bool valid(string &, const int &); | |
void init(); | |
bool ApplyConstraints(string &); | |
char CheckSingleValue(const int & i); | |
bool assign(string &a, char val, const int &i); | |
public: | |
Sudoku(const char *); | |
~Sudoku(); | |
string operator()(); | |
}; | |
void Sudoku::init(){ | |
nlist.assign(81, VI()); | |
for (int i =0;i<81;i++){ | |
int x = i%9; | |
int y = i/9; | |
for (int xi=0;xi<9;xi++){ | |
if (xi == x) continue; | |
nlist[i].pb(xi+y*9); | |
} | |
for (int yi=0;yi<9;yi++){ | |
if (yi == y) continue; | |
nlist[i].pb(x+yi*9); | |
} | |
int qx = x/3; | |
int qy = y/3; | |
for (int xi=qx*3;xi<qx*3+3;xi++){ | |
for (int yi=qy*3;yi<qy*3+3;yi++){ | |
if (x==xi || y==yi) continue; | |
nlist[i].pb(xi+yi*9) ; | |
} | |
} | |
#ifdef DBG | |
cout << "NLIST of " << i << ": "; | |
for (int k=0;k<20;k++) cout<< nlist[i][k] << " "; | |
cout <<endl; | |
#endif | |
} | |
} | |
bool Sudoku::valid(string & a, const int & i) { | |
for (VI::iterator it=nlist[i].begin(); it!= nlist[i].end(); ++it){ | |
if(a[*it] == a[i]) return false; | |
} | |
return true; | |
} | |
bool Sudoku::check(string & a){ | |
for (int i=0;i<a.size();i++) { | |
if ( a[i] <'0' || a[i] >'9') return false; | |
} | |
if (a.size()!=81 ) return false; | |
return true; | |
} | |
Sudoku::Sudoku(const char * namef){ | |
ifstream in(namef); | |
start=string(""); | |
while (in){ | |
string l; | |
in >> l; | |
start += l; | |
} | |
if (check(start)){ | |
cout << "Start interpreting" <<endl; | |
sdkprint(start,cout); | |
} | |
else { | |
cout << "Error in input" <<endl; | |
} | |
init(); | |
} | |
char Sudoku::CheckSingleValue(const int & i){ | |
for (int j=0;j<9;j++){ | |
if ( workspace[i] == (1<<j) ) return '0'+1+j; | |
} | |
return 0; | |
} | |
bool Sudoku::assign(string &a, char val, const int &i){ | |
if (!assigned[i]){ | |
assigned[i] = true; // mark as assigned at end of loop | |
a[i] = val; // set value to string | |
int ival = val-'0'-1; | |
workspace[i] = (1 << ival); // set only possibility | |
for (int j=0;j<20;j++){ | |
int neigh = nlist[i][j]; // select neighbour | |
bitset<9> mask; | |
mask.set(); | |
mask[ival] = 0; | |
workspace[neigh] &= (mask.to_ulong()); // set bit neigh to 0 | |
if (!workspace[neigh]) return false; //return false if no possibilities are left | |
} | |
for (int j=0;j<81;j++){ // do a second sweep to check if any new characters are single valued | |
char recur = CheckSingleValue(j); // check if a single value is allowed | |
if (recur){ | |
bool notposs = assign(a, recur, j); | |
if (!notposs) return false; | |
} | |
} | |
} | |
return true; | |
} | |
bool Sudoku::ApplyConstraints(string &a){ | |
workspace.assign(81, (1<<10)-1); // set all to 1 | |
assigned.reset(); // unset all DP shit | |
for (int i=0;i<81;i++){ | |
if (a[i]!= '0') { | |
if( !assign(a,a[i],i) ) return false; | |
} | |
} | |
return true; | |
} | |
string Sudoku::operator()(){ | |
stack <string> s; | |
s.push(start); | |
int l =0; | |
while (!s.empty() ){ | |
l++; | |
string t = s.top(); | |
#ifdef DBG | |
cout << "trial: " ; | |
sdkprint(t, cout); | |
#endif | |
s.pop(); | |
bool prop = ApplyConstraints(t); | |
if (done.find(t) == done.end() ){ | |
done[t] = true; // t might have changed due to the constraints! | |
#ifdef DBG | |
cout << "After applying constraints: " ; | |
sdkprint(t, cout); | |
for (int i=0;i<81;i++) { | |
bitset<9> tmp(workspace[i]); | |
cout << "possibilities for: " << i << " " << tmp.to_string()<<endl; | |
} | |
cout << "test #1: " << int(CheckSingleValue(1)) <<endl; | |
#endif | |
if (prop){ | |
bool finished = true; | |
l++; | |
for (int i=0;i<81;i++) { | |
if (!assigned[i]) { | |
finished = false; | |
for (int j=0;j<9;j++){ | |
#ifdef DBG | |
bitset <9>tmp(workspace[i]); | |
bool test= (((workspace[i] & (1<<j) ) >> j)) ; | |
cout << "looking for next possible ones for pos: "<< i<< " poss: " << tmp.to_string() << "tring : " << j << | |
" bitshit: " << test << endl; | |
#endif | |
if ( (workspace[i] & (1<<j) ) >> j ) { | |
string news(t); | |
news[i] = '0'+1+j; | |
s.push(news); | |
} | |
} | |
} | |
} | |
if (finished){ | |
bool test = (done.find(t) == done.end()); | |
cout << "Tried so many: " << l << " permutes " << endl; | |
if (test) cout << "could repeat?" <<endl; | |
sol = t; | |
sdkprint(t, cout); | |
} | |
} | |
} | |
} | |
cout << "tried all Solutions " <<endl; | |
return sol; | |
} | |
Sudoku::~Sudoku(){ | |
done.clear(); | |
start.clear(); | |
nlist.clear(); | |
workspace.clear(); | |
} | |
int main(){ | |
Sudoku sdk("test1.txt"); | |
string res = sdk(); | |
sdkprint(res, cout); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment