I found this…someone else was rather intrigued by these puzzles–apparently they can be better interpreted as directed graphs. (Finite state machines are essentially directed graphs that are non-specific to inputs/functions. In addition, the type of solution we’re looking for is called a Hamiltonian Path, the theory behind which has been researched to an extent.) He couldn’t find a solution either but there’s some great theory and proofs of certain properties of the puzzles here…
So I’ve been absolutely binging on Final Fantasy XIII-2 to an insane extent this weekend (finished the story already–just to give an idea), and of course now I need to come back to reality because it’s Sunday evening and I have class tomorrow. I’ve even got an electronic exam for one of my electives this semester tomorrow and I haven’t even studied for it yet–I’ll do fine though, the professor in that course literally tries to make his class extremely easy because he knows most of his students are taking his course for general education credits.
Anyway, so before I go off to eat (late night) and do some homework for another class, I wanted to mention something that’s been bugging me ever since I got to a certain part of final fantasy XIII-2. Oddly enough, this is math/computer science related (don’t worry, it’s something relatively easy to understand); in fact, to something I learned about in a discrete math course last semester.
You see in several parts of the game, there’s this one type of puzzle you have to solve, which due to its nature can be difficult. The puzzle is thus: There is a circle with with 5-13 numbers, pre-set or random (in a manner that always has at least one solution), evenly spaced on its circumference, none of which can be greater than # of numbers/2, rounded down (floor(# of numbers/2)). You need to mark all the numbers, and you can start by choosing any number to mark initially. Then, your next number must be the number of spaces on the number you just marked off going either clockwise or counterclockwise away from the number you just marked. You can choose either if there are two not yet used options, and you continue the process in this manner, going a number of spaces away counter-clockwise or clockwise that was designated on your new number. If you have not marked off all of the numbers yet, yet you cannot make a move to another unmarked number after several moves, you fail the puzzle and need to start over/do another puzzle of equal size. These puzzles get VERY hard to solve mentally when there are more numbers on the board.
If you’re having trouble following that, watch this video for examples from actual gameplay footage. The puzzle footage (giving solutions only) is at around 5:50.
Now, based on what I learned last semester in my discrete maths course–I eventually recognized this puzzle as simply being a disguised representation of a problem related to finite state machines. A finite state machine is a system of sorts where you have a finite number of elements, or states, and a finite number of inputs, or functions, which map each state onto other states or trivially back onto themselves. For example, this would be a finite state machine with states あ, ひ, ユ, ネ, and よ (I used my favorite Japanese Kana cuz I can…xD) and inputs, or functions, f and g.
So in the above example, if you were at あ and did input g, you’d end up at ひ(g(あ)=ひ). If you were ユ and did either f or g, you’d end up at あ. If you were at あ or よ and did f (or g as well on よ) , you’d stay in the same place.
Now you can probably see how this relates to the puzzle from Final Fantasy XIII-2 at this point. Basically, each of the numbers would be one of the states, and there would be two functions, ccw (counter-clockwise) and cw (clockwise). Your goal would be to find a path through the state machine, traversing all values without going over one of them twice.
Now, in order to solve some of the actual puzzles in game, I actually worked out finite state machine graphs to use as an aids in solving them, labeling each state as the number labeled on it and a superscript if need be to help clarify which number it was if there were duplicate digits. I didn’t bother to keep track of the two functions/inputs (which was which) as that wasn’t relevant to the problem…take a look for yourself. Sorry if it’s a bit messy, this was scratchwork not a homework assignment for a class–lol. It’s an interesting parallel though, don’t you think! :D
So, besides doing this to solve these problems, I was wondering if there was infallible algorithm that could actually be followed to solve these problems on the computer (I’m figuring this may be too cumbersome to do by hand, but if you can prove me otherwise, go for it). (If you don’t understand the next few sentences, that’s fine–feel free to skip over the rest of this paragraph) I was figuring that these could be done by creating a matrix of sorts with rows corresponding to x (original state values) and columns corresponding to cw/ccw(x)=y (destination values) that has true (1) values when one of the functions maps to a given value, else 0. The i-th row’s state would have to correspond to the i-th column’s state in this matrix for all i. If one could interchange corresponding rows and columns (keeping the i-th row corresponding to the i-th column by interchanging the corresponding columns/rows after interchanging rows/columns respectively) in a way such that you’d end up with a diagonal of true values above the main diagonal, that would be a solution…problem is though I’m pretty sure I’d need a pivoting/interchange algorithm to get that done, else I wouldn’t get anywhere with those interchanges unless I already knew the solution. Some feedback on this would be nice…thanks!
Oh and I know I could do this with guess and check or constrained guess and check on the computer, but that’s not the point. (Skip the next part if you don’t understand…) Straight guess and check has a complexity of O(n!) in this case anyway (being that there are n! possible paths to check, n being the number of numbers in the puzzle), which isn’t good–a faster algorithm that could be scaled (even though that isn’t relevant to this case as n<14 in all these puzzles in game), would be more interesting.