Wednesday, October 31, 2007

Toggle This! Continued...

I made some progress on the previous puzzle that I didn't think would fit in a comment ...

After trying to aproach the problem from a pattern standpoint and being unable to come up with a simple (if X, do Y, else do Z...) kind of solutions and after talking with my dad and reading his ideas about the mathematics behind a solution I decided to write up a brute force solution that might at least get the creative juices flowing.

Some of my thought process was:
  • As my dad pointed out, toggling the same place more than once give you nothing (you may and probably will need to have tiles toggled more than once by a combination of their neighbors and thereselves, but never in a sequence should the same location appear more than once)
  • Since every location can either be toggled or not toggled in a solution, there are therefore theoretically 2^(n*n) solutions for an nxn table (a lot!)
  • The vast majority are bad solutions, and bad solutions for many reason (ie have multiple holes)
  • A solution needs to have a minimal number of locations in its sequence
  • The easiest way to find possible solutions is to iteritively try each possible solution.
  • It is possible to determine that a particular candidate solution is trash much sooner than the end when applying the toggles in an iterative manor (if you are building your solution column by column and row by row, then you can find that a solution is bad if any square is left off and none of the 5 squares that can toggle it are left to do)
  • By finding bad solutions early, we don't need to worry about determining if the rest of the bad sequence is bad ..... its bad to the bone! This reminded me and stemmed out of a thought about Alpha-beta pruning in AI decision trees.

I therefore wrote up code which would try to build solution sequences in a brute force and interative manor ... but that would "prune" out bad solutions as early as possible and therefore run much more efficient than a pure brute force algorithm which would produce a whole candidate and then evaluate it.

The code I wrote can be found here and here (with non formatted code here and here).

The results were promising, but quickly unverifiable as being complete (its hard to verify a large number of solutions and given that I haven't looked up other solutions, hard to verify as being all of them). Results of my code with n = 1...10 can be found here with there solutions and some summary information.

I am concerned that there is such a desparity in numbers of solutions, but that may just be because of the small sample size I have to work with.

I would have run the code for much larger N, but my solution is proving problematic. Since it is based on recursion and for large N, the possible levels of recursion needed are very very large ... I ended up getting Stack Overflow errors from the JVM. Yep, O(2^(n^2)) is pretty bad ;). I am currently working on a version which wouldn't use recursion which I think will fair much better and be purely CPU bound. The current version is VERY fast and if the JVM wouldn't freak out at the large stack size, could be run very quickly on large N. I will also try tweeking my JVM settings to allocate a much larger stack and smaller heap and try it that way. Heap size looks to be bound by a constant*n*n which is about as good as you can get given the problem.

[ADDED] Also, it seems although I haven't verified it, that working through the matrix in some pattern other than row/column could possible find the problem areas even sooner for the majority of cases. I tried writing up code to "dove-tail?" the sequence (e.g. 0,0 1,0 0,1 2,0 1,1 0,2....) but it had a bug and I reverted back to the current method. I also considered doing a spiral in or out but since I don't know that it will help, I haven't tried yet...

Anyone with coding experience, please glance over my code and let me know if you find any stupid mistakes, optimizations, or cleverness I didn't include. Also let me know if you have found any other solutions, have any other ideas, or basically have any thoughts on the subject. I would rather be told I am wrong about something than go on thinking I am right. :)

....... How about someone else try and find a puzzle for tomorrow (even if this one isn't solved). I don't mind finding them but I want to make sure everyone/anyone is getting what they are interested in and is still wanting to do this.....

2 comments:

Benjamin P Lee said...

I verified that my code produces logically equivelant solutions (radially symetric) which is what I expected it to do. I may add code to check and remove them, especially to try and verify how many of the n=9 ones are different.

Benjamin P Lee said...

I did end up finishing a non-recursive version and it runs with decent speed and in a constant memory space ... however when running it on n=25 or n=26 (i think these were the values, it was last week) ... the code doesn't return an answer in a satisfactory amount of time.

without adding more logging I can't be sure if there is a problem in the logic, if there is no solution for these N, or if they are just not being found and that the pruning is not helping nearly as much for these N.

the amount of time to find a single solutiong for the increasing N was slower than I was anticipating. I think with some better pruning logic, possibly a different way to find the "next location" and some other heuristics, I might be able to cut this down a lot but I am not sure its worth the time.