From 756a8c48b567901d2483e6ea2213c00e5ca47931 Mon Sep 17 00:00:00 2001
From: tomsmeding <tom.smeding@gmail.com>
Date: Fri, 28 Oct 2016 23:14:38 +0200
Subject: Initial

---
 solve.cpp | 275 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 275 insertions(+)
 create mode 100644 solve.cpp

(limited to 'solve.cpp')

diff --git a/solve.cpp b/solve.cpp
new file mode 100644
index 0000000..59c43e3
--- /dev/null
+++ b/solve.cpp
@@ -0,0 +1,275 @@
+#include <iostream>
+#include <fstream>
+#include <sstream>
+#include <vector>
+#include <string>
+#include <bitset>
+#include <cassert>
+
+
+bool stdout_is_color_tty;
+
+
+#if defined (__unix__) || (defined (__APPLE__) && defined (__MACH__))
+
+#include <unistd.h>
+class Tty_init_static{
+public:
+	Tty_init_static(){
+		stdout_is_color_tty=(bool)isatty(1);
+	}
+} tty_init_static;
+
+#else
+
+class Tty_init_static{
+public:
+	Tty_init_static(){
+		stdout_is_color_tty=false;
+	}
+} tty_init_static;
+
+#endif
+
+
+using namespace std;
+
+
+string readfile(istream &is){
+	string res;
+	char buf[1024];
+	while(true){
+		is.read(buf,sizeof(buf));
+		int nread=is.gcount();
+		if(nread==0)break;
+		res.append(buf,sizeof(buf));
+	}
+	return res;
+}
+
+
+template <int N,int BW,int BH>
+class Sudoku{
+private:
+	int bd[N][N]; // bd[y][x]
+	bitset<N> poss[N][N];
+	bool given[N][N];
+
+	void calcposs(){
+		for(int y=0;y<N;y++){
+			for(int x=0;x<N;x++){
+				if(bd[y][x]!=-1)continue;
+				poss[y][x].set();
+				for(int i=0;i<N;i++){
+					if(bd[y][i]!=-1)poss[y][x].reset(bd[y][i]-1);
+				}
+				for(int i=0;i<N;i++){
+					if(bd[i][x]!=-1)poss[y][x].reset(bd[i][x]-1);
+				}
+				int boxX=x/BW*BW,boxY=y/BH*BH;
+				for(int i=0;i<BH;i++){
+					for(int j=0;j<BW;j++){
+						if(bd[boxY+i][boxX+j]!=-1)poss[y][x].reset(bd[boxY+i][boxX+j]-1);
+					}
+				}
+			}
+		}
+	}
+
+	bool resolveposs(){
+		bool acted=false;
+		for(int y=0;y<N;y++){
+			for(int x=0;x<N;x++){
+				if(bd[y][x]!=-1)continue;
+				if(poss[y][x].count()==1){
+					bd[y][x]=__builtin_ctz(poss[y][x].to_ulong())+1;
+					poss[y][x].reset();
+					acted=true;
+				}
+			}
+		}
+		return acted;
+	}
+
+	void recurseone(vector<Sudoku<N,BW,BH>> &dst) const {
+		int miny=-1,minx=-1,mincount=N+1;
+		for(int y=0;y<N;y++){
+			for(int x=0;x<N;x++){
+				if(bd[y][x]!=-1)continue;
+				int count=poss[y][x].count();
+				if(count>0&&count<mincount){
+					mincount=poss[y][x].count();
+					minx=x;
+					miny=y;
+				}
+			}
+		}
+		if(minx==-1)return; //no possible changes to make
+		for(int i=1;i<=N;i++){
+			if(!poss[miny][minx].test(i-1))continue;
+			Sudoku<N,BW,BH> S(*this);
+			S.bd[miny][minx]=i;
+			S.solve(dst);
+		}
+	}
+
+	bool solved() const {
+		if(!verifyConsistent())return false;
+		for(int y=0;y<N;y++){
+			for(int x=0;x<N;x++){
+				if(bd[y][x]==-1)return false;
+			}
+		}
+		return true;
+	}
+
+	void solve(vector<Sudoku<N,BW,BH>> &dst){
+		do calcposs();
+		while(resolveposs());
+		if(solved()){
+			dst.push_back(*this);
+			return;
+		}
+		recurseone(dst);
+	}
+
+public:
+	Sudoku(const string &init){
+		static_assert(N>1&&BW>1&&BH>1&&BW*BH==N,"Box size inconsistent");
+
+		stringstream ss(init);
+		for(int y=0;y<N;y++){
+			for(int x=0;x<N;x++){
+				char c;
+				ss>>c;
+				if(c=='.'){
+					bd[y][x]=-1;
+					poss[y][x].set();
+					given[y][x]=false;
+					continue;
+				}
+				int n=-1;
+				if(c>='1'&&c<='9')n=c-'0';
+				else if(c>='A'&&c<='Z')n=c-'A'+10;
+				else if(c>='a'&&c<='z')n=c-'a'+10;
+				if(n<1||n>N)throw "Invalid character in init string for Sudoku";
+				bd[y][x]=n;
+				poss[y][x].set(n-1);
+				given[y][x]=true;
+			}
+		}
+	}
+
+	vector<Sudoku<N,BW,BH>> solve(){
+		vector<Sudoku<N,BW,BH>> dst;
+		solve(dst);
+		return dst;
+	}
+
+	bool verifyConsistent(bool diag=false) const {
+		for(int i=0;i<N;i++){
+			bitset<N> seenH,seenV;
+			for(int j=0;j<N;j++){
+				if(bd[i][j]!=-1){
+					if(seenH.test(bd[i][j]-1)){if(diag)cerr<<__LINE__<<": ("<<j<<','<<i<<')'<<endl; return false;}
+					seenH.set(bd[i][j]-1);
+				}
+				if(bd[j][i]!=-1){
+					if(seenV.test(bd[j][i]-1)){if(diag)cerr<<__LINE__<<": ("<<i<<','<<j<<')'<<endl; return false;}
+					seenV.set(bd[j][i]-1);
+				}
+			}
+		}
+		return true;
+	}
+
+	bool verifySolution(const Sudoku<N,BW,BH> &sol) const {
+		for(int y=0;y<N;y++){
+			for(int x=0;x<N;x++){
+				if(sol.bd[y][x]==-1){cerr<<__LINE__<<": ("<<x<<','<<y<<')'<<endl; return false;}
+				if(bd[y][x]!=-1&&bd[y][x]!=sol.bd[y][x]){cerr<<__LINE__<<": ("<<x<<','<<y<<')'<<endl; return false;}
+			}
+		}
+		return sol.verifyConsistent(true);
+	}
+
+	//-1: <, 0: ==, 1: >
+	int compare(const Sudoku<N,BW,BH> &other) const {
+		for(int y=0;y<N;y++){
+			for(int x=0;x<N;x++){
+				if(bd[y][x]==other.bd[y][x])continue;
+				if(bd[y][x]==-1)return -1;
+				if(other.bd[y][x]==-1)return 1;
+				if(bd[y][x]<other.bd[y][x])return -1;
+				if(bd[y][x]>other.bd[y][x])return 1;
+			}
+		}
+		return 0;
+	}
+
+	bool operator==(const Sudoku<N,BW,BH> &other) const {return compare(other)==0;}
+	bool operator!=(const Sudoku<N,BW,BH> &other) const {return compare(other)!=0;}
+	bool operator> (const Sudoku<N,BW,BH> &other) const {return compare(other)> 0;}
+	bool operator>=(const Sudoku<N,BW,BH> &other) const {return compare(other)>=0;}
+	bool operator< (const Sudoku<N,BW,BH> &other) const {return compare(other)< 0;}
+	bool operator<=(const Sudoku<N,BW,BH> &other) const {return compare(other)<=0;}
+
+	template <int _,int BW_,int BH_>
+	friend ostream& operator<<(ostream &os,const Sudoku<_,BW_,BH_> &S);
+};
+
+template <int N,int BW,int BH>
+ostream& operator<<(ostream &os,const Sudoku<N,BW,BH> &S){
+	for(int y=0;y<N;y++){
+		if(y>0){
+			if(y%BH==0)os<<endl;
+			os<<endl;
+		}
+		for(int x=0;x<N;x++){
+			if(x>0){
+				if(x%BW==0)os<<"  ";
+				os<<' ';
+			}
+			bool color=stdout_is_color_tty&&!S.given[y][x]&&S.bd[y][x]!=-1;
+			if(color)os<<"\x1B[42;1m";
+			if(S.bd[y][x]==-1)os<<'.';
+			else if(S.bd[y][x]<=9)os<<S.bd[y][x];
+			else os<<(char)('A'+S.bd[y][x]-10);
+			if(color)os<<"\x1B[0m";
+		}
+	}
+	os<<endl;
+	return os;
+}
+
+
+int main(){
+	const int N=15,BW=5,BH=3;
+	const string fname="eureka.txt";
+	// const int N=9,BW=3,BH=3;
+	// const string fname="easy2.txt";
+
+	ifstream is(fname);
+	Sudoku<N,BW,BH> S(readfile(is));
+	Sudoku<N,BW,BH> origS(S);
+
+	auto solutions=S.solve();
+	if(solutions.size()==0){
+		cerr<<"0 solutions :("<<endl;
+		return 0;
+	} else {
+		cerr<<solutions.size()<<" solution"<<(solutions.size()==1?"":"s")<<':'<<endl;
+	}
+	bool first=true;
+	sort(solutions.begin(),solutions.end());
+	for(int i=0;i<(int)solutions.size();i++){
+		const auto &sol=solutions[i];
+		if(i>0&&sol==solutions[i-1])continue;
+		if(!first){
+			cout<<string(2*N-1+2*(N/BW-1)+6,'-')<<endl<<endl;
+		}
+		first=false;
+		assert(origS.verifySolution(sol));
+		cout<<sol<<endl;
+	}
+}
-- 
cgit v1.2.3-54-g00ecf