Quote:
|
Originally Posted by Sharon
This seems like an INCREDIBLY difficult game... is it actually playable (by humans) at the higher levels?
|
Apparently, it is playable unless there are better problem solvers out there than I am. There are, literally, millions of
Neopets users so it's not outrages that some of them have managed to finish the entire string of puzzles (or know programmers who can solve the problem).
By the way, I'm glad to see you participating in various forums, here. Welcome to TFP!
Now, to give some more context to the discussion, here's the puzzle that my algorithm finds intractable.
Quote:
|
Originally Posted by twilight
Hmm, maybe you have overseen one aspekt of my last post - the row by row thing. This highly reduces the number of possible tries and solutions for the remaining lines.
Usually the last row requires the fewest number of shapes to solve than any other row. Once a row is solved, try to solve the next row with the remaining shapes.
Let's take a 8x8 blocks field with 20 shapes. Beginning with the last row, even if the last line requires 14 shapes to be solved, you only have to check, possible shape postions (you only need to multiply all possible x-positions of each shape),e.g.:
2 x 4 x 4 x 8 x 2 x 3 x 4 x 5 x 8 x 3 x 5 x 4 x 6 x 3 = 265.420.800
Why only 14? Easy the 6 remaining shapes are not enough to cover all remaining fields that need to be turned (this may be an additional check in your routine).
I guess, you can imagine that is it very unlikely that you need 14 images to solve the last row. In practice you need around numOfShapes/4, with our 20, this would mean 5 shapes to solve the last line...
With each solved row you GREATLY reduce further calculations, because both, field size and number of shapes to be tested against are reduced.
|
Okay, I did miss this "row by row thing" about your post but, after re-reading your original post as well as this quoted one, I still don't understand what you're saying.
I'm guessing that you made all those numbers up just as an example but I don't know why you think that "6 remaining shapes are not enough to cover all remaining fields." Also, I don't know why you think that "the last row requires the fewest number of shapes to solve than any other row." As far as I can tell, how many shapes each row needs to be solved with is independent of each other. Now, I do understand that the edge rows will statistically have fewer shapes on them but this is just as true for the first row as it is for the last. The second row as much as the second last row, etc... This doesn't sound like what you're trying to say. Furthermore, it sounds like you think that after we "solve" one row, we can use that solution to solve the other rows. Again, as far as I can tell, there are multiple solutions for each row and the only way to know which one contributes to the final solution is to iterate over all combinations of them and see which one actually works.
Going back to your original post, I'm not sure what distinction you're making between solving "one-field" at a time and "checking against a whole line." In order to check that a line is solved you need to verify that each "field" in the line is solved, right?
Finally, is your first language English? If it's not, I'm sure you're doing the best you can and, in all fairness, it's pretty good. If it is your first language, can you proof read your posts, please? Normally, it's not a big deal but when talking about complicated and very technical subjects, grammatical mistakes can seriously impedge clarity. Thank you...
As an aside, I can't help but notice that the two posts that you've made in this thread are the only posts you've ever made on this forum. Did you join this forum just to participate in this thread? If so, I find that very interesting. How did you come across it?
Quote:
|
Originally Posted by JinnKai
Because each state requires 0 or 1 hits in order to achieve the correct state (the sword thing, in this case), the shapes themselves can be abstracted away and you basically have a "Travelling Salesman" situation, do you not?
If so, your problem is NP-Complete, and intractable. If you solve it, you'd be eligible for almost $7 million in research rewards for solving NP-Complete problems of this type.
|
I don't think it's a
travelling salesman problem. It may very well be
NP-complete, I don't know, but the travelling salesman problem is a problem about optimal path finding under very specific constraints and I don't immediately see a reduction to that from ShapeShifter...
I'm glad people are still reading this thread, especially considering how dead Tilted Knowledge has become. I hope no one has given up and this problem because I haven't quite yet. I actually have some new ideas that I haven't implemented yet. I know they will reduce the execution time, I just don't know if they will reduce it enough and I can't until I actually implement them and run the program. Big bucks, no whammies!
Thank you all for participating...