Konfigurace na vyzkoušení, seřazené podle vzdálenosti:

Výchozí kód

#include <vector>
#include <cstdio>

using State = std::vector<int>;
const std::vector<int> movements{-4, -1, 1, 4};

int find_hole(const State &state)
{
	for (int i=0; i<16; ++i) {
		if (state[i] == 0) {
			return i;
		}
	}
	throw 1;
}

bool modify(State &state, int move)
{
	int hole = find_hole(state);
	if (hole + move < 0 or hole + move >= 16) {
		return false;
	} else if ((move == -1 and hole % 4 == 0) or (move == 1 and hole % 4 == 3)) {
		return false;
	} else {
		state[hole] = state[hole + move];
		state[hole + move] = 0;
		return true;
	}
}

bool solve(const State &start, const State &end, int distance)
{
	if (distance == 0) {
		return start == end;
	} else {
		for (int move : movements) {
			State step = start;
			if (modify(step, move) and solve(step, end, distance - 1)) {
				printf("move %i\n", step[find_hole(start)]);
				return true;
			}
		}
		return false;
	}
}

int main()
{
    State start = {0, 2, 4, 3, 5, 6, 1, 7, 8, 9, 10, 11, 12, 13, 14, 15};
    State end = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
	for (int distance=0; distance<80; ++distance) {
		printf("distance %i...\n", distance);
		if (solve(start, end, distance)) {
			printf("Solved.\n");
			return 0;
		}
	}
	printf("Failed.\n");
	return 1;
}

Tabulka

Vyrobíte ji jako Table tabulka; Pokud funkce tabulka.add(stav) vrací true, stav si nepamatuje a má cenu ho prozkoušet.

class Table
{
	using Code = uint64_t;
	std::array<Code, 65536> data;

	Code code(const State &state)
	{
		Code result = 0;
		for (int value : state) {
			result = (result << 4) | Code(value);
		}
		return result;
	}

	int hash(Code c)
	{
		int result = (c) + (c << 16) + (c << 32) + (c << 48);
		return result % data.size();
	}

public:
	Table()
	{
		std::fill(data.begin(), data.end(), 0);
	}

	bool add(const State &state)
	{
		Code c = code(state);
		Code &cell = data[hash(c)];
		if (cell == c) {
			return false;
		} else {
			cell = c;
			return true;
		}
	}
};

Odhad složitosti

Odhadovací funkci vyrobíte jako SwapDistance odhad(cilovy_stav); Můžete ji pak prostě zavolat: odhad(stav) vrátí číslo.

class SwapDistance
{
	using Code = uint64_t;
	using uchar = unsigned char;
    struct Bitarray {
        unsigned a : 2;
        unsigned b : 2;
        unsigned c : 2;
        unsigned d : 2;
        void swap_back(Bitarray &other, uchar index) {
            uchar tmp = d;
            switch (index) {
            case 0:
                d = other.a;
                other.a = other.d;
                break;
            case 1:
                d = other.b;
                other.b = other.d;
                break;
            case 2:
                d = other.c;
                other.c = other.d;
                break;
            default:
                d = other.d;
            }
            other.d = tmp;
        }
        Code encode() const {
            const uchar table[] = {0, 1, 2, 3, 1, 4, 5, 6, 2, 5, 7, 8, 3, 6, 8, 9, 1, 4, 5, 6, 4, 10, 11, 12, 5, 11, 13, 14, 6, 12, 14, 15, 2, 5, 7, 8, 5, 11, 13, 14, 7, 13, 16, 17, 8, 14, 17, 18, 3, 6, 8, 9, 6, 12, 14, 15, 8, 14, 17, 18, 9, 15, 18, 19, 1, 4, 5, 6, 4, 10, 11, 12, 5, 11, 13, 14, 6, 12, 14, 15, 4, 10, 11, 12, 10, 20, 21, 22, 11, 21, 23, 24, 12, 22, 24, 25, 5, 11, 13, 14, 11, 21, 23, 24, 13, 23, 26, 27, 14, 24, 27, 28, 6, 12, 14, 15, 12, 22, 24, 25, 14, 24, 27, 28, 15, 25, 28, 29, 2, 5, 7, 8, 5, 11, 13, 14, 7, 13, 16, 17, 8, 14, 17, 18, 5, 11, 13, 14, 11, 21, 23, 24, 13, 23, 26, 27, 14, 24, 27, 28, 7, 13, 16, 17, 13, 23, 26, 27, 16, 26, 30, 31, 17, 27, 31, 32, 8, 14, 17, 18, 14, 24, 27, 28, 17, 27, 31, 32, 18, 28, 32, 33, 3, 6, 8, 9, 6, 12, 14, 15, 8, 14, 17, 18, 9, 15, 18, 19, 6, 12, 14, 15, 12, 22, 24, 25, 14, 24, 27, 28, 15, 25, 28, 29, 8, 14, 17, 18, 14, 24, 27, 28, 17, 27, 31, 32, 18, 28, 32, 33, 9, 15, 18, 19, 15, 25, 28, 29, 18, 28, 32, 33, 19, 29, 33, 34};
            return table[(a<<6) | (b<<4) | (c<<2) | d];
        }
    };
    struct Hash {
        Bitarray val[4];
        uchar zero;
        std::vector<Hash> variants() const {
            std::vector<Hash> result;
            std::vector<std::vector<int>> steps = {{1}, {-1, 1}, {-1, 1}, {-1}};
            for (int i=0; i<4; i++) {
                for (int step : steps[zero]) {
                    result.push_back(*this);
                    Hash &variant = result.back();
                    variant.val[zero].swap_back(variant.val[zero + step], i);
                    variant.zero = zero + step;
                }
            }
            return result;
        }
        const static Code max_encode = 4 * 64 * 64 * 64;
        Code encode() const {
            Code result = zero;
            result = (result * 64) | val[0].encode();
            result = (result * 64) | val[1].encode();
            result = (result * 64) | val[2].encode();
            return result;
        }
    };
    std::vector<uchar> distance;
    uchar* ddata;
    static uchar correct_row(Code value) {
        return value / 4;
    }
    static uchar correct_col(Code value) {
        return value % 4;
    }
    static Hash row_hash(const State &state) {
        Hash result;
        for (int row=0; row<4; row++) {
            Bitarray &ldata = result.val[row];
            ldata.a = correct_row(state[4*row + 0]);
            ldata.b = correct_row(state[4*row + 1]);
            ldata.c = correct_row(state[4*row + 2]);
            ldata.d = correct_row(state[4*row + 3]);
        }
        result.zero = find_hole(state) / 4;
        return result;
    }
    static Hash col_hash(const State &state) {
        Hash result;
        for (int col=0; col<4; col++) {
            Bitarray &ldata = result.val[col];
            ldata.a = correct_col(state[0 + col]);
            ldata.b = correct_col(state[4 + col]);
            ldata.c = correct_col(state[8 + col]);
            ldata.d = correct_col(state[12 + col]);
        }
        result.zero = find_hole(state) % 4;
        return result;
    }
public:
    SwapDistance(const State end) : distance(Hash::max_encode, 255) {
        ddata = distance.data();
        int level = 0;
        std::vector<Hash> frontier{row_hash(end)};
        ddata[row_hash(end).encode()] = level;
        while (not frontier.empty()) {
			printf("level %i, %lu items\n", level, frontier.size());
            level += 1;
            std::vector<Hash> new_frontier;
            for (Hash h : frontier) {
                for (Hash g : h.variants()) {
                    if (ddata[g.encode()] == 255) {
                        ddata[g.encode()] = level;
                        new_frontier.emplace_back(std::move(g));
                    }
                }
            }
            std::swap(new_frontier, frontier);
        }
    }
    uchar operator() (const State &s) const {
        return ddata[row_hash(s).encode()] + ddata[col_hash(s).encode()];
    }
};