summaryrefslogtreecommitdiff
path: root/solve.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'solve.cpp')
-rw-r--r--solve.cpp275
1 files changed, 275 insertions, 0 deletions
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 (git 2.25.1) at 2024-04-28 12:04:21 +0200