60 lines
2.5 KiB
C++
60 lines
2.5 KiB
C++
// A class to solve Nonogram (Hadje) Puzzles
|
|
// Nigel Galloway - January 23rd., 2017
|
|
template<uint _N, uint _G> class Nonogram {
|
|
enum class ng_val : char {X='#',B='.',V='?'};
|
|
template<uint _NG> struct N {
|
|
N() {}
|
|
N(std::vector<int> ni,const int l) : X{},B{},Tx{},Tb{},ng(ni),En{},gNG(l){}
|
|
std::bitset<_NG> X, B, T, Tx, Tb;
|
|
std::vector<int> ng;
|
|
int En, gNG;
|
|
void fn (const int n,const int i,const int g,const int e,const int l){
|
|
if (fe(g,l,false) and fe(g+l,e,true)){
|
|
if ((n+1) < ng.size()) {if (fe(g+e+l,1,false)) fn(n+1,i-e-1,g+e+l+1,ng[n+1],0);}
|
|
else {
|
|
if (fe(g+e+l,gNG-(g+e+l),false)){Tb &= T.flip(); Tx &= T.flip(); ++En;}
|
|
}}
|
|
if (l<=gNG-g-i-1) fn(n,i,g,e,l+1);
|
|
}
|
|
void fi (const int n,const bool g) {X.set(n,g); B.set(n, not g);}
|
|
ng_val fg (const int n) const{return (X.test(n))? ng_val::X : (B.test(n))? ng_val::B : ng_val::V;}
|
|
inline bool fe (const int n,const int i, const bool g){
|
|
for (int e = n;e<n+i;++e) if ((g and fg(e)==ng_val::B) or (!g and fg(e)==ng_val::X)) return false; else T[e] = g;
|
|
return true;
|
|
}
|
|
int fl (){
|
|
if (En == 1) return 1;
|
|
Tx.set(); Tb.set(); En=0;
|
|
fn(0,std::accumulate(ng.cbegin(),ng.cend(),0)+ng.size()-1,0,ng[0],0);
|
|
return En;
|
|
}}; // end of N
|
|
std::vector<N<_G>> ng;
|
|
std::vector<N<_N>> gn;
|
|
int En, zN, zG;
|
|
void setCell(uint n, uint i, bool g){ng[n].fi(i,g); gn[i].fi(n,g);}
|
|
public:
|
|
Nonogram(const std::vector<std::vector<int>>& n,const std::vector<std::vector<int>>& i,const std::vector<std::string>& g = {}) : ng{}, gn{}, En{}, zN(n.size()), zG(i.size()) {
|
|
for (int n=0; n<zG; n++) gn.push_back(N<_N>(i[n],zN));
|
|
for (int i=0; i<zN; i++) {
|
|
ng.push_back(N<_G>(n[i],zG));
|
|
if (i < g.size()) for(int e=0; e<zG or e<g[i].size(); e++) if (g[i][e]=='#') setCell(i,e,true);
|
|
}}
|
|
bool solve(){
|
|
int i{}, g{};
|
|
for (int l = 0; l<zN; l++) {
|
|
if ((g = ng[l].fl()) == 0) return false; else i+=g;
|
|
for (int i = 0; i<zG; i++) if (ng[l].Tx[i] != ng[l].Tb[i]) setCell (l,i,ng[l].Tx[i]);
|
|
}
|
|
for (int l = 0; l<zG; l++) {
|
|
if ((g = gn[l].fl()) == 0) return false; else i+=g;
|
|
for (int i = 0; i<zN; i++) if (gn[l].Tx[i] != gn[l].Tb[i]) setCell (i,l,gn[l].Tx[i]);
|
|
}
|
|
if (i == En) return false; else En = i;
|
|
if (i == zN+zG) return true; else return solve();
|
|
}
|
|
const std::string toStr() const {
|
|
std::ostringstream n;
|
|
for (int i = 0; i<zN; i++){for (int g = 0; g<zG; g++){n << static_cast<char>(ng[i].fg(g));}n<<std::endl;}
|
|
return n.str();
|
|
}};
|