Click Nothing

design from a long time ago

recent posts

  1. Sven's avatar
  2. Unknown's avatar

    I’m one of the author’s in the 2022 opdc (didn’t win anything, still trying to bear up under the shame…

  3. Arya's avatar
  4. Max Clark's avatar
  5. Kfix's avatar

    Thank you for this very interesting collection, and for wrestling with the obviously mixed feelings on this anniversary. And thank…

Kuratowski’s Theorem – The Game!

Finally someone has made a game that allows he player the skirt the edges of the fearsome Kuratowski theorem and open up some whoop-ass on K5 and K3,3 – two bosses that you normally would not want to mess with unless you have a Masters in Graph Theory.

Actually – I find this little puzzle game strangely hypnotic. It’s interesting because as you progress through the levels you discover new approaches to solving the puzzle at varying stages of complexity. At the beginning – on level 1, you can actually picture the puzzle as a 3d extrusion, and it’s very easy to unfold. At level 2, that approach fails – but you can still use a holistic approach to solving it… by level 4 or 5 you need to start solving the problem in local segments. By level 6 or 7 you need to start breaking the problem down into local clusters – separating those clusters and solving each of them using local solves, then connecting the solved domains one by one (there is an interface failure here where I am unable to drag a selection box around a set of nodes and move them all… so I run out of space on the screen sometimes, which is very annoying).

I haven’t gone any further than level 8 – except to use the warp to jump to level 100 and watch it crash my computer.

I think that every second I spent playing this game has paid off in providing me insight into the structure of all kinds of more ‘real’ problems. Seriously – for 20 minutes of your time to do the first 4 or 5 levels of this thing, it’s worth it.

Posted in ,

One response to “Kuratowski’s Theorem – The Game!”

  1. Sean Barrett Avatar
    Sean Barrett

    (Hi Clint; I was one of the people in the big discussion group at starbucks after your lecture.)
    Planarity actually admits a somewhat degenerate solving strategy due to the nature of how the boards are generated. It’s only somewhat degenerate because it’s still a lot of work at higher levels, and I’m not sure it necessarily leads to the best human solving times.
    Every vertex in a planarity puzzle has degree 2, 3, or 4 (that is, they have 2, 3, or 4 connections to other vertices), due to the way the puzzles are constructed. It turns out (also due to the construction) that every planarity puzzle admits a solution in which the vertices on the “outside” edge of the puzzle have arbitrary degree, and the vertices on the inside are all of degree 4.
    Thus, the “degenerate” solution is to first determine all the vertices on the “outside”. Find a 2- or 3-degree vertex, then walk along connected vertices, grabbing those that are degree 2 or 3 (although greediness will require some fixup when all of the vertices adjacent to a 3-degree vertex are on the outside).
    When you reach a point where all of the unconsumed adjacent vertices are of degree-4, you’ll have to probe them to see which one is nearest to a degree-3 or degree-4 node. This can get tricky simply because it’s hard to see. Eventually you’ll loop back to your starting 2- or 3-degree vertex, and you’re done the outside. The remaining vertices can be processed in the order that they are close to the outside, since that provides a good guide for where to place them.
    I don’t know for sure how the puzzles are constructed, but one way to construct puzzles with this property is to draw a collection of random lines and create a vertex at the intersection of any two pairs, and the obvious edges. Any interior vertex has adjacent vertices along each line in both directions (4); vertices of degree 2 or 3 occur when there are no further intersections along one line in one or both directions.

    Like

    Reply

Leave a reply to Sean Barrett Cancel reply