FFOD - Level 3 - Homeomorphically Directed Acyclic Graphs!

Monday, November 28, 2016

Just got cracking on the level three puzzle which is inspired by that bit in Good Will Hunting where the janitor solves the super-hard maths puzzle on the blackboard.

Although as this "Numberphile" video here shows, the problem isn't actually that hard. Certainly something you could build a puzzle around.

Without watching the video, the problem is essentially, can you draw every possible way to connect 10 dots, such that every dot is connected, there are no loops, and none of your answers can be a re-shuffling of another answer. Simples.

Unfortunately, while it is easy to look at two little graph diagrams with your brain and say: "Yup, those two are the same just rearranged a bit." It is quite difficult to write an algorithm to do this. I spent 4 hours today with a pencil and paper proving this, and concluded that I did not know how to do it. I won't be able to make the puzzle unless I can get the code to check the players answers are correct.

Fortunately I had a little help from my friends. And when I say friends, I mean, I googled "C# implementation of graph isomorphism" and found this smart little library here that some chap had done in 2008. Added the DLL to the unity project, and bang, am good to go.

Now all I have to do is build a shed-load of puzzles, and a user-interface, and present it to the player without using words so that they will all understand. Not Simples.

Tags: Four Floors of Doors Unity