minesweeper-bot/main.c

/*
 * Copyright (c) Camden Dixie O'Brien
 * SPDX-License-Identifier: AGPL-3.0-only
 */

#include "puzz.h"

#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>

#define NRUNS 10000
#define MAX_ADJ 8
#define QUEUE_MAX 128

typedef enum {
	MADE_INFERENCE,
	FOUND_NOTHING,
	FOUND_CONTRADICTION,
} update_res_t;

typedef struct {
	int x, y;
} coord_t;

typedef struct {
	coord_t buf[QUEUE_MAX], *start, *end;
} queue_t;

typedef struct {
	int mines, unknown;
	queue_t queue;
	puzz_t field;
} state_t;

static bool empty(const queue_t *queue)
{
	return queue->start == queue->end;
}

static void enqueue(queue_t *queue, int x, int y)
{
	queue->end->x = x;
	queue->end->y = y;

	++queue->end;
	if (queue->end == queue->buf + QUEUE_MAX)
		queue->end = queue->buf;
	assert(queue->end != queue->start);
}

static void dequeue(queue_t *queue, int *x_out, int *y_out)
{
	assert(queue->start != queue->end);
	*x_out = queue->start->x;
	*y_out = queue->start->y;

	++queue->start;
	if (queue->start == queue->buf + QUEUE_MAX)
		queue->start = queue->buf;
}

static void init(state_t *state)
{
	state->mines = 0;
	state->unknown = WIDTH * HEIGHT;
	state->queue.start = state->queue.end = state->queue.buf;
	memset(state->field, UNKNOWN, sizeof(puzz_t));
}

static void dup(state_t *orig, state_t *copy)
{
	memcpy(copy, orig, sizeof(state_t));
	const int startpos = orig->queue.start - orig->queue.buf;
	const int endpos = orig->queue.end - orig->queue.buf;
	copy->queue.start = copy->queue.buf + startpos;
	copy->queue.end = copy->queue.buf + endpos;
}

static void setadj(puzz_t field, int x, int y, uint8_t from, uint8_t to)
{
	FORADJ(x, y, xi, yi)
	field[xi][yi] = field[xi][yi] == from ? to : field[xi][yi];
}

static update_res_t update(state_t *state)
{
	state->mines = state->unknown = 0;

	for (int y = 0; y < HEIGHT; ++y) {
		for (int x = 0; x < WIDTH; ++x) {
			state->mines += state->field[x][y] == MINE ? 1 : 0;
			state->unknown += state->field[x][y] == UNKNOWN ? 1 : 0;
		}
	}

	if (state->mines > NMINES || state->mines + state->unknown < NMINES)
		return FOUND_CONTRADICTION;

	for (int y = 0; y < HEIGHT; ++y) {
		for (int x = 0; x < WIDTH; ++x) {
			if (state->field[x][y] == UNKNOWN || state->field[x][y] == MINE
			    || state->field[x][y] == SAFE)
				continue;

			const int mines = countadj(state->field, x, y, MINE);
			if (mines > state->field[x][y])
				return FOUND_CONTRADICTION;

			const int unknowns = countadj(state->field, x, y, UNKNOWN);
			if (unknowns == 0)
				continue;

			if (mines + unknowns < state->field[x][y])
				return FOUND_CONTRADICTION;

			if (mines + unknowns == state->field[x][y]) {
				setadj(state->field, x, y, UNKNOWN, MINE);
				return MADE_INFERENCE;
			}

			if (mines == state->field[x][y]) {
				FORADJ(x, y, xi, yi)
				{
					if (state->field[xi][yi] == UNKNOWN)
						enqueue(&state->queue, xi, yi);
				}
				setadj(state->field, x, y, UNKNOWN, SAFE);
				return MADE_INFERENCE;
			}
		}
	}

	return FOUND_NOTHING;
}

static update_res_t search_at(state_t *state, int x, int y)
{
	update_res_t res;

	state_t with_mine;
	dup(state, &with_mine);
	with_mine.field[x][y] = MINE;
	do {
		if ((res = update(&with_mine)) == FOUND_CONTRADICTION) {
			state->field[x][y] = SAFE;
			enqueue(&state->queue, x, y);
			return MADE_INFERENCE;
		}
	} while (res == MADE_INFERENCE);

	state_t with_safe;
	dup(state, &with_safe);
	with_safe.field[x][y] = SAFE;
	do {
		if ((res = update(&with_safe)) == FOUND_CONTRADICTION) {
			state->field[x][y] = MINE;
			return MADE_INFERENCE;
		}
	} while (res == MADE_INFERENCE);

	for (int y = 0; y < HEIGHT; ++y) {
		for (int x = 0; x < WIDTH; ++x) {
			if (with_mine.field[x][y] == with_safe.field[x][y] &&
			    state->field[x][y] != with_mine.field[x][y]) {
				state->field[x][y] = with_mine.field[x][y];
				if (state->field[x][y] == SAFE)
					enqueue(&state->queue, x, y);
				res = MADE_INFERENCE;
			}
		}
	}

	return res;
}

static update_res_t search(state_t *state)
{
	for (int y = 0; y < HEIGHT; ++y) {
		for (int x = 0; x < WIDTH; ++x) {
			if (state->field[x][y] != UNKNOWN)
				continue;
			if (countadj(state->field, x, y, UNKNOWN) != MAX_ADJ) {
				update_res_t res = search_at(state, x, y);
				if (res != FOUND_NOTHING)
					return res;
			}
		}
	}
	return FOUND_NOTHING;
}

static status_t solve(int *probes_out)
{
	state_t state;
	init(&state);

	enqueue(&state.queue, rand() % WIDTH, rand() % HEIGHT);

	int probes = 0;
	do {
		while (!empty(&state.queue)) {
			int x, y;
			dequeue(&state.queue, &x, &y);
			if (state.field[x][y] != SAFE && state.field[x][y] != UNKNOWN)
				continue;
			++probes;
			if (probe(x, y, state.field) == DEAD) {
				*probes_out = probes;
				return DEAD;
			}
		}

		update_res_t res;
		do {
			res = update(&state);
			if (res == FOUND_NOTHING)
				res = search(&state);
		} while (res == MADE_INFERENCE);

		if (check(state.field) != OK) {
			printf("Incorrect inference!\n");
			print(state.field);
			printsoln();
			return INCORRECT;
		}

		if (empty(&state.queue)) {
			int x, y;
			do {
				x = rand() % WIDTH;
				y = rand() % HEIGHT;
			} while (state.field[x][y] == MINE);
			enqueue(&state.queue, x, y);
		}
	} while (state.mines < NMINES || state.unknown > 0);

	*probes_out = probes;
	return OK;
}

int main(void)
{
	struct timeval tv;
	if (gettimeofday(&tv, NULL) != 0) {
		perror("Failed to get time");
		exit(1);
	}
	srand(tv.tv_usec);

	int nsolved = 0, nfirst = 0, nincorrect = 0, probes;
	for (int i = 0; i < NRUNS; ++i) {
		gen();
		switch (solve(&probes)) {
		case DEAD:
			if (probes == 1)
				++nfirst;
			break;
		case OK:
			++nsolved;
			break;
		case INCORRECT:
			++nincorrect;
			break;
		}
	}

	if (nincorrect > 0) {
		printf(
		    "Fail: %d incorrect! (%0.1f%%)\n", nincorrect,
		    (double)nincorrect / NRUNS);
		return 1;
	}

	const double solved_prop = (double)nsolved / NRUNS;
	const double first_prop = (double)nfirst / NRUNS;
	const double solved_safe_start_prop = (double)nsolved / (NRUNS - nfirst);
	printf("Solved %d (%0.1f%%)\n", nsolved, 100 * solved_prop);
	printf("%d died on first turn (%0.1f%%)\n", nfirst, 100 * first_prop);
	printf("%0.1f%% solved on safe start\n", 100 * solved_safe_start_prop);

	return 0;
}