Skip to content

Instantly share code, notes, and snippets.

Created April 22, 2012 16:27
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save anonymous/2465071 to your computer and use it in GitHub Desktop.
Save anonymous/2465071 to your computer and use it in GitHub Desktop.
Sudoku solver
#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