Hey admins, I've sent a couple of tests to timus_support@acm.timus.ru that my AC solution was struggling with. Please validate if they can be added to the system.

Your tests have been added. Thanks!

Milanin, thanks a lot for new tests! Now I've got AC only with neural networks solution. All solutions with just "optimizations"/"bad subfields & patterns", etc. didn't allow me to pass new tests.

This is impressive. I still can't believe that there's a problem on Timus that has a meaningful neural network based solution.

Finally, 0.062 sec without neural networks. Just correct removing of "bad" fields, effective hash/pq implementations + bit tricks & memory optimizations + A*.

I have been working on this problem since it appeared - the 2007 student quarterfinal, I went there with a team from SUrSU.
Later I tried many different approaches and in practice, the hardest tests in this problem are those with 12 and 13 boxes.
In the end, the solution turned out as follows:

1. Use uint64_t bit masks to store the board state (36 bits for the box positions + the coordinates of the upper-left corner of the connected component in which Stas is located) + 22 bits remain for additional information.
   A transition between vertices of the position graph is performed specifically by PUSHING a box, not by moving Stas.

2. Traverse the position graph using BFS with A* according to the g+h principle, where g is the exact cost of the path from the starting point to the current vertex, and h is a heuristic estimate from the current vertex to the final state.

3. Check for repeated visits to vertices of the graph using a hash table (implemented independently, with no STL containers, as they reduce performance and increase memory usage).

4. Store all examined boards in a fixed-maximum-size priority queue, which I implemented as a heap with K children at each node (K does not necessarily equal 2; it turns out that for this problem K = 4 or 6 is more advantageous).

5. To quickly find all cells of the connected component reachable by Stas from his current position without pushing boxes, you should use not bfs with a queue, but a wave algorithm on bit masks.
const uint64_t M36 = (1ULL<<36)-1;
Free cells: opened = ~(walls | boxes) & M36;
Starting from the player's start bit, we expand the region through neighboring cells until a fixed point is reached.
    r = start;
    do {
        old = r;
        r |= neighbors(r) & open;
    } while (r != old);

6. Generation of all possible box pushes from the current position. Instead of a "each box X four directions" loop, for each direction one 36-bit mask of boxes that can be pushed is constructed.
In the general case, the condition consists of three factors: the cell contains a box + behind the box there is a cell reachable by the player + in front there is a free cell. These sets are combined through AND after the required shifts.
Then only the set bits are iterated over:
    while (z) {
        int q = ctz(z);
        z &= z-1;
        ...
    }
This is especially efficient because the board is small, while most boxes cannot be pushed in a given direction.

7. Before the main search, immediately after reading the board, for each goal cell a BFS for one box is built in the reverse direction. The other boxes are ignored, but walls and push geometry are taken into account: for a box to be pushed from the previous cell into the current one, both a cell for the box itself and a support cell for the player are needed. We obtain pullDist[goal][cell], as well as pullMin[cell] - the minimum number of pushes to any goal, mask_r[cell] - a bit mask of goals that a box from this cell is capable of reaching at all. If mask_r[cell] == 0 and the cell is not a goal, a new box in it is statically dead. This is much stronger than a simple corner check.

8. Fast heuristic update: on a push, exactly one box q->d moves. Therefore h is not recalculated over all boxes, h_new = h_old - cost[q] + cost[d].
   After push q->d, it is not always necessary to perform a full flood fill to determine Stas's component. The old region R changes as follows: d becomes occupied, q becomes free, and the player starts from q.
   If d did not belong to R or had no more than one neighbor from R, removing d cannot split the component into two parts. Then R can be corrected locally and expanded only through the newly freed q.

9. Before adding a new position to the priority queue, of course, it is worth checking it for unsolvability. The key point of this problem is that you should not be afraid of complex and time-consuming methods for pruning bad positions, the main thing is to prune as many of them as possible. Even solutions that took every 4 by 4 square on the board, fed it into a trained neural network with 2 hidden layers of 60 neurons each, and asked it whether this 4 by 4 combination was unsolvable or not passed within the time limit for me, although it would seem that this already involves 9 * 3600 float multiplication operations (at least), and doing this for every board would take a very long time, but NO, IT WILL NOT, if FEW of those boards remain.

So, this is how I pruned bad positions:
   (!!!) Important note (!!!)
      We perform the unsolvability check specifically taking into account the position into which the moved box has entered. There is no need to check the lower corner 2 by 2 square on a 6 by 6 board if we moved a box in the top row. This greatly speeds up the checks.

     a) the perimeter of the board (the simplest case - the number of boxes along the perimeter and the number of goal cells along the perimeter; more complex - along each side taking attached walls into account, a set of segments along the perimeter, each with its own mask-based check)

     b) all combinations of occupied 2 by 2 cells (with wall/box variations) - if it is unsolvable, then entire field is unsolvable (this gives 4 squares to check on a 6 by 6 board, since we will check only those adjacent to the moved box)

     c) all variants of 3 by 3 combinations that no longer contain 2 by 2 blockages, since they were checked at the previous step, which means that it is enough to check 3 by 3 combinations with an empty central cell, which, of course, may also be a goal (we check 8 such squares, depending on which cell of that square corresponds to the moved box)

     d) there are very many 4 by 4 variants (you must also remember to take into account that Stas may be either inside the selected 4 by 4 sub-square or outside it, so if the combination is encoded with masks, it takes 49 bits: 16 bits each for the positions of boxes and goals inside the 4 by 4, 16 possible positions of Stas inside and 1 outside, 3*16+1 bits). I implemented a generator of unsolvable 4 by 4 squares taking into account that all cells outside it are made goal cells, since we do not know the context of the board when extracting a 4 by 4 square from it, so goals there could be anywhere, and solvability can also depend on that. Of course, during generation, I did not include in the collection those positions that were already pruned by my perimeter checks and 2 by 2 and 3 by 3 squares, only NEW blockage variants. Generation took a couple of months. This produced about 70 million combinations for the corner placement of the 4 by 4 sub-square and slightly fewer for the placement where the upper corner is in cell (0,1) of the original 6 by 6 board. Of course, such a number of combinations cannot be inserted into the source code as a constant array. I tried to train a neural network, but first of all, it takes a long time to query it for an answer (see above, many float multiplications; networks smaller than 120 neurons did not train at all), and second, it still gives a probabilistic answer and on some Timus tests (especially newly added ones) it may classify a solvable combination (even if only one out of 10000) as unsolvable, and it turns out that pruning such a board just once or moving it to the end of the priority queue is enough to fail to find a solution in time. Therefore, although I managed to fit the solution with the neural network into 4.5 seconds, I discarded this variant as inefficient. An analysis of the resulting collection and identification of common patterns that can be checked simply with bit masks worked much better here; of course, these common patterns did not cover the entire range of bad boards, but I managed to prune about 80 % of the collection.

     I no longer generated or considered the 5 by 5 and 6 by 6 variants - it is pointless, there are too many combinations.

     e) Another class of deadlocks is a small rectangular pocket bounded by walls/boxes, with too few goals inside. The player must not be inside the rectangle being considered + internal goals are taken into account + only small sizes for which the checking rule is provable and safe are considered.

10. The order (!) of the board solvability checks and the check for whether the board is in the hash table is important. It is better to first perform the simple checks (up to 2 by 2), then check for presence in the hash, and then perform the complex checks.

11. Not only the box cell is important, but also the side from which the player must approach it. For each (cell,side) pair, msk[cell][side] is calculated - a mask of goals reachable by one box on the static board with the corresponding orientation of the player's approach to the box. From this, a mask of other boxes is also constructed which, together with the new box, create a two-box conflict over the set of reachable goals.

12. An important optimization was that local 2x2,3x3,4x4 windows do not see interactions between boxes located at a distance from one another. For difficult tests, certain four boxes are also selected from all boxes, the remaining boxes are temporarily removed, and if even after removing the other boxes the selected four cannot reach four goals, the full state is unsolvable. Four distinct cells are sorted, the number of combinations is C(36,4)=58905, but solvability also depends on the side/from which component the player can act. Therefore, I store a 36-bit mask of player cells from which this four-box case is solvable in the simplified problem.

13. I had to optimize the hash, making it initially small at 2^16, then increasing it if the combinations grew substantially. I also used _mm_loadu_si128 / _mm_cmpeq_epi16 for hash comparison.
    It was also important to avoid any dynamically allocated memory: no new/delete, no STL containers.

14. I encountered the problem of insufficient source-code size (64 KB is still too little for large solutions, there is not much room, especially if storing rules for pruning 4 by 4 boards and so on). All such additional static information had to be encoded in a large constant string using alphabetic characters/digits and so on, and decoded during program execution. Variable names had to be kept short, which makes the code difficult to understand, even line breaks sometimes had to be removed to fit into 64 KB. I asked above on the forum to increase the size, this seems like it should not be difficult, but no one heard me.

Edited by author 04.09.2026 19:09

Edited by author 04.09.2026 19:20