#include <chrono>
#include <cstring>
#include <iostream>
#include <map>
#include <random>
#include <string>
#include <vector>

template <size_t w, size_t h>
class CGameSolver {
	static_assert(w*h,"Game Table Size must be a valid value.");
	
	std::string m_table;
public:
	inline bool operator<(const CGameSolver& o) const {return m_table<o.m_table;}
	const std::string& getHash() const {return m_table;}
	void fromHash(std::string const& hash)
	{
		if(hash.size()!=(w*h)) return;
		for(size_t i=0;i<hash.size();++i) { if(hash[i] != ' ' && hash[i] != 'x') return; }
		m_table=hash;
	}

	CGameSolver()
	{
		m_table.resize(w*h);
		for(size_t i=0;i<(w*h);++i)
			m_table[i]=' ';
	}
	inline size_t get_index(size_t x, size_t y) const
	{
		return (y*w)+x;
	}
	static bool IsValidIndex(size_t x, size_t y)
	{
		return x<w&&y<h;
	}
	void Toggle(size_t x, size_t y)
	{
		if(!IsValidIndex(x,y)) return;
		
		bool m_toggleTable[w*h];
		for(size_t i=0;i<(w*h);++i) { m_toggleTable[i]=0; }
		
		for(size_t i=0;i<w;++i)
		{
			m_toggleTable[get_index(i,y)]=1;
		}
		for(size_t i=0;i<h;++i)
		{
			m_toggleTable[get_index(x,i)]=1;
		}
		
		for(size_t i=0;i<(w*h);++i)
		{
			if(m_toggleTable[i])
			{
				m_table[i] = (m_table[i]=='x')?' ':'x';
			}
		}
	}
};

struct PathPoint {
	size_t X;
	size_t Y;
};

class CSolvingPath {
	std::vector<PathPoint> m_Path;
public:
	void Append(PathPoint const& b) {m_Path.push_back(b);}
	template <size_t x, size_t y>
		bool ComputeTable(CGameSolver<x,y> const& src, CGameSolver<x,y>& dst) const
		{
			for(size_t i=0;i<m_Path.size();++i)
			{
				if(!CGameSolver<x,y>::IsValidIndex(m_Path[i].X,m_Path[i].Y))
					return 0;
			}
			dst = src;
			for(size_t i=0;i<m_Path.size();++i)
			{
				dst.Toggle(m_Path[i].X,m_Path[i].Y);
			}
			return 1;
		}
};

int main(int argc, char** argv)
{
	const size_t width=3;
	const size_t height=3;
	typedef CGameSolver<width,height> ActualTable;
	
	int doContinue(0);
	do {
		std::string userHash;
		
		//! Generate from commandline hash?
		if(argc==2)
		{
			//! Format:
			//!   Either an X/x, or any other symbol.
			//!   String is truncated, the rest is whitespace.
			userHash.assign(width*height,' ');
			size_t userlen = std::strlen(argv[1]);
			if(userlen > (width*height))
				userlen = (width*height);
			for(size_t i=0;i<userlen;++i)
			{
				if( (argv[1][i] == 'x') || (argv[1][i] == 'X') )
					userHash[i] = 'x';
			}
			
			//! So that next loop we will generate randomly.
			argc=1;
		}
		else
		{
			//! Generate randomly
			std::mt19937 rng;
			std::uniform_int_distribution<std::int8_t> distr(0,1);
			rng.seed(std::chrono::steady_clock::now().time_since_epoch().count());
			userHash.resize(width*height);
			for(size_t i=0;i<(width*height);++i)
			{
				userHash[i] = (!distr(rng)) ? ' ' : 'x';
			}
			
			std::cout << "Computed hash:" << std::endl << "\t[" << userHash << ']' << std::endl << std::endl;
		}
		
		//! Initial table, initialized from hash
		//! The hash is simply a combination of either a ' ' or a 'x'.
		//! An "123456789" hash is stored as follows:
		//! [--][x1][x2][x3]
		//! [y1][ 1][ 2][ 3]
		//! [y2][ 4][ 5][ 6]
		//! [y3][ 7][ 8][ 9]
		
		ActualTable sourceTable;
		sourceTable.fromHash(userHash);
		
		//! Store all the possible combinations,
		//! and the shortest path to any of them.
		std::map<ActualTable,CSolvingPath> m_solvers;
		m_solvers[sourceTable] = CSolvingPath();
		
		{
			//! Shouldn't be returned to our older scope,
			//! but should also not be in the for loop
			
			//! Our computed table is recomputed correctly from ComputeTable.
			//! This does not need to be constructed each time.
			ActualTable m_newTable;
			
			//! Did we find a new combination this one loop?
			//! If we didn't, we can simply stop iterating.
			bool m_thisLoopAdded;
			
			do {
				m_thisLoopAdded=0;
				
				//! For all existing combinations...
				//!		[Note: This loop can be optimized:
				//!			When a new node gets added, it may be stored in a different map.
				//!			This could save iterating over all previously-iterated nodes.
				//!			]
				for(auto it = m_solvers.begin(); it != m_solvers.end(); ++it)
				{
					ActualTable const& m_result = it->first;
					CSolvingPath& m_path = it->second;
					
					PathPoint pp;
					//! For every possible position in the table...
					for(pp.X=0;pp.X<width;++pp.X)
					{
						for(pp.Y=0;pp.Y<height;++pp.Y)
						{
							//! Append the position to the combination.
							//!   At this point, all combinations will be
							//!   combined with all points.
							CSolvingPath m_newPath(m_path);
							m_newPath.Append(pp);
							
							//! Compute the resulting table.
							if(!m_newPath.ComputeTable(m_result,m_newTable))
								continue;
							//! It should never fail.
							
							//! If there is already a combination, it has been found
							//!   with less moves, so we can ignore our current path.
							auto it_find = m_solvers.find(m_newTable);
							if(it_find == m_solvers.end())
							{
								//! Otherwise, add this combination
								m_solvers[m_newTable] = m_newPath;
								//! And mark that this loop we found a new combination.
								m_thisLoopAdded=1;
							}
						}
					}
				}
			} while(m_thisLoopAdded);
			//! Until no new combination is found.
		}
		
		std::cout << m_solvers.size() << " solutions found. Hashes: " << std::endl << std::endl;
		
		//! To store the current hash's index
		std::uint32_t i=0;
		
		//! We'll find it out right now as we iterate
		bool has_solution_empty=0;
		bool has_solution_fill=0;
		
		for(auto it = m_solvers.begin(); it != m_solvers.end(); ++it)
		{
			std::string const& m_sol = it->first.getHash();
			
			//! 1	[         ]
			//! 2	[x  xxxx  ]
			//! and so on...
			std::cout << ++i << "\t[" << m_sol << ']' << std::endl;
			
			//! Not much about these ones.
			if(m_sol.find('x') == std::string::npos) has_solution_empty=1;
			else if(m_sol.find(' ') == std::string::npos) has_solution_fill=1;
		}
		
		//! And that's it.
		//!   We print these afterwards, since if there's an empty solution, it can only be the first one,
		//!   and if there's a filled solution, it can only be the last one.
		//!	  Instead of having to look through the entire list of moves to find the "X solution found",
		//!	  we'll kindly put them together at the end of it.
		
		if(has_solution_empty||has_solution_fill)
		{
			std::cout << std::endl;
			if(has_solution_empty) std::cout << "Empty solution found!" << std::endl;
			if(has_solution_fill) std::cout << "Filled solution found!" << std::endl;
		}
		
		std::cout << std::endl << "Type 0 to quit, or any other number to repeat the test with a generated value." << std::endl;
		std::cin >> doContinue;
	} while(doContinue != 0);
	
	return 0;
}