{"id":130,"date":"2014-11-22T11:04:22","date_gmt":"2014-11-22T11:04:22","guid":{"rendered":"http:\/\/ceptimus.co.uk\/?p=130"},"modified":"2014-11-22T11:04:22","modified_gmt":"2014-11-22T11:04:22","slug":"untangle-planarity","status":"publish","type":"post","link":"https:\/\/ceptimus.co.uk\/index.php\/2014\/11\/22\/untangle-planarity\/","title":{"rendered":"Untangle, Planarity."},"content":{"rendered":"

I’ve been writing some code (in Java) to solve this fun puzzle.\u00a0 I’ve played the puzzle for many years – it’s part of the excellent and free Simon Tatham’s Portable Puzzle Collection<\/a> which has been available on many platforms for ages and has recently been ported to Android too.\u00a0 Untangle was inspired by Planarity<\/a>, written by John Tantalo.<\/p>\n

My first effort modelled the puzzle as a physical system.\u00a0 The links between points are elastic bands, where the attractive force is proportional to the cube of their length.\u00a0 The points have an electric charge which produces a repulsive force between all points in line with Coulomb’s inverse square law.\u00a0 The whole thing is submerged in a viscous fluid so that things don’t move too fast.<\/p>\n

\"Untangle17\"<\/a><\/p>\n

It solves many puzzles just using those rules but sometimes, especially with puzzles with a large number of vertices, it gets stuck in ‘a knot’ or takes too long to stabilize.\u00a0 Also, if it happens to ‘choose’ an outer face with a large number of vertices, then some inner vertices can be pushed out by the repulsive force so that they cross the ‘perimeter line’.<\/p>\n

I’m now working on a faster and guaranteed-to-work algorithm – though it may not be as interesting to watch in action.\u00a0 Stay tuned for an update…<\/p>\n","protected":false},"excerpt":{"rendered":"

I’ve been writing some code (in Java) to solve this fun puzzle.\u00a0 I’ve played the puzzle for many years – it’s part of the excellent and free Simon Tatham’s Portable Puzzle Collection which has been available on many platforms for ages and has recently been ported to Android too.\u00a0 Untangle was inspired by Planarity, written […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4,5],"tags":[],"class_list":["post-130","post","type-post","status-publish","format-standard","hentry","category-programming","category-puzzles"],"_links":{"self":[{"href":"https:\/\/ceptimus.co.uk\/index.php\/wp-json\/wp\/v2\/posts\/130","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ceptimus.co.uk\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/ceptimus.co.uk\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/ceptimus.co.uk\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/ceptimus.co.uk\/index.php\/wp-json\/wp\/v2\/comments?post=130"}],"version-history":[{"count":0,"href":"https:\/\/ceptimus.co.uk\/index.php\/wp-json\/wp\/v2\/posts\/130\/revisions"}],"wp:attachment":[{"href":"https:\/\/ceptimus.co.uk\/index.php\/wp-json\/wp\/v2\/media?parent=130"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/ceptimus.co.uk\/index.php\/wp-json\/wp\/v2\/categories?post=130"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/ceptimus.co.uk\/index.php\/wp-json\/wp\/v2\/tags?post=130"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}