Brutally approaching blocky arrangements

2022-04-30, post № 258

programming, discrete-optimization, #sokoban, #brute-force, #baba, #c++

Arvi Teikari’s discrete self-referencing puzzler has fascinated with its non-formulaic take on box pushing since its early days as a contest entry in April of 2017^[1]. Whilst its vanilla level set is vast, conceptually coupled as well as thematically aligned, one cannot expect it to exhaustively cover the gargantuan space of world scenarios, even after filtration by solvability and playfulness.

As such, in line with the ever increasing shift in gaming away from the ROM-baked whollistic experiences towards providing loose game-inducing boundaries on internet-driven platforms — dually tending to the consuming player as well as the niche creator in one —, of particular note being Roblox, LittleBigPlanet, Super Mario Maker, its sequel and Dreams, it was a natural step for Teikari to open up their game to become a puzzler engine in late 2020^[2], allowing anyone to tinker with the shifting ways of their visually dissonant purely property-induced worlds.

A stumped Baba.

A testimony to this engine’s capabilities, classic games as well as prominent puzzlers of the present times have been in parts embedded in it. It was in this regime of levels my brother was meandering about when he laid his Switch onto the dining table to take a bite that I got a chance to try myself at solving an excerpted recreation of Cosmic Express; with my tracks successfully laid within us finishing our meal. Recognizant of my solve, my brother menued swiftly to the next level of interest: a Sokoban recreation. And with both of us being knowingly inept at true box pushers, after a brief dabble we both lost interest at getting virtual squares stuck in virtual corners. To my brother’s slight dismay — him being generally interested in the act of playing a game — I could not let a graph traversal problem of such miniscule complexity rest unsolved and began work on a brute-force-based solver, aiming for finding a solution minimal in its step count. A few hours later, around midnight, I presented one of the two minimal solutions to be checked against real hardware; with the final crate maneuvered onto its flag, I got a collected response exposing the triviality of exhaustive algorithms:

Level e3bd-v4z1 “Sokoban” by an unknown author is optimally solved by either one of the following two move sequences:

{vv><^^>v>v^<<v>^>>vvv<<^^<^>v
 vv>>^<>^>>v<<v<<^><^>>>v>^^v<
 <<<<^^>v<v>>>>v>^<<^<v<<^^>v<
 v>>>><<v>>}

{vv><^^>v>v^<<v>^>>vvv<<^^<^>v
 vv>>^<>^>>v<<v<<^^>>>v>^^v<<<
 <<^^>v<v>>>>v>^<<^<v<<^^>v<v>
 >>><<<v>>>}

Source: baba-sokoban.cpp