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

в 15:04, , рубрики: c++, брутфорс, головоломка, рекурсия, метки: , ,

Предыстория

Чтобы летом держать мозг в тонусе я скачал себе сборник головоломок. По началу задания были довольно простыми и не особо требовательными к проявлению логики, но по ходу игры чувствовалось нарастающее усложнение.
В какой-то момент я застрял на головоломке под названием «Китайские шашки». Редкие потуги решить её своими силами не приносили особых плодов на протяжение долгого времени и в итоге я отложил свои муки с решением до лучших времен.
Закончилась зимняя сессия, а до начала учебы еще пара недель — чем не «лучшие времена»? Я заглянул в интернет, дабы проверить есть ли у данной головоломки вообще хоть какое-нибудь решение, и первые же результаты поискового запроса убедили меня в том, что оно действительно существует.
Я не стал подглядывать в прохождение, мне хотелось дойти до него своими силами — или самому решить, или написать программу, которая найдет мне это решение. Однако напрямую применить силу мозга мне так и не удалось, я явно упускал из виду что-то принципиально важное для нахождения решения.
— «Ну всё, пусть эта головоломка поговорит с моим многоядерным другом!» — пронеслось у меня в голове, и я сел за написание брутфорса.

Постановка задачи
Поле — 33 ячейки, 32 из которых заняты фишками. Цель — съесть максимально возможное количество фишек(должна остаться лишь одна). Есть можно только по вертикали и горизонтали таким образом:
Брутфорс головоломки «Китайские шашки»
Пример хода

Первая попытка решения
Первый брутфорс был написан без учета теории за пол-часа, его идея заключалась в рекурсивном спуске по дереву возможных ходов, с рандомным выбором каждого последующего хода.
Брутфорс головоломки «Китайские шашки»
Псевдо блок-схема первой версии

И всё это чудо вертелось в цикле. В первые 15 секунд он даже смог найти ход решения приводящий к 3 остающимся фишкам на поле, а в последующую минуту и к 2! Но радость была не долгой, ибо рандом, пусть даже псевдо, трудно предсказуем — за ночь работы он не смог более приблизиться к решению. Становилось очевидна потребность рассмотрения вопроса с теоретической точки зрения.

Немного теории
Если действующее игровое поле вытянуть в строку, то получится 33 разрядное двоичное число, где 1 соответствует ячейке с фишкой, а 0 пустой ячейке. Соответственно всего состояний у поля может быть не больше 2^33 — 2, так как по правилам поле не может стать полностью пустым(всегда остается хотя бы одна фишка), или полностью заполненным фишками(их дается 32 изначально и больше уже стать не может).
Это можно интерпретировать как то, что ходов у нас всего не более 8 589 934 590, что вполне перебираемо на домашнем компьютере. То есть нужно просто написать честный полный перебор.

Вторая попытка решения
Избавившись от рандомной составляющей алгоритм брутфорса принял следующий вид:
Брутфорс головоломки «Китайские шашки»
Псевдо блок-схема второй версии

Этот брутфорс написанный на C++ на всех известных мне оптимизациях в релиз-версии работал довольно резво, перебирая чуть ли не 200 000 ходов в секунду, а значит для полного перебора понадобилось бы (2^33 — 2) / (2 * 10^5) ≈ 12 часов. Но так как четыре варианта первого хода очевидно ведут к лишним повторениям, то мы делаем первый ход за программу, таким образом на 3/4 уменьшая количество ходов которые требуется перебрать(а значит и время работы). Программа занимала в оперативной памяти 2.6 МБ и довольно быстро перебрала 2 * 10^7 ходов и все бы ничего, но ответа до сих пор не было.
Самое веселье же было в том, что на этих двух миллиардах программа показывала что перебирает подветвь дерева всех возможных ходов которая образуется после 12 хода! Что-то тут не так, либо ошибка в брутфорсе, либо существуют такие различные ходы, которые приводят поле к одному состоянию, причем этих пересечений должно быть достаточно много.
Мои опасения подтвердились простейшей проверкой — разные ходы действительно могли приводить поле в одно и то же состояние.

Третья попытка решения
Значит нужно сохранять рассчитанные поля и при обнаружение повтора сразу сообщать, что их считать не нужно.
Брутфорс головоломки «Китайские шашки»
Псевдо блок-схема третьей версии с запоминанием рассчитанных полей

Только вот это дело оказалось весьма накладным, если хранить просчитанные поля в оперативной памяти, то получается в идеальном случае что нам потребуется 33 бита на одно поле, а их даже с учетом сделанного первого хода (2^33 — 2) / 4, то есть памяти понадобится на хранение всех просчитанных полей ((2^33 — 2) / 4) * 33) / (8 * 2^20) ≈ 8.5 ГБ, а у меня всего 4, из которых я могу дать программе лишь 2. Что же делать? Особенно если учесть, что 33 бита это теоретический минимум требуемый на игровое поле, а на практике их ведь постоянно нужно сравнивать, да и не как-то там, а побитово! Можно было поискать системные функции для побитового сравнения двух участков памяти, или попробовать сделать это ассемблерными вставками. Но все равно нужно ведь будет хранить еще и указатели на эти поля, то есть в 33 бита игрового поля + 4 байта указатель(на моей машине) на них + выравнивание структур в памяти — ну никак не уложиться даже с оперативкой в 16 ГБ. Можно было бы попробовать сделать хранение на диске, но тогда скорость перебора упала бы на непозволительный уровень…
В итоге было решено опробовать злосчастный std::vector bool для хранения рассчитанных полей и молиться о том, чтобы ход решения был найден до того, как иссякнет память.
Новый брутфорс перебирал около 7000 ходов в секунду, но этого оказалось вполне достаточно — по счастливому стечению обстоятельств я выловил аж 4 решения до того как выскочила плашка «Memory out». Память иссякла когда он перебрал пять миллионов ходов и находился при этом на подветви дерева всех возможных ходов которая образуется после 5 хода от начала игры.

Заключение
Вроде головоломка и решена своими силами, но недосказанность осталась. Решение вполне могло и не находится в перебранном мной диапазоне, тогда бы пришлось думать дольше, и возможно уже совсем в ином направление.
PS Перед публикацией нашел на хабре пост Применяем на практике знания, полученные на курсе MIT 6.00x (edx.org) часть которого повествовала о решение этой же задачи, но справедливости ради замечу что мы с автором того поста пошли разными путями.
PPS Возможно наличие ошибок и неточностей, буду признателен за поправки и советы.

Итоговый код брутфорса на C++

#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 * *

Автор: Whiteha

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js