Geekly Articles each Day
📜 ⬆️ ⬇️

The case of the maloksky safe


I think that many of those present here know the game Space Rangers . Also, I don’t think that I’m going to make a big mistake if I say that, to a large extent, this game owes its charm to the text quests that have actually been revived. Some of these quests, such as the Citadel or Ski Resort, may well be considered as independent games.

My attitude to text quests is twofold. On the one hand, they are very interesting and incredibly atmospheric. On the other hand, some of them are not easy to go through. Quest "Fifteen" immediately put me in a dead end. I do not solve all sorts of puzzles very well, so I decided to write a program that will find a solution for me.

So, according to the conditions of the assignment, we need to open the safe, which requires solving a puzzle, which painfully resembles the well-known game 15 .

image
')
Despite the similarities, there are two important differences that should be mentioned:

  1. The puzzle is required to solve for a limited number of moves.
  2. As you can see, the numbers on the chips are repeated.

The restriction on the number of moves, as will be shown below, will help us in solving the problem (I note that it is not necessary to search for the shortest solution, it is enough to find any solution not exceeding 59 moves). With the second item, things are not so simple. At first glance, it should simplify the decision, but it is not.

It is widely known that half of the possible positions in the “15” game have no solutions. In addition, for part of the positions, the minimum number of moves required for the decision may exceed the number of moves specified in the conditions of the task. Thus, if we start moving one of the paired chips out of place, we most likely will not be able to solve the puzzle. In order not to be confused with paired chips, it makes sense to renumber them in a unique way, reducing the puzzle to the classic game "15".

Since, according to the conditions of the assignment, there are 7 pairs of matching chips, in fact, it is required to solve one of 2 ^ (7 - 1) = 64 puzzles, some of which will not have a solution. This undoubtedly complicates the task.

Before proceeding to the solution of the problem, we note that it is required to store the state of 16 cells, each of which can be in 16 states (an empty cell will be encoded with a zero). This allows you to use an 8-byte integer to store the position.

Let's start with solving the classic puzzle "15" (with non-repeating chips):

solver.h
#ifndef SOLVER_H_ #define SOLVER_H_ #include <stdio.h> #include "common.h" #include "PerfCnt.h" class Solver { public: Solver(Long startPos, Long endPos, int stepCnt): startPos(startPos), endPos(endPos), stepCnt(stepCnt), posCnt(0), perfCnt() {} bool solve(); private: Long startPos; Long endPos; int stepCnt; Long posCnt; PerfCnt perfCnt; static Long pos[MAX_DEEP]; static Byte step[MAX_DEEP]; void dumpSolve(int deep); void dumpPos(int delta); void dumpTotal(); bool checkPos(Long p, int deep); bool solve(int deep, int delta, int startDelta, int X, int Y); Long getStep(Long p, int x, int y, int dx, int dy, int& dd); }; #endif


solver.cpp
 #include "solver.h" Long Solver::pos[MAX_DEEP]; Byte Solver::step[MAX_DEEP]; void Solver::dumpPos(int delta) { printf("Distance: %d\n\n", delta); Long mask = 0xFFFF; for (int shift = 48; shift >= 0; shift -= 16) { int x = (int)((startPos & (mask << shift)) >> shift); int y = (int)((endPos & (mask << shift)) >> shift); printf("%04X %04X\n", x, y); } } void Solver::dumpSolve(int deep) { printf("\n"); for (int i = 0; i < deep; i++) { printf("%d", step[i]); } printf("\n"); } void Solver::dumpTotal() { printf("\nCount: %6I64d\n", posCnt); printf("Time: %7.3f\n\n", perfCnt.elapsed()); } bool Solver::checkPos(Long p, int deep) { int j = MAX_LOOP; for (int i = deep - 1; i >=0; i--) { if (pos[i] == p) return true; if (--j <= 0) break; } return false; } bool Solver::solve() { if (stepCnt >= MAX_DEEP) return false; pos[0] = startPos; int delta = getDelta(startPos, endPos); int X = getX(startPos); int Y = getY(startPos); dumpPos(delta); bool r = solve(0, delta, delta, X, Y); dumpTotal(); return r; } Long Solver::getStep(Long p, int x, int y, int dx, int dy, int& dd) { Long digit = getDigit(p, x + dx, y + dy); if (digit == 0) return p; if (dx != 0) { int delta = getDeltaX(startPos, endPos, digit); if (delta * dx <= 0) { dd++; } else { dd--; } } if (dy != 0) { int delta = getDeltaY(startPos, endPos, digit); if (delta * dy <= 0) { dd++; } else { dd--; } } xorDigit(p, x, y, digit); xorDigit(p, x + dx, y + dy, digit); return p; } bool Solver::solve(int deep, int delta, int startDelta, int X, int Y) { if (pos[deep] == endPos) { dumpSolve(deep); return true; } if (delta > stepCnt - deep) { return false; } if (delta - startDelta > MAX_DELTA_DIFF) { return false; } for (int i = 0; i < 4; i++) { int dd = 0; int dx = 0; int dy = 0; switch (i) { case 0: dy--; break; case 1: dx++; break; case 2: dy++; break; case 3: dx--; break; } if ((X + dx < 1)||(Y + dy < 1)||(X + dx > 4)||(Y + dy > 4)) continue; if (deep + 1 >= MAX_DEEP) return false; pos[deep + 1] = getStep(pos[deep], X, Y, dx, dy, dd); if (checkPos(pos[deep + 1], deep)) continue; step[deep] = i; posCnt++; if (solve(deep + 1, delta + dd, startDelta, X + dx, Y + dy)) return true; } return false; }


This is an ordinary return search. We iterate over all possible moves, change the position and call the same function recursively for the new position. The made moves are encoded with numbers from 0 to 3, indicating the direction of movement of an empty cell (0 - up, 1 - right, 2 - down, 3 - left):

  switch (i) { case 0: dy--; break; case 1: dx++; break; case 2: dy++; break; case 3: dx--; break; }


For the convenience of outputting the solution, we store the sequence of completed moves on the stack (since the number of moves is limited by the conditions of the problem, you can use a regular static array).

The main difficulty of this approach is an avalanche increase in the number of viewed positions, depending on the depth of search. It is necessary to somehow cut the moves, which obviously do not lead to the correct decision. The following considerations will help:

  1. For each position it is possible from 2 to 4 possible moves (depending on the position of the empty cell), while it does not make sense to repeat the previously considered positions (positions, as well as moves, can be stored in a static stack).
  2. For each position, you can calculate the Manhattan distance to the desired position (the total number of moves required to return all the chips to their place, provided that other chips do not interfere with them). Hereinafter, I will call it simply distance. If the calculated distance exceeds the number of remaining moves, the position has no solution and further search can be stopped (here we are helped by the knowledge that the puzzle is solved in no more than N moves).

Since the calculation of the distance is a relatively resource-intensive operation, it can be calculated once (for the initial position), further incrementing or decrementing this value depending on the direction of movement of the piece, which is another move.

We implement auxiliary functions:

common.h
 #ifndef COMMON_H_ #define COMMON_H_ typedef unsigned __int64 Long; typedef unsigned __int16 Short; typedef unsigned char Byte; const int MAX_POSITION = 4; const int MAX_DIGIT = 15; const int MAX_DEEP = 100; const int MAX_LOOP = 10; const int MAX_TASKS = 100; const int MAX_DELTA_DIFF = 5; int getPosition(Long part); int getX(Long state); int getY(Long state); int getX(Long state, Long d); int getY(Long state, Long d); int getDeltaX(Long a, Long b, Long d); int getDeltaY(Long a, Long b, Long d); int getDelta(Long a, Long b); Long getDigit(Long p, int x, int y); void xorDigit(Long& p, int x, int y, Long d); void setDigit(Long& p, Long m, Long d); #endif


common.cpp
 #include "common.h" #include <math.h> Long digit[MAX_DIGIT + 1] = { 0x0000000000000000L, 0x1111111111111111L, 0x2222222222222222L, 0x3333333333333333L, 0x4444444444444444L, 0x5555555555555555L, 0x6666666666666666L, 0x7777777777777777L, 0x8888888888888888L, 0x9999999999999999L, 0xAAAAAAAAAAAAAAAAL, 0xBBBBBBBBBBBBBBBBL, 0xCCCCCCCCCCCCCCCCL, 0xDDDDDDDDDDDDDDDDL, 0xEEEEEEEEEEEEEEEEL, 0xFFFFFFFFFFFFFFFFL }; int getPosition(Long part) { for (int i = 4; i > 0; i--) { if ((part & 0xF) == 0) return i; part >>= 4; } return 0; } int getX(Long state) { for (int i = 4; i >= 1; i--) { int r = getPosition(state & 0xFFFF); if (r != 0) return r; state >>= 16; } return 0; } int getY(Long state) { for (int i = 4; i >= 1; i--) { int r = getPosition(state & 0xFFFF); if (r != 0) return i; state >>= 16; } return 0; } int getX(Long state, Long d) { state ^= digit[d]; return getX(state); } int getY(Long state, Long d) { state ^= digit[d]; return getY(state); } int getDeltaX(Long a, Long b, Long d) { a ^= digit[d]; b ^= digit[d]; return getX(a) - getX(b); } int getDeltaY(Long a, Long b, Long d) { a ^= digit[d]; b ^= digit[d]; return getY(a) - getY(b); } int getDelta(Long a, Long b) { int r = 0; for (Long d = 1; d <= MAX_DIGIT; d++) { r += abs(getDeltaX(a, b, d)); r += abs(getDeltaY(a, b, d)); } return r; } Long getDigit(Long p, int x, int y) { for (; y <= 4; y++) { if (y == 4) { p &= 0xFFFF; for (; x <= 4; x++) { if (x == 4) { return p & 0xF; } p >>= 4; } break; } p >>= 16; } return -1; } void xorDigit(Long& p, int x, int y, Long d) { for (; x < 4; x++) { d <<= 4; } for (; y < 4; y++) { d <<= 16; } p ^= d; } void setDigit(Long& p, Long m, Long d) { p ^= p & m; m &= digit[d]; p ^= m; }


In order to optimize performance, we try to maximize the use of bit operations.

To make sure everything works, you can solve a small puzzle:

 1 2 3 4 5 1 3 4 5 6 7 8 9 2 B 7 9 ABCD 6 A 8 DEFEFC

Since I myself have prepared this example, I know that 11 moves are enough to solve it.

Indeed, with this limitation, the program displays the answer in a thousandth of a second:

 Distance: 11 1234 5134 5678 92B7 9ABC D6A8 DEF0 0EFC 00323003222 Count: 18 Time: 0.001

We see that 18 positions are considered. In order to assess the increase in complexity, depending on the difference in the limit on the number of moves and the distance to the final position, I will increase the limit on the number of moves, fixing the number of viewed positions.

The final schedule is as follows:

image

Sawtooth graphics due to the fact that the program finds new (longer) solutions, with increasing restrictions on the number of moves. As expected, the number of viewed positions increases very quickly.

Now it remains to implement the renumbering of pair chips. This also helps recursion:

initializer.h
 #ifndef INITIALIZER_H_ #define INITIALIZER_H_ #include "common.h" #include "solver.h" struct Task { Long startPos; Long endPos; int delta; bool isProcessed; }; class Initializer { public: Initializer(Long startPos, Long endPos, int stepCnt): startPos(startPos), endPos(endPos), stepCnt(stepCnt), taskCnt(0) {} bool solve(); private: Long startPos; Long endPos; int stepCnt; int taskCnt; static Task tasks[MAX_TASKS]; static int digits[MAX_DIGIT + 1]; bool checkInit(Long s, Long e); bool addPos(Long s, Long e); bool init(Long s, Long e); Long getFreeDigit(); bool checkPos(Long s, Long e); void normalize(Long& p); void dumpPos(Long s, Long e, int delta); }; #endif


initializer.cpp
 #include "initializer.h" Task Initializer::tasks[MAX_TASKS]; int Initializer::digits[MAX_DIGIT + 1]; bool Initializer::solve() { if (!init(startPos, endPos)) return false; while (true) { int mn = stepCnt; int ix = -1; for (int i = 0; i < taskCnt; i++) { if (tasks[i].isProcessed) continue; if (stepCnt - tasks[i].delta < mn) { mn = stepCnt - tasks[i].delta; ix = i; } } if (ix < 0) break; tasks[ix].isProcessed = true; Solver solver(tasks[ix].startPos, tasks[ix].endPos, stepCnt); if (solver.solve()) return true; } return false; } bool Initializer::checkInit(Long s, Long e) { for (int i = 0; i <= MAX_DIGIT; i++) { digits[i] = 0; } for (int i = 0; i <= MAX_DIGIT; i++) { digits[s & 0xF]++; s >>= 4; } if (digits[0] != 1) return false; for (int i = 0; i <= MAX_DIGIT; i++) { digits[e & 0xF]--; e >>= 4; } for (int i = 0; i <= MAX_DIGIT; i++) { if (digits[i] != 0) return false; } return true; } void Initializer::dumpPos(Long s, Long e, int delta) { printf("0x"); Long mask = 0xFFFF; for (int shift = 48; shift >= 0; shift -= 16) { int x = (int)((s & (mask << shift)) >> shift); printf("%04X", x); } printf(" 0x"); mask = 0xFFFF; for (int shift = 48; shift >= 0; shift -= 16) { int x = (int)((e & (mask << shift)) >> shift); printf("%04X", x); } printf(" %d\n", delta); } bool Initializer::addPos(Long s, Long e) { if (!checkPos(s, e)) return true; if (taskCnt >= MAX_TASKS) return false; tasks[taskCnt].startPos = s; tasks[taskCnt].endPos = e; tasks[taskCnt].delta = getDelta(s, e); tasks[taskCnt].isProcessed = false; if (tasks[taskCnt].delta == 0) return false; if (tasks[taskCnt].delta > stepCnt) return true; taskCnt++; return true; } Long Initializer::getFreeDigit() { for (Long i = 1; i <= MAX_DIGIT; i++) { if (digits[i] == 0) return i; } return 0; } bool Initializer::init(Long s, Long e) { for (int i = 0; i <= MAX_DIGIT; i++) { digits[i] = 0; } Long x = s; for (int i = 0; i <= MAX_DIGIT; i++) { digits[x & 0xF]++; x >>= 4; } bool f = true; for (int i = 0; i <= MAX_DIGIT; i++) { if (digits[i] != 1) f = false; } if (f) { return addPos(s, e); } Long d = getFreeDigit(); if (d == 0) return false; x = s; Long ms = 0xF; for (int i = 0; i <= MAX_DIGIT; i++) { Long t = x & 0xF; if (digits[t] > 1) { setDigit(s, ms, d); Long y = e; Long me = 0xF; for (int j = 0; j <= MAX_DIGIT; j++) { if ((y & 0xF) == t) { Long k = e; setDigit(k, me, d); if (!init(s, k)) return false; } me <<= 4; y >>= 4; } break; } ms <<= 4; x >>= 4; } return true; } void Initializer::normalize(Long& p) { int x = getX(p); int y = getY(p); for (; x < 4; x++) { Long d = getDigit(p, x + 1, y); xorDigit(p, x + 1, y, d); xorDigit(p, x, y, d); } for (; y < 4; y++) { Long d = getDigit(p, x, y + 1); xorDigit(p, x, y + 1, d); xorDigit(p, x, y, d); } } bool Initializer::checkPos(Long s, Long e) { normalize(s); normalize(e); Long nums[16] = {0}; int ix = 0; for (int y = 1; y < 4; y++) { for (int x = 1; x < 4; x++) { Long d = getDigit(e, x, y); if (d != 0) { nums[d] = ++ix; } } } int cn = 0; for (int y = 1; y < 4; y++) { for (int x = 1; x < 4; x++) { Long d = getDigit(s, x, y); for (Long i = 1; i <= 15; i++) { if (nums[i] < nums[d]) { int Y = getY(s, i); if (Y < y) continue; if (Y > y) { cn++; break; } int X = getX(s, i); if (X > x) { cn++; break; } } } } } return (cn & 1) == 0; }


Before adding to the list, we check whether the position has a solution and whether it can be solved for the specified number of moves (it is better to check once more than to perform a costly search for a position that is obviously not having a solution).

Here is a list of possible positions, sorted in descending order of distance:

list
 0x763258F4E1DCBA90 0x6CBEDA1F29873450 50 0x763258F4E1DCBA90 0x6CBED81F29A73450 48 0x763258F4E1DCBA90 0x6CBEDA9F21873450 48 0x763258F4E1DCBA90 0x6CBED89F21A73450 46 0x763258F4E1DCBA90 0x6C4EDA1F29873B50 44 0x763258F4E1DCBA90 0x65BEDA12F98734C0 44 0x763258F4E1DCBA90 0x6CBE7A1F298D3450 44 0x763258F4E1DCBA90 0x6C4ED81F29A73B50 42 0x763258F4E1DCBA90 0x65BED812F9A734C0 42 0x763258F4E1DCBA90 0x6CBE781F29AD3450 42 0x763258F4E1DCBA90 0x6CB3DA1F2987E450 42 0x763258F4E1DCBA90 0x6C4EDA9F21873B50 42 0x763258F4E1DCBA90 0x65BEDA92F18734C0 42 0x763258F4E1DCBA90 0x6CBE7A9F218D3450 42 0x763258F4E1DCBA90 0x6CB3D81F29A7E450 40 0x763258F4E1DCBA90 0x6C4ED89F21A73B50 40 0x763258F4E1DCBA90 0x65BED892F1A734C0 40 0x763258F4E1DCBA90 0x6CBE789F21AD3450 40 0x763258F4E1DCBA90 0x6CB3DA9F2187E450 40 0x763258F4E1DCBA90 0x654EDA12F9873BC0 38 0x763258F4E1DCBA90 0x6C4E7A1F298D3B50 38 0x763258F4E1DCBA90 0x65BE7A12F98D34C0 38 0x763258F4E1DCBA90 0x6CB3D89F21A7E450 38 0x763258F4E1DCBA90 0x654ED812F9A73BC0 36 0x763258F4E1DCBA90 0x6C4E781F29AD3B50 36 0x763258F4E1DCBA90 0x65BE7812F9AD34C0 36 0x763258F4E1DCBA90 0x6C43DA1F2987EB50 36 0x763258F4E1DCBA90 0x65B3DA12F987E4C0 36 0x763258F4E1DCBA90 0x6CB37A1F298DE450 36 0x763258F4E1DCBA90 0x654EDA92F1873BC0 36 0x763258F4E1DCBA90 0x6C4E7A9F218D3B50 36 0x763258F4E1DCBA90 0x65BE7A92F18D34C0 36 0x763258F4E1DCBA90 0x6C43D81F29A7EB50 34 0x763258F4E1DCBA90 0x65B3D812F9A7E4C0 34 0x763258F4E1DCBA90 0x6CB3781F29ADE450 34 0x763258F4E1DCBA90 0x654ED892F1A73BC0 34 0x763258F4E1DCBA90 0x6C4E789F21AD3B50 34 0x763258F4E1DCBA90 0x65BE7892F1AD34C0 34 0x763258F4E1DCBA90 0x6C43DA9F2187EB50 34 0x763258F4E1DCBA90 0x65B3DA92F187E4C0 34 0x763258F4E1DCBA90 0x6CB37A9F218DE450 34 0x763258F4E1DCBA90 0x654E7A12F98D3BC0 32 0x763258F4E1DCBA90 0x6C43D89F21A7EB50 32 0x763258F4E1DCBA90 0x65B3D892F1A7E4C0 32 0x763258F4E1DCBA90 0x6CB3789F21ADE450 32 0x763258F4E1DCBA90 0x654E7812F9AD3BC0 30 0x763258F4E1DCBA90 0x6543DA12F987EBC0 30 0x763258F4E1DCBA90 0x6C437A1F298DEB50 30 0x763258F4E1DCBA90 0x65B37A12F98DE4C0 30 0x763258F4E1DCBA90 0x654E7A92F18D3BC0 30 0x763258F4E1DCBA90 0x6543D812F9A7EBC0 28 0x763258F4E1DCBA90 0x6C43781F29ADEB50 28 0x763258F4E1DCBA90 0x65B37812F9ADE4C0 28 0x763258F4E1DCBA90 0x654E7892F1AD3BC0 28 0x763258F4E1DCBA90 0x6543DA92F187EBC0 28 0x763258F4E1DCBA90 0x6C437A9F218DEB50 28 0x763258F4E1DCBA90 0x65B37A92F18DE4C0 28 0x763258F4E1DCBA90 0x6543D892F1A7EBC0 26 0x763258F4E1DCBA90 0x6C43789F21ADEB50 26 0x763258F4E1DCBA90 0x65B37892F1ADE4C0 26 0x763258F4E1DCBA90 0x65437A12F98DEBC0 24 0x763258F4E1DCBA90 0x65437812F9ADEBC0 22 0x763258F4E1DCBA90 0x65437A92F18DEBC0 22 0x763258F4E1DCBA90 0x65437892F1ADEBC0 20


It was in this order that I began to check positions, because I believed that the fastest search would be for positions with the maximum distance. Indeed, the first elements of the list were checked in a few seconds, but for the first position with a distance of 42, the search had to be stopped after 10 minutes of waiting.

At this point, I was a little sad and began to think about introducing heuristics to determine the order of enumeration of possible moves, and generally, about a more careful study of the algorithm A * . But, just by inertia, I decided to check the last element of the list:

 #include <iostream> #include <tchar.h> #include "initializer.h" int _tmain(int argc, _TCHAR* argv[]) { Initializer m(0x763258F4E1DCBA90, 0x65437892F1ADEBC0, 59); m.solve(); return 0; }

I did not even immediately realize that the program found a solution:

 Distance: 20 7632 6543 58F4 7892 E1DC F1AD BA90 EBC0 00032103210321032330111223010323032112233000121221 Count: 6117348 Time: 2.404

In just two and a half seconds.

Quest is passed.

Sources, as always, on github .

Source: https://habr.com/ru/post/180043/

More articles:


All Articles