Брутфорс головоломки «Китайские шашки»

#include <iostream>
#include <fstream>
#include <list>
#include <string>
#include <set>
#include <vector>

namespace China_Checkers
{
	// Size of the game field
	unsigned x, y;

	// Class of game field for storage
	class Field
	{
		static const unsigned size;

		std::vector<bool> *field;
		bool is_copy;

	public:
		Field(bool** f)
		{
			field = new std::vector<bool>(size);
			// Transforming game field as matrix to vector
			for (unsigned i = 0; i < x; ++i)
			{
				for (unsigned j = 0; j < y; ++j)
				{
					if ((i > 1 && i < 5) && (j < 2 || j > 4))
						field->push_back(f[i][j]);
					else if (j > 1 && j < 5)
						field->push_back(f[i][j]);
				}
			}
		}

		Field(Field& f)
		{
			f.is_copy = true;
			field = f.field;
		}

		Field &operator=(Field& f)
		{
			f.is_copy = true;
			field = f.field;
		}

		friend bool operator==(const Field& m1, const Field& m2)
		{
			if (m1.field == m2.field) return true;
			if ((*m1.field) != (*m2.field)) return false;
			return true;
		}

		friend bool operator<(const Field& m1, const Field& m2)
		{
			if ((*m1.field) < (*m2.field)) return true;
			return false;
		}
		
		~Field()
		{
			if (is_copy)
				return;

			delete field;
		}
	};
	const unsigned Field::size = 33;

	class China_Checkers_Hack
	{
		typedef bool**                              field   ; // Type of a game field
		typedef std::pair<unsigned, unsigned>       position; // Pair of x, y
		typedef std::pair<position, position>       move    ; // Type for a move (start position, end position)
		typedef std::pair<field, std::list<move*>*> step    ; // Type for description one step of the bruteforce

		int              win_condition; // Condition scoring
		std::list<field> path_to_win  ; // Path to win
		std::set<Field>  fld_buf      ; // We checked these fields
		
		// To output a field in a stream
		friend std::ostream &operator<<(std::ostream &out, const field fld)
		{
			if (fld == nullptr)
			{
				std::cout << "Attempt to output nullptr field" << std::endl;
				system("pause");
				return out;
			}

			for (unsigned j = 0; j < x ; ++j)
			{
				for (unsigned i = 0; i < y; ++i)
				{
					if (((i < 2) || (i > 4)) && ((j < 2) || (j > 4)))
						out << '*' << ' ';
					else
						out << fld[i][j] << ' ';
				}
				out << 'n' << std::flush;
			}

			return out;
		}

		// To display a some message
		void message(const std::string msg = "")
		{
			std::cout << "Message: " << msg << std::endl;
			system("pause");
		}

		// Returns a pointer to a memory was allocated for a field, or nullptr in error case
		field alloc_mem_for_field()
		{
			field fld = nullptr;

			try
			{
				fld = new bool*[x];
				for (unsigned i = 0; i < x; ++i)
				{
					fld[i] = new bool[y];
				}
			}
			catch(std::bad_alloc)
			{
				fld = nullptr;
				message("Memory out in alloc_mem_for_field()");
			}

			return fld;
		}

		// Copy a field and returns a reference on it, or nullptr in error case
		field copy_field(field fld_dest, const field fld_source)
		{
			if (fld_dest == nullptr)
			{
				if ((fld_dest = alloc_mem_for_field()) != nullptr)
				{
					for (unsigned i = 0; i < x; ++i)
					{
						for (unsigned j = 0; j < y; ++j)
						{
							fld_dest[i][j] = fld_source[i][j];
						}
					}
				}
			}
			else
			{
				for (unsigned i = 0; i < x; ++i)
				{
					for (unsigned j = 0; j < y; ++j)
					{
						fld_dest[i][j] = fld_source[i][j];
					}
				}
			}
			return fld_dest;
		}

		// First initialize of a field
		void init_field(field &fld)
		{	
			for (unsigned i = 0; i < x; ++i)
			{
				for (unsigned j = 0; j < y; ++j)
				{
					if (
						(((i == 0) || (i == 1)) || ((i == (x - 1)) || (i == (x - 2))))
						&&
						(((j == 0) || (j == 1)) || ((j == (y - 1)) || (j == (y - 2))))
						)
						fld[i][j] = (bool)2; // Not used
					else
						fld[i][j] = 1;
				}
			}
			
			// Make the first move to reduce space of moves on 3/4
			fld[(x / 2)][(y / 2)] = 1;
			fld[(x / 2)][(y / 2 - 1)] = 0;
			fld[(x / 2)][(y / 2) - 2] = 0;
		}

		// Returns num of chips on field
		int IsWin(const field &fld)
		{
			int k = 0;

			for (unsigned i = 0; i < x; ++i)
			{
				for (unsigned j = 0; j < y; ++j)
				{
					if (
						(i < 2 || i > 4)
						&&
						(j < 2 || j > 4)
					   )
					   continue;
					
					if (fld[i][j] == 1)
						++k;
				}
			}

			return k;
		}

		// Free alloc memory 
		void free_mem_from_field(field &fld)
		{
			if (fld == nullptr)
			{
				message("Attempt to delete nullptr in free_mem_from_field()");
				return;
			}

			for (unsigned i = 0; i < y; ++i)
			{
				delete[] fld[i];
			}
			delete[] fld;

			fld = nullptr;
		}

		// Returns true if a cell is empty
		bool IsCell(const field &fld, const int lx, const int ly)
		{
			if (
				(lx > 0 && ly > 0) 
				&& 
				(lx < (int)x && ly < (int)y)
				&&
				(!((lx < 2 || lx > 4) && (ly < 2 || ly > 4)))
			   )
			{
				if (fld[(unsigned)lx][(unsigned)ly] == 0) return true;
			}
			return false;
		}
		
		// Returns true if a cell has a chip
		bool IsChip(const field &fld, const int lx, const int ly)
		{
			if (
				(lx > 0 && ly > 0) 
				&& 
				(lx < (int)x && ly < (int)y)
				&&
				(!((lx < 2 || lx > 4) && (ly < 2 || ly > 4)))
			   )
			{
				if (fld[(unsigned)lx][(unsigned)ly] == 1) return true;
			}

			return false;
		}
		
		// Returns a pointer on a list of all moves for the current field
		// or nullptr if moves doesn't exist
		std::list<move*> *get_all_moves(const field &fld)
		{
			std::list<move*> *buf = nullptr;

			try
			{
				buf = new std::list<move*>; 
				move* m = nullptr;
				for (int i = 0; (unsigned)i < x; ++i)
				{
					for (int j = 0; (unsigned)j < y; ++j)
					{
						if ((fld[i][j] == 1) && (!(((i < 2) || (i > 4)) && ((j < 2) || (j > 4)))))
						{
							if (IsCell(fld, i + 2, j))
							{
								if (IsChip(fld, i + 1, j))
								{
									m = new move();

									m->first.first = i;
									m->first.second = j;
									m->second.first = i + 2;
									m->second.second = j;

									buf->push_back(m);
								}
							}
							if (IsCell(fld, i - 2, j))
							{
								if (IsChip(fld, i - 1, j))
								{
									m = new move();

									m->first.first = i;
									m->first.second = j;
									m->second.first = i - 2;
									m->second.second = j;

									buf->push_back(m);
								}
							}
							if (IsCell(fld, i, j + 2))
							{
								if (IsChip(fld, i, j + 1))
								{
									m = new move();

									m->first.first = i;
									m->first.second = j;
									m->second.first = i;
									m->second.second = j + 2;

									buf->push_back(m);
								}
							}
							if (IsCell(fld, i, j - 2))
							{
								if (IsChip(fld, i, j - 1))
								{
									m = new move();

									m->first.first = i;
									m->first.second = j;
									m->second.first = i;
									m->second.second = j - 2;

									buf->push_back(m);
								}
							}
						}
					}
				}

				if (buf->size() == 0) 
				{
					delete buf;
					buf = nullptr;
				}
			
			}
			catch (std::bad_alloc)
			{
				delete buf;
				buf = nullptr;
				message("Memory out in get_all_moves()");
			}

			return buf;

		}//*/
		
		// To make a move
		field make_move(field fld, const move &mv)
		{
			if (fld == nullptr)
			{
				message("Attempt to move on empty field in make_move()");
				return fld;
			}

			if (mv.first.first != mv.second.first)
			{
				if (mv.first.first < mv.second.first)
				{
					fld[mv.first.first + 1][mv.second.second] = 0;
				}
				else 
					fld[mv.first.first - 1][mv.second.second] = 0;

			}
			else if (mv.first.second != mv.second.second)
			{
				if (mv.first.second < mv.second.second)
				{
					fld[mv.first.first][mv.first.second + 1] = 0;
				}
				else 
					fld[mv.first.first][mv.first.second - 1] = 0;
			}
			else
			{
				message("Move is incorrect, error in get_all_moves()");
				return fld;
			}

			fld[mv.first.first][mv.first.second] = 0;
			fld[mv.second.first][mv.second.second] = 1;

			return fld;
		}
	
		// Recursive passage all the moves
		void bruteforce(field fld)
		{
			static bool display = false;
			static int lvl = 33;
			static time_t counter = 0;   // Num of checked field

			++counter;

			// Num 7000 is empirical
			// Once we get the conclusion of the 7000, it allows the processor
			// to be optimally loaded, and we see a progress
			if ((counter % 7000) == 0)
			{
				display = true;
			}

			if ( counter > 33 )
			{
				int ibuf = path_to_win.size();
				if (lvl > ibuf) lvl = ibuf;
			}

			std::list<move*> *b = get_all_moves(fld); 
			
			step buf;

			if (b != nullptr)
			{
				buf = step(fld, b);
				path_to_win.push_back(fld);
			}
			else 
			{
				int res = IsWin(fld);
				path_to_win.push_back(fld);

				if (display == true)
				{
					system("cls");
					std::cout << "Min level: " << lvl << "n<" 
						<< counter << '>' << "nCurrent result:n" << fld << std::endl;
					display = false;
				}

				if (res == win_condition)
				{
					std::cout << "Num of checked fields: " << fld_buf.size() <<
						"nSize of the path_to_win: " << path_to_win.size()  << std::endl;
					
					std::ofstream winpath_to_win("path_to_win.txt");
					if (winpath_to_win)
					{
						for (std::list<field>::const_iterator it = path_to_win.begin(); it != path_to_win.end(); ++it)
						{
							winpath_to_win << (*it) << std::endl;
						}
						winpath_to_win.close();
					}
					for (std::list<field>::const_iterator it = path_to_win.begin(); it != path_to_win.end(); ++it)
					{
						std::cout << (*it) << std::endl;
					}

					system("pause");
				}
				path_to_win.pop_back();
				return;
			}
		
			field fwithmove = nullptr;
			for (
				std::list<move*>::iterator it = buf.second->begin();
				it != buf.second->end();
				fwithmove = nullptr, buf.second->pop_front(), it = buf.second->begin()
				)
			{
				fwithmove = copy_field(fwithmove, buf.first);
				// Make move in copy of the buf.first field,
				// buf.first field not changed and use to copy in next iteration
				make_move(fwithmove, *(*it));
				
				Field *f = new Field(fwithmove);

				if (fld_buf.count(*f)) 
				{
					free_mem_from_field(fwithmove);
					delete (*it);
					continue;
				}
				else
					fld_buf.insert(*f);

				delete f;

				bruteforce(fwithmove);
				free_mem_from_field(fwithmove); // Free alloc memory for the fwithmove field, where we did move
				delete (*it);                   // Free memory from under "move" in list<move*> which we did
			}

			path_to_win.pop_back();
			delete buf.second;
		}

	public: 
		China_Checkers_Hack(const int _x = 7, const int _y = 7, const int wincondition = 1) : win_condition(wincondition)
		{
			x = _x;
			y = _y;

			field main_field;

			if ((main_field = alloc_mem_for_field()) != nullptr)
			{
				init_field(main_field);
				bruteforce(main_field);
				free_mem_from_field(main_field);
			}
			else
				message("Memory out, your computer gonna update RAM!");
		}
		~China_Checkers_Hack()
		{
			for (std::list<field>::iterator it = path_to_win.begin(); it != path_to_win.end(); ++it)
			{
				free_mem_from_field(*it);
			}
		}
	};
}

int main(int argc, char* argv[])
{
	China_Checkers::China_Checkers_Hack bruteforce;
	system("pause");
	return 0;
}

* * 1 1 1 * *
* * 1 0 1 * *
1 1 1 0 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
* * 1 1 1 * *
* * 1 1 1 * *

* * 1 1 1 * *
* * 1 0 1 * *
1 0 0 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
* * 1 1 1 * *
* * 1 1 1 * *

* * 1 1 1 * *
* * 1 0 1 * *
1 1 0 1 1 1 1
1 0 1 1 1 1 1
1 0 1 1 1 1 1
* * 1 1 1 * *
* * 1 1 1 * *

* * 1 1 1 * *
* * 1 0 1 * *
0 0 1 1 1 1 1
1 0 1 1 1 1 1
1 0 1 1 1 1 1
* * 1 1 1 * *
* * 1 1 1 * *

* * 1 1 1 * *
* * 1 0 1 * *
0 1 0 0 1 1 1
1 0 1 1 1 1 1
1 0 1 1 1 1 1
* * 1 1 1 * *
* * 1 1 1 * *

* * 0 1 1 * *
* * 0 0 1 * *
0 1 1 0 1 1 1
1 0 1 1 1 1 1
1 0 1 1 1 1 1
* * 1 1 1 * *
* * 1 1 1 * *

* * 0 1 1 * *
* * 0 0 1 * *
0 0 0 1 1 1 1
1 0 1 1 1 1 1
1 0 1 1 1 1 1
* * 1 1 1 * *
* * 1 1 1 * *

* * 0 1 1 * *
* * 0 0 1 * *
0 0 0 1 1 1 1
1 1 0 0 1 1 1
1 0 1 1 1 1 1
* * 1 1 1 * *
* * 1 1 1 * *

* * 0 1 1 * *
* * 0 0 1 * *
0 0 0 1 1 1 1
0 0 1 0 1 1 1
1 0 1 1 1 1 1
* * 1 1 1 * *
* * 1 1 1 * *

* * 0 1 1 * *
* * 0 0 1 * *
0 0 0 1 1 1 1
0 0 1 0 1 1 1
1 1 0 0 1 1 1
* * 1 1 1 * *
* * 1 1 1 * *

* * 0 1 1 * *
* * 0 0 1 * *
0 0 0 1 1 1 1
0 0 1 0 1 1 1
0 0 1 0 1 1 1
* * 1 1 1 * *
* * 1 1 1 * *

* * 0 1 1 * *
* * 0 0 1 * *
0 0 0 1 1 1 1
0 0 1 1 0 0 1
0 0 1 0 1 1 1
* * 1 1 1 * *
* * 1 1 1 * *

* * 0 1 1 * *
* * 0 1 1 * *
0 0 0 0 1 1 1
0 0 1 0 0 0 1
0 0 1 0 1 1 1
* * 1 1 1 * *
* * 1 1 1 * *

* * 0 0 1 * *
* * 0 0 1 * *
0 0 0 1 1 1 1
0 0 1 0 0 0 1
0 0 1 0 1 1 1
* * 1 1 1 * *
* * 1 1 1 * *

* * 0 0 1 * *
* * 0 0 0 * *
0 0 0 1 0 1 1
0 0 1 0 1 0 1
0 0 1 0 1 1 1
* * 1 1 1 * *
* * 1 1 1 * *

* * 0 0 1 * *
* * 0 0 0 * *
0 0 0 1 1 0 0
0 0 1 0 1 0 1
0 0 1 0 1 1 1
* * 1 1 1 * *
* * 1 1 1 * *

* * 0 0 1 * *
* * 0 0 0 * *
0 0 0 0 0 1 0
0 0 1 0 1 0 1
0 0 1 0 1 1 1
* * 1 1 1 * *
* * 1 1 1 * *

* * 0 0 1 * *
* * 0 0 0 * *
0 0 0 0 0 1 1
0 0 1 0 1 0 0
0 0 1 0 1 1 0
* * 1 1 1 * *
* * 1 1 1 * *

* * 0 0 1 * *
* * 0 0 0 * *
0 0 0 0 1 0 0
0 0 1 0 1 0 0
0 0 1 0 1 1 0
* * 1 1 1 * *
* * 1 1 1 * *

* * 0 0 1 * *
* * 0 0 1 * *
0 0 0 0 0 0 0
0 0 1 0 0 0 0
0 0 1 0 1 1 0
* * 1 1 1 * *
* * 1 1 1 * *

* * 0 0 0 * *
* * 0 0 0 * *
0 0 0 0 1 0 0
0 0 1 0 0 0 0
0 0 1 0 1 1 0
* * 1 1 1 * *
* * 1 1 1 * *

* * 0 0 0 * *
* * 0 0 0 * *
0 0 0 0 1 0 0
0 0 1 0 1 0 0
0 0 1 0 0 1 0
* * 1 1 0 * *
* * 1 1 1 * *

* * 0 0 0 * *
* * 0 0 0 * *
0 0 0 0 0 0 0
0 0 1 0 0 0 0
0 0 1 0 1 1 0
* * 1 1 0 * *
* * 1 1 1 * *

* * 0 0 0 * *
* * 0 0 0 * *
0 0 0 0 0 0 0
0 0 1 0 0 0 0
0 0 1 1 0 0 0
* * 1 1 0 * *
* * 1 1 1 * *

* * 0 0 0 * *
* * 0 0 0 * *
0 0 0 0 0 0 0
0 0 1 0 0 0 0
0 1 0 0 0 0 0
* * 1 1 0 * *
* * 1 1 1 * *

* * 0 0 0 * *
* * 0 0 0 * *
0 0 0 0 0 0 0
0 0 1 0 0 0 0
0 1 1 0 0 0 0
* * 0 1 0 * *
* * 0 1 1 * *

* * 0 0 0 * *
* * 0 0 0 * *
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 1 0 0 0 0 0
* * 1 1 0 * *
* * 0 1 1 * *

* * 0 0 0 * *
* * 0 0 0 * *
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 1 0 0 0 0 0
* * 1 1 0 * *
* * 1 0 0 * *

* * 0 0 0 * *
* * 0 0 0 * *
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 1 1 0 0 0 0
* * 0 1 0 * *
* * 0 0 0 * *

* * 0 0 0 * *
* * 0 0 0 * *
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 1 0 0 0
* * 0 1 0 * *
* * 0 0 0 * *

* * 0 0 0 * *
* * 0 0 0 * *
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
* * 0 0 0 * *
* * 0 1 0 * *