Now that I think on it, I’m not sure Kvho ever ‘places’ a piece on the board, merely keeps a parallel array of the changes and a running count of the number of flips. When that parallel array becomes the inverse of the board, and the number of flips remaining is zero, the board is solved…
Of course. That’s another reason to invert it.
Most of the time Shifter spends, is spent placing a piece on the board. You don’t even have to bother seeing how the pieces look on the board until your flips remaining is zero.
That seems so obvious now.
Kvho sorts pieces based on the number of squares in them, not the number of potential moves. This is to decrease the number of flips remaining as fast as possible. This one change would probably speed things up a lot. In fact, pieces are stored, not as maps, but as an array of offsets of the non-empty squares in each piece. This means that a piece’s empty area is never even considered.
My Shifter never even had a chance. It did as well as it could based on how I set it up.
You never have to compare a board position against zero or any other value. If the last piece can be placed without causing any flips, that’s a solved board. And if there are any flips left when it comes to placing the last depth-1 pieces, just leave, because there’s no way to fill it.
13 Comments
Hey, I am amazed that you were able to create a program to solve shapeshifter. I am new to the game, and after a few hours of playing I am currently stuck at level 26 x_x Ive tried everything possible and spent my time calculating moves but it still somehow messes up somewhere. Do u have any tips on how to beat this level and a few level above it ? Im really close to the high score table. Any help would be appreciated
Bill
I’d like to know if you could share this program you’ve made…
I still at level 25… When the *3 changes* came, I just got a little depressed =/
Please, I’d like if you could give it…
Thanks.
Heyllord.
bleh… my solver got me to level 40 something. but i haven’t looked at it for a few years.
My solver, if I gave it away, would be useless to you unless you knew Python; and as I haven’t solved Shapeshifter to 100, I don’t even know if it will work for anyone including me. Shifter is user-unfriendly and I haven’t taken even the slightest steps toward making it useful for anyone else
Though I wanted to. I had the idea that I would take some time and make a great UI for it, turn it into a one-button solver (that you would still need to run under Linux, Shifter’s native environment), but then I got sane and realized a fancy UI meant nothing if it couldn’t solve the puzzle.
My entire goal with Shapeshifter is to make myself a better programmer. Using someone else’s program to solve it is pointless, don’t you think?
I DID merge my page scraper with Kvho, and I still run it in parallel with Shifter — level 81, which Shifter solved this morning in 36 seconds, Kvho solved in 2 seconds. And in fact, both Shifter and Kvho arrived at the same solution. I’m not proud of the fact that I spent days figuring out how Kvho worked, saw how similar we were in some ways (re: flips), and different in others (offset maps and transform vectors, which I immediately borrowed).
Part of the reason I gave up back in September was just the pointlessness of using someone else’s program to get a high score. So now I’m back with many new approaches to try with Shifter to get back to my goal of writing a BETTER solver than Kvho, possibly by using multiple processors.
Anyway, I see this all like the pod racer race in that Star Wars movie, where we race built on all our little cobbled-together programs, and hopefully at the end, we can give each other a peek at them. I will admit that I will not really respect someone who never wrote their own solver, and just used Kvho to do it (unless they are Kvho, in which case, I want to bask in their divine light, because that is some imaginative programming).
I’ve mentioned Kvho enough here that I imagine everyone who has wanted to use his program has found it already, and figured out how to use it, so you will never find that code hosted here.
I have been working on my own Shapeshifter solving program in “C” for some time now to help my daughter solve the puzzles and I was happy to find others out there like me who drawn into the challenge of finding a way to solve the puzzles. I was also amazed that we seem to follow the same course of attack until we discover that our new enemy is processing time.
I am not a programmer. I do it as a hobby. My main objective at this point of the programming is to cut processing time. I am trying to abstract from your comments how you were able to cut the processing time down. I am not sure I am catching the meaning of your words: “flip” and “inverse”. Is “flip” referring to the change occurs when the puzzle piece is place over the puzzle. It must not be because I don’t see how you are solving the puzzle in one or two flips.
Any, advice or explanation would greatly be appreciated.
Hiya, Jayzer!
I call it a flip when you place a piece over a solved square “flipping” it back to the unsolved state. You can mathematically prove how many flips there are in any puzzle; once you have reduced the puzzle to zero remaining flips, you drastically reduce the number of possible moves remaining. My solver is based on reducing the number of flips to zero as swiftly as possible. Obviously, starting out with very few flips means the puzzle would be significantly easier than one with a lot of flips, all other things being equal.
Since even in the best of worlds, some puzzles take a very long time to solve — what I call 146 year puzzles — it’s good to have a benchmark to let you know when you might want to discard the puzzle and get another. Counting the flips is a quick (though not always accurate) metric.
Thanks for your last reply.
I have realized by reading the posts that switching my program to bitwise operations would vastly increase the speed of my program and it has. It was fairly easy to understand. Up until this point I have built my program out of multi-dimensional matrixes filled with “0’s” and “1’s” and sometimes “2’s” if my symbols followed the rule 2 -> 1 -> 0 -> 2 where “0″ is my goal. Now that I am flipping bits on and off I only have “1’s” and “0’s” to work with. What did you do when you had three symbols like the preceding example?
I moved back to one byte per cell, eventually, but used a vector instead of an array and built optimized piece placing routines. I didn’t ever pick them up again — I just kept an array of vectors and just moved up and down them. I wrote that part in ‘C’ (my main solver is in Python) for performance.
Later, I took inspiration from Kvho and stored my pieces as arrays of offsets rather than sparse matrices, and that *really* sped things up.
But the number one optimization was flips. Sensei (who helped me with the later stages) had a more mathematical approach which I don’t have — but it shows there are many ways to solve the puzzle.
Even at my best times, there were puzzles I could not solve in a reasonable amount of time.
Thanks for the help. I am not that familiar with vectors so I will have to read up on them. Sounds like I have a lot to learn along the way, maybe I will be a programmer when I finally reach level 100. I might drop in occasionally with a question if I get stuck. I appreciate your help so far.
Thanks again.
I’ve been searching, but I can’t find Kvho anywhere. I’m really interested in looking through some of its code. Does no one have it or a link to it?
I have Kvho.
a) I know nothing about code.
b) I would like to know how to “create” a solver.
Well, knowing how to code would be a necessary first step