summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--.gitignore4
-rw-r--r--Makefile24
-rw-r--r--easy.txt11
-rw-r--r--easy2.txt11
-rw-r--r--eureka.txt19
-rw-r--r--solve.cpp275
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;
+ }
+}
generated by cgit v1.2.3-70-g09d2 (git 2.47.0) at 2024-11-22 09:19:10 +0100