Initial

6 files changed, 344 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..af2ead4
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,4 @@
+solve
+*.o
+*.dSYM
+.DS_Store
diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..ef6cc85
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,24 @@
+CXX = g++
+CXXFLAGS = -Wall -Wextra -std=c++11 -fwrapv -g
+ifneq ($(DEBUG),)
+	CXXFLAGS += -g
+else
+	CXXFLAGS += -O2
+endif
+BIN = solve
+
+.PHONY: all clean remake
+
+all: $(BIN)
+
+clean:
+	rm -rf $(BIN) *.o *.dSYM
+
+remake: clean all
+
+
+$(BIN): $(patsubst %.cpp,%.o,$(wildcard *.cpp))
+	$(CXX) -o $@ $^
+
+%.o: %.cpp $(wildcard *.h)
+	$(CXX) $(CXXFLAGS) -c -o $@ $<
diff --git a/easy.txt b/easy.txt
new file mode 100644
index 0000000..5acd093
--- /dev/null
+++ b/easy.txt
@@ -0,0 +1,11 @@
+. . .  . 4 6  1 . .
+3 . .  . . .  . . .
+7 6 .  . . 3  . 5 2
+
+. 7 1  3 . .  . . 8
+9 3 .  . 2 .  . 7 1
+6 . .  . . 1  5 4 .
+
+1 8 .  6 . .  . 9 4
+. . .  . . .  . . 7
+. . 7  4 1 .  . . .
diff --git a/easy2.txt b/easy2.txt
new file mode 100644
index 0000000..88f4eaa
--- /dev/null
+++ b/easy2.txt
@@ -0,0 +1,11 @@
+. 6 .  . . 4  3 . .
+. 8 .  . 2 .  . . .
+. . 2  . 7 9  8 5 .
+
+. . .  . . .  . 6 7
+. 2 3  8 . 1  4 9 .
+5 9 .  . . .  . . .
+
+. 4 9  2 1 .  5 . .
+. . .  . 5 .  . 8 .
+. . 8  3 . .  . 4 .
diff --git a/eureka.txt b/eureka.txt
new file mode 100644
index 0000000..dc9e672
--- /dev/null
+++ b/eureka.txt
@@ -0,0 +1,19 @@
+. 1 E . .   . . 5 . F   7 2 . . D
+. . . A F   . 7 . . .   . C . 1 B
+. 8 . . .   . . . . 3   A E . . .
+
+D 4 7 F 1   . 9 A C .   . . . . 3
+C 5 . 9 3   B . . . .   . . F . .
+. 6 . B .   F 1 . . .   9 . D C 4
+
+8 E B . 6   C . 3 . .   . 9 4 F .
+F 3 2 1 7   E B 9 . A   C 6 8 D .
+. . 9 . .   1 . 8 . 6   E 3 7 . .
+
+2 . 1 . .   A . B D 5   . 7 . 9 C
+B . 4 . D   . . . . .   . A . 5 6
+9 . . E A   4 . 2 . .   . . 1 3 8
+
+. B 3 7 .   . 4 D . E   . F . 2 1
+. 9 F . .   . . C 8 .   . . . . .
+. . . 8 .   . . . . .   . . . 6 9
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;
+	}
+}