Does anyone have any information on mathematical analyses of Triazzle-style puzzles? I’m assuming you could solve them using graph theory, but I haven’t quite been able to figure out the details.
-Ben
I’ve never played Triazzle, but after a web search, I can venture a guess. Assuming that each piece is the same shape (a triangle) and that you’re interested in matching the patterns. Correct me if you need to.
Unfortunately, the best answer I can give is a non-constructive “yes”. There are 3[sup]n[/sup]*n! possible arrangements of the pieces, so a brute force search of the solution space should be possible in at most quadratic non-deterministic time. Therefore, Triazzle could be formulated as a problem in NP. Every problem in NP can be reduced to any NP-complete problem, so all you have to do is transform your problem instance into an instance of some NP-complete problem, and you’re good to go. Personally, I’d first consider reductions to the Hamiltonian path problem (which gets you the graph theoretic aspects), but I don’t have any particular reason to do, just instinct.
Probably not quite the answer you’re looking for, but it’s the best I can do for now.
Yes, this was my basic idea- that you could convert the puzzle pieces into a graph and look for a Hamiltonian cycle, sort of like the old GT solution of the “Instant Insanity” puzzle.
If you have just six triangular pieces that have to be fitted into a hexagon, the problem seems pretty easy, because there’s only one cycle in question- the cycle around the center point. The problem is that a typical triazzle has a lot of pieces, so any cycle leading through all the sides that have to be matched will meander around the board and end up using different faces of the same tiles at different parts of the cycle, so it’s hard for me to think of an elegant way to make the cycle work out right. With “Instant Insanity,” the solution is dependent on the fact that the pieces can rotate, and so different sides of the pieces are somewhat independent of each other. Unfortunately, that won’t work for the triazzle.
-Ben
Unfortunately, I’ve never actually seen Triazzle, so I have no more insight to offer. If you know of a website that has a fairly detailed description of the game, I’d definitely be interested in looking at it.
A search turned up a demo version of the Triazzle computer game. Does that help?
http://www.kidsdomain.com/down/pc/triazzlep1.html
-Ben
Yeah, that’s good. I downloaded it and played with it for a little while. Truth be told, I’m not sure I can help–although you might have more luck working it as a vertex covering problem than a Hamiltonian path. You might also want to look around usenet, especially in the games newsgroups. Sorry that I couldn’t help more.