Wednesday, 21 December 2016

Retarus Charity Game is Bridges of Koningberg

Julie sent me a link to this game, and said I should play it, as it supports Techtonica, which does great things (copying from their webpage): "Free tech training with living and childcare stipends and job placement for low-income women and non-binary adults. #BridgeTheTechGap".  Great, I'm on board with all that.

The game is essentially a more complicated version of the Bridges of Koningsberg problem.  There are nodes you need to pass through, and you can't retrace steps.  I did the first 17 levels before realizing I should get back to work, so I waited until I got home to finish all the levels (and bring Techtonica above 50000 stars.  I assume everybody gets some money, and that it's not some sort of monstrous three charities enter, one charity leaves thing).  It wasn't until level 29/30 that I realized that there had to be some sort of algorithm to solve these, and not just "magical topology powers."  So I sat down to write out what I was doing with diagrams and words, to make sense of it.


Here's the board.

Nodes with only two edges must be traveled through both, obviously.

So, we can block off any route that the two-edge nodes force us to exclude.
 I ended up largely solving this from the end, because I know a path must go to the terminal node, and that immediately forces the route into the two nodes in the bottom right corner.  Knowing that the intermediate node already had two edges on the path excludes any other path from using the other two edges.
And this provides the next big hint to how the algorithm works:  Once you've blocked edges from being part of the path, you turn some nodes that were previously connected to 3+ nodes into 2-edge nodes, so you can iterate the process again.  I've labeled the first node that is downgraded like this with a star.

Another round of marking and blocking gets the pseudo-path near the start point, but there aren't any clear ways to continue at that end.

Which is good that I noticed that in the upper right, the one edge I crossed off in stage 1a is connected to another edge that is also forbidden.  This makes the one node a 2-edge.  The square path at the top is redundant, so I chose one to exclude.  This connects those two corner nodes to the straight 2-edge in the middle.

I'm not 100% sure that my solution here is unique, but I'm not redrawing my diagrams again.  In any case, my logic here says that the start can't continue straight past that first target node, as it would then either need to go down (which leads to the end), or straight (back through that 2-edge), which isn't value.  I already excluded the bottom route, so it will need to turn up.  Blocking that route forces the empty node to have 2-edges, which connects the "to-the-end" path with the "back through the straight 2-edge" path.  This blocks the down edge out of the top-center node, forcing it to be a turn.

That forces the empty node above it to have one exit blocked, and then things fall into place. 
See, 50008.
And I think that this algorithm solves any similar game, although there are two edge cases.  The first is when the grid is over connected with edges.  This should always have trivial solutions that are obvious (and the early stages have extra connectivity, and that simply means that there are multiple paths that are valid.  Path length was not a constraint).  The second problem case is when the objective is not possible because it's a true Bridges of Koningsberg problem with no solution.