Auto Sweeper

main.cpp

#include<iostream>
#include<functional>
#include<algorithm>
#include<array>
#include<optional>
#include<random>
#include<sstream>
#include<queue>

constexpr int width = 9;
constexpr int height = 9;
constexpr int count = std::min(width*height - 9, 10);

template<class T, std::size_t Dim1, std::size_t Dim2>using dual_array = std::array<std::array<T, Dim2>, Dim1>;
typedef dual_array<std::optional<int>, width, height> field_t;
typedef dual_array<bool, width, height> mines_t;

template<class Engine>mines_t make_field(std::size_t sx, std::size_t sy, Engine&& engine)
{
	std::uniform_int_distribution<int> xr(0, width - 1);
	std::uniform_int_distribution<int> yr(0, height - 1);
	mines_t field{};
	for (int i = 0; i < count; ++i)
	{
		while (true)
		{
			auto x = xr(engine);
			auto y = yr(engine);
			if (sx - 1 <= x&&x <= sx + 1 && sy - 1 <= y&&y <= sy + 1)
			{
				continue;
			}
			if (field[x][y])
			{
				continue;
			}
			field[x][y] = true;
			break;
		}
	}
	return field;
}

struct receive_data_t
{
	int number;
	std::size_t x;
	std::size_t y;
};
constexpr std::pair<int, int> rotate[] = { {-1,-1},{0,-1},{1,-1},{1,0},{1,1},{0,1},{-1,1},{-1,0} };

constexpr bool range_check(std::size_t x, std::size_t y)
{
	return 0 <= x&&x < width && 0 <= y&&y < height;
}

template<class Solver>struct test_engine
{
	Solver solver;
	bool run(std::size_t xs, std::size_t ys)
	{
		int rest = width*height - count;
		auto mines = make_field(xs, ys, solver.random);
		field_t numbers{};
		open(mines, numbers, xs, ys, rest);
		std::string dummy;
		while (rest != 0)
		{
			print(numbers);
			std::getline(std::cin, dummy);
			auto p = solver.send();
			if (open(mines, numbers, p.first, p.second, rest))
			{
				std::cout << "ゲームオーバー" << std::endl;
				print(numbers);
				std::getline(std::cin, dummy);
				return false;
			}
		}
		std::cout << "ゲームクリア" << std::endl;
		print(numbers);
		std::getline(std::cin, dummy);
		return true;
	}

	void print(field_t const& numbers)
	{
		for (int y = 0; y < height; ++y)
		{
			for (int x = 0; x < width; ++x)
			{
				if (!numbers[x][y])
				{
					std::cout << "[ ]";
				}
				else if (*numbers[x][y] == 0)
				{
					std::cout << "   ";
				}
				else
				{
					std::cout << " " << *numbers[x][y] << " ";
				}
			}
			std::cout << std::endl;
		}
	}

	bool open(mines_t& mines, field_t& numbers, std::size_t x, std::size_t y, int& rest)
	{
		if (numbers[x][y])
		{
			return false;
		}
		if (mines[x][y])
		{
			return true;
		}
		int c = 0;
		for (auto const& p : rotate)
		{
			if (range_check(x + p.first, y + p.second) &&
				mines[x + p.first][y + p.second])
			{
				++c;
			}
		}
		numbers[x][y] = c;
		solver.receive(receive_data_t{ c,x,y });
		--rest;
		if (c == 0)
		{
			for (auto const& p : rotate)
			{
				if (range_check(x + p.first, y + p.second))
				{
					open(mines, numbers, x + p.first, y + p.second, rest);
				}
			}
		}
		return false;
	}
};
template<class Solver>struct checker_engine
{
	Solver solver;
	bool run(std::size_t xs, std::size_t ys)
	{
		int rest = width*height - count;
		auto mines = make_field(xs, ys, solver.random);
		field_t numbers{};
		open(mines, numbers, xs, ys, rest);
		while (rest != 0)
		{
			auto p = solver.send();
			if (open(mines, numbers, p.first, p.second, rest))
			{
				return false;
			}
		}
		return true;
	}

	bool open(mines_t& mines, field_t& numbers, std::size_t x, std::size_t y, int& rest)
	{
		if (numbers[x][y])
		{
			return false;
		}
		if (mines[x][y])
		{
			return true;
		}
		int c = 0;
		for (auto const& p : rotate)
		{
			if (range_check(x + p.first, y + p.second) &&
				mines[x + p.first][y + p.second])
			{
				++c;
			}
		}
		numbers[x][y] = c;
		solver.receive(receive_data_t{ c,x,y });
		--rest;
		if (c == 0)
		{
			for (auto const& p : rotate)
			{
				if (range_check(x + p.first, y + p.second))
				{
					open(mines, numbers, x + p.first, y + p.second, rest);
				}
			}
		}
		return false;
	}
};

struct beginner_solver
{
	dual_array<std::optional<int>, width, height> flags;
	std::mt19937 random;

	std::pair<std::size_t, std::size_t> send()
	{
	start:;
		for (int x = 0; x < width; ++x)
		{
			for (int y = 0; y < height; ++y)
			{
				if (!flags[x][y] || *flags[x][y] == -1)
				{
					continue;
				}
				auto n = *flags[x][y];
				auto r = 8 - n;
				for (auto p : rotate)
				{
					if (x + p.first < 0 || width <= x + p.first)
					{
						--r;
					}
					else if (y + p.second < 0 || height <= y + p.second)
					{
						--r;
					}
					else if (!flags[x + p.first][y + p.second])
					{

					}
					else if (*flags[x + p.first][y + p.second] == -1)
					{
						--n;
					}
					else
					{
						--r;
					}
				}
				if (n == 0)
				{
					for (auto p : rotate)
					{
						if (x + p.first < 0 || width <= x + p.first)
						{
							continue;
						}
						else if (y + p.second < 0 || height <= y + p.second)
						{
							continue;
						}
						else if (!flags[x + p.first][y + p.second])
						{
							return { x + p.first,y + p.second };
						}
					}
				}
				if (r == 0)
				{
					bool f = false;
					for (auto const& p : rotate)
					{
						if (x + p.first < 0 || width <= x + p.first)
						{
							continue;
						}
						else if (y + p.second < 0 || height <= y + p.second)
						{
							continue;
						}
						else if (!flags[x + p.first][y + p.second])
						{
							f = true;
							flags[x + p.first][y + p.second] = -1;
						}
					}
					if (f)
					{
						goto start;
					}
				}
			}
		}
		std::uniform_int_distribution<int> xr(0, width - 1);
		std::uniform_int_distribution<int> yr(0, height - 1);
		while (true)
		{
			auto x = xr(random);
			auto y = yr(random);
			if (!flags[x][y])
			{
				return { x,y };
			}
		}
	}
	void receive(receive_data_t const& data)
	{
		flags[data.x][data.y] = data.number;
	}
	void reset()
	{
		flags = dual_array<std::optional<int>, width, height>{};
	}
};

int main()
{
	std::priority_queue<std::pair<int, std::pair<int, int>>> ranking;
	checker_engine<beginner_solver> engine{ beginner_solver{{},std::mt19937{std::random_device()()}} };

	for (int x = 0; x < 5; ++x)
	{
		for (int y = x; y < 5; ++y)
		{
			int w = 0;
			for (int i = 0; i < 10000000; ++i)
			{
				engine.solver.reset();
				if (engine.run(x, y))
				{
					++w;
				}
			}
			ranking.emplace(std::make_pair(w, std::make_pair(x, y)));
			std::cout << "(" << x << "," << y << ")終了" << std::endl;
		}
	}
	for (int i = 0; i < 5; ++i)
	{
		auto top = ranking.top();
		ranking.pop();
		auto w = top.first;
		auto x = top.second.first;
		auto y = top.second.second;
		std::cout << i + 1 << ":(" << x << "," << y << ")-" << w << std::endl;
	}
}