// template sudoku backtracking solver // marcus fritzsch, http://fritschy.de, 2007-02-01 // // input files should look like the following example: // // 53--7---- // 6--195--- // -98----6- // 8---6---3 // 4--8-3--1 // 7---2---6 // -6----28- // ---419--5 // ----8--79 // // (w/o any spaces or newlines ;o)) #include #include #include #include #include #include //#define USE_TEST //#define USE_OUTPUT typedef unsigned char pzt; typedef pzt Pz [81]; struct Sols { typedef unsigned int basetype; struct ll { basetype a, b; ll () : a(0), b(0) {} ll & operator ++ () { b += a == 0xffffffffu; ++a; return *this; } operator double () const { return double (a) + double (0xffffffffu) * double (b); } }; ll n; static Sols & i () { static Sols s; return s; } private: Sols () : n() {} Sols (const Sols &); Sols & operator = (const Sols &); }; #ifdef USE_TEST // return true if the whole p is correct, i.e. completely solved // and valid const bool Correct (Pz p) { for (int r = 0; r != 9; ++r) for (int c = 0, n = 0, m = 0; c != 9; ++c) { if (p [r*9+c] == 0) return false; if (n & (1<<(p [r*9+c]-1))) return false; n |= 1<<(p [r*9+c]-1); if (p [c*9+r] == 0) return false; if (m & (1<<(p [c*9+r]-1))) return false; m |= 1<<(p [c*9+r]-1); } for (int r0 = 0; r0 != 3; ++r0) for (int c0 = 0; c0 != 3; ++c0) for (int r = r0*3, n = 0; r != (r0+1)*3; ++r) for (int c = c0*3; c != (c0+1)*3; ++c) { if (p [r*9+c] == 0) return false; if (n & (1<<(p [r*9+c]-1))) return false; n |= 1<<(p [r*9+c]-1); } return true; } #endif const double Time () { timeval tv; gettimeofday (&tv, NULL); return static_cast (tv.tv_sec) + static_cast (tv.tv_usec) * 1e-6; } template void Print (Pz pz) { if (i!=0&&i%9==0) std::cout << std::endl; std::cout << char(pz[i]+'0'); Print (pz); } template <> void Print <81> (Pz) { std::cout << std::endl << std::endl; } // check all columns at row r for symbol x recursively template struct Row { static const bool V (Pz p) { return p [r*9+c] != x && Row ::V (p); } }; // last column, check for symbol x and return template struct Row { static const bool V (Pz p) { return p [r*9+8] != x; } }; // check all rows at column c for symbol x recursively template struct Col { static const bool V (Pz p) { return p [r*9+c] != x && Col ::V (p); } }; // last row, check for symbol x and return template struct Col { static const bool V (Pz p) { return p [8*9+c] != x; } }; // check the block (r,c) for symbol x template struct Block { static const bool V (Pz p) { return p [(r+ir)*9+c+ic] != x && Block ::V (p); } }; // column overflow in block, restart at next row template struct Block { static const bool V (Pz p) { return Block ::V (p); } }; // row overflow in block, block is valid with x template struct Block { static const bool V (Pz) { return true; } }; template struct S { static void s (Pz p) { if (p [i]) S ::s (p); // cell is not empty, next cell else { #define F (i%3==0?i+1:i) // F should not be dividable by 3 #define X (1+(x*F+1)%9) // permuted symbols if (!(Row ::V (p) && Col ::V (p) && Block ::V (p))) { S ::s (p); // symbol is invalid here, try next one } else { p [i] = X; S ::s (p); // this one fits, next cell p [i] = 0; S ::s (p); // next symbol, to acquire all solutions } #undef F #undef X } } }; // row overflow, the p was solved template struct S <81, x> { static void s (Pz p) { #ifdef USE_OUTPUT Print <0> (p); #else static_cast (p); #endif #ifdef USE_TEST if (!Correct (p)) { std::cerr << "This is no correct solution" << std::endl; exit (1); } #endif ++Sols::i().n; } }; // symbol overflow, do nothing template struct S { static void s (Pz) {} }; void file (std::istream & is) { Pz p; int N=0; std::string ln; for (int r = 0; r != 9 && getline (is, ln); ++r) for (int i = 0; i != 9; ++i) { if (ln[i]=='-' || ln[i]=='*' || ln[i]==' ' || ln[i]=='.') ln[i]='0'; p [r*9+i] = ln[i]-'0'; ++N; } assert (N == 81); Sols::i().n=Sols::ll(); double x = Time (); S <0,1>::s (p); std::cerr << Time () - x << " seconds to solve (" << std::setprecision (16) << Sols::i().n << " solutions)" << std::endl << std::endl; } int main (int c, char ** v) { if (c<2) { std::cerr << "usage: " << *v << " [file1 ...]" << std::endl; std::cerr << "waiting for input..." << std::endl << std::endl; file (std::cin); } else for (c=1; v [c]; ++c) { std::ifstream is (v[c]); file (is); } return 0; }