Microsoft Puzzle Box Solver

blocks.cc

// g++ -std=c++11 -O3 blocks.cc -o blocks
#include <iostream>
#include <vector>
#include <bitset>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <cstdint>
#include <sstream>
#include <string>

const int MAX_DEPTH = 100;
typedef int block_id;
typedef uint32_t block;
typedef uint64_t offset_type;
typedef int depth_type;

block blocks[6] = {
	0b1000000110010001,
	0b1000000111001011,
	0b1100000111001011,
	0b1000001110011111,
	0b1100001111100111,
	0b1110000111111011,
};

static inline uint8_t reverse(uint8_t b)
{
	return ((b * 0x0202020202ULL & 0x010884422010ULL) % 1023);
}

static inline uint32_t flip(uint32_t u)
{
	return (reverse(u & 0xff) << 8) | reverse(u >> 8);
}

static inline bool block_ij(block b, int i, int j)
{
	return (((b >> (8*i)) & 0xff) >> j) & 1;
}

static inline int8_t &offset_b(offset_type &offsets, int b)
{
	int8_t *p = reinterpret_cast<int8_t*>(&offsets);
	return p[b];
}

bool testOccupancy(const std::vector<block> &shapes, offset_type offsets)
{
	int8_t occupancy[8][8] = {false};
	for (block_id b: {0, 1, 2})
		for (int i = 0; i < 2; i++)
			for (int j = 0; j < 8; j++) {
				int coords_x = 1+2*b+i;
				int coords_y = j+offset_b(offsets, b);
				if (coords_x < 0 || coords_x >= 8 || coords_y < 0 || coords_y >= 8)
					continue;
				if (block_ij(shapes[b], i, j)) {
					if (occupancy[coords_x][coords_y])
						return false;
					occupancy[coords_x][coords_y] = 1;
				}
			}
	for (block_id b: {3, 4, 5})
		for (int i = 0; i < 2; i++)
			for (int j = 0; j < 8; j++) {
				int coords_x = j+offset_b(offsets, b);
				int coords_y = 1+2*(b-3)+i;
				if (coords_x < 0 || coords_x >= 8 || coords_y < 0 || coords_y >= 8)
					continue;
				if (block_ij(shapes[b], i, j)) {
					if (occupancy[coords_x][coords_y])
						return false;
					occupancy[coords_x][coords_y] = 2;
				}
			}
	return true;
}

static inline bool isOutside(int8_t offset)
{
	return offset <= -8 || offset >= 8;
}

static inline int outsideNumber(offset_type offsets)
{
	int ret = 0;
	for (block_id i = 0; i < 6; i++)
		ret += isOutside(offset_b(offsets, i));
	return ret;
}

void printSteps(offset_type offsets, const std::unordered_map<offset_type, offset_type> &visited, std::string &solution, int &steps)
{
	std::stringstream ss;
	steps = 0;

	block_id last = -1;
	ss << "Initial positions: ";
	for (int i = 0; i < 6; i++)
		ss << (int)offset_b(offsets, i) << " ";
	ss << std::endl;

	offset_type curr, next = offsets;
	for (;;) {
		curr = next;
		next = visited.find(curr)->second;
		if (curr == next)
			break;

		block_id diff = -1;
		offset_type diffval = curr ^ next;
		for (block_id b = 0; b < 6; b++)
			if (offset_b(diffval, b))
				diff = b;

		if (last != diff) {
			if (last != -1)
				ss << " to " << (int)offset_b(curr, last) << std::endl;
			ss << "move block " << (char)('A' + diff) << " from " << (int)offset_b(curr, diff);
			steps++;
		}
		last = diff;
	}
	ss << " to 0";
	solution = ss.str();
}

bool searchMovement(const std::vector<block> &shapes, const int max_depth, std::string &solution, int &steps)
{
	std::queue<std::pair<offset_type, depth_type>> tovisit;
	std::unordered_map<offset_type, offset_type> visited;

	tovisit.push(std::make_pair(0, 0));
	visited[0] = 0;

	while (tovisit.size()) {
		const auto &pair = tovisit.front();
		auto offsets = pair.first;
		const auto depth = pair.second;
		tovisit.pop();

		if (depth >= max_depth)
			continue;

		for (block_id b = 0; b < 6; b++) {
			if (isOutside(offset_b(offsets, b)))
				continue;
			for (int movement: {1, -1}) {
				offset_type new_offsets = offsets;
				offset_b(new_offsets, b) += movement;

				if (!testOccupancy(shapes, new_offsets))
					continue;
				if (visited.count(new_offsets))
					continue;

				if (outsideNumber(new_offsets) >= 3) {
					printSteps(offsets, visited, solution, steps);
					return true;
				}

				tovisit.push(std::make_pair(new_offsets, depth+1));
				visited[new_offsets] = offsets;
			}
		}
	}
	return false;
}

bool searchMovementAtDepth(const int max_depth, std::string& min_solution, std::vector<block> &min_shapes)
{
	int min_steps = -1;

	std::vector<block_id> p{0, 1, 2, 3, 4, 5};
	do {
		std::vector<block> shapes_permuted(6);
		for (block_id i = 0; i < 6; i++)
			shapes_permuted[i] = blocks[p[i]];
		
		for (int flip_bits = 0; flip_bits < 64; flip_bits++) {
			std::bitset<6> flips(flip_bits);
			std::vector<block> shapes(shapes_permuted);
			for (block_id i = 0; i < 6; i++)
				if (flips[i])
					shapes[i] = flip(shapes[i]);

			if (!testOccupancy(shapes, 0))
				continue;

			std::string solution;
			int steps;
			if (!searchMovement(shapes, max_depth, solution, steps))
				continue;
			if (min_steps == -1 || steps < min_steps) {
				min_steps = steps;
				min_solution = solution;
			}

			min_shapes = shapes;
		}
	} while (std::next_permutation(p.begin(), p.end()));

	return min_steps != -1;
}

static void print_block(block b, bool vertical)
{
	std::bitset<16> shapes(b);
	for (int i = 0; i < 16; i++) {
		int j;
		if (vertical)
			j = (i % 2 ? 15 - i/2 : 7 - i/2);
		else
			j = (i < 8 ? i + 8 : i - 8);
			
		std::cout << (shapes[j] ? '#' : '.');
		if (vertical && i % 2 == 1)
			std::cout << std::endl;
		if (!vertical && i % 8 == 7)
			std::cout << std::endl;
	}
}

int main()
{
	std::string min_solution;
	std::vector<block> min_shapes;

	int depth;
	for (depth = 1; depth < MAX_DEPTH; depth++)
		if (searchMovementAtDepth(depth, min_solution, min_shapes))
			break;

	if (depth == MAX_DEPTH)
		return 0;

	for (block_id b = 0; b < 6; b++) {
		std::cout << "block " << (char)('A' + b) << ":" << std::endl;
		print_block(min_shapes[b], b < 3);
	}
	std::cout << min_solution << std::endl;
	return 0;
}