A146971 generator

sicktiles.cpp

#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>
#include <vector>
#include <unordered_map>
#include <utility>
#include <tuple>
#include <algorithm>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <cstdint>

using namespace std;

typedef uint64_t ull;

int S,SS;


struct Bitset{
	const int N;
	uint64_t *bits;
	Bitset(int _N):N(_N),bits(new uint64_t[N/64+1]()){}
	~Bitset(void){if(bits)delete[] bits;}
	Bitset(const Bitset &other):N(other.N){
		if(other.bits){
			bits=new uint64_t[N/64+1];
			memcpy(bits,other.bits,N/8+1);
		} else {
			bits=NULL;
		}
	}
	inline bool test(int i){return bits[i/64]&((uint64_t)1<<(i%64));}
	inline void set(int i){bits[i/64]|=((uint64_t)1<<(i%64));}
	inline void reset(int i){bits[i/64]&=~((uint64_t)1<<(i%64));}
};


void print_board(Bitset &bd,ostream &os){
	int x,y;
	for(y=0;y<S;y++){
		for(x=0;x<S;x++){
			os<<bd.test(S*y+x);
		}
		os<<endl;
	}
}

inline bool docheck(Bitset bd,int &count){
	int x,y;
	bool /*good,*/acted,allfull;
	//first check for adjacent tiles
	/*good=true;
	for(y=0;y<S&&good;y++){
		for(x=0;x<S;x++){
			if(!bd.test(S*y+x))continue;
			if(x!=0&&bd.test(S*y+x-1)){good=false;break;}
			if(y!=0&&bd.test(S*(y-1)+x)){good=false;break;}
		}
	}
	if(!good)return false;*/

	//then check if this configuration will indeed make a full board
	do{
		acted=false;
		allfull=true;
		for(y=0;y<S;y++){
			for(x=0;x<S;x++){
				if(bd.test(S*y+x))continue;
				allfull=false;
				if((x!=0&&bd.test(S*y+x-1))+
				   (y!=0&&bd.test(S*(y-1)+x))+
				   (x%S!=S-1&&bd.test(S*y+x+1))+
				   (y!=S-1&&bd.test(S*(y+1)+x))>=2){
					bd.set(S*y+x);
					acted=true;
				}
			}
		}
		/*for(i=0;i<SS;i++){
			if(bd.test(i))continue;
			allfull=false;
			if((i%S!=0&&bd.test(i-1))+
			   (i>=S&&bd.test(i-S))+
			   (i%S!=S-1&&bd.test(i+1))+
			   (i<SS-S&&bd.test(i+S))>=2){
				bd.set(i);
				acted=true;
			}
		}*/
	}while(acted);
	if(allfull){
		count++;
		return true;
	}
	return false;
}

void search(Bitset &bd,int &count,int from,int depth){
	if(depth==S){
		if(docheck(bd,count)){
			//print_board(bd,cerr); cerr<<endl;
		}
		return;
	}
	int i;
	for(i=from;i<SS-(S-depth-1);i++){
		if((i>=S&&bd.test(i-S))||(i%S!=0&&bd.test(i-1)))continue;
		bd.set(i);
		search(bd,count,i+1,depth+1);
		bd.reset(i);
	}
}

int main(void){
	ios_base::sync_with_stdio(false);
	cin>>S;
	SS=S*S;
	Bitset bd(SS);
	int count=0;
	search(bd,count,0,0);
	cout<<count<<endl;
	return 0;
}