Algorithm for solving Timburr Tile Puzzle

[crashteamalphing]

So last night I was trying to solve that puzzle, and after 5 minutes I realized I was just wasting my time and there was a much easier solution.

I made a code in c++ that goes through all 4^16=4.2 billion possibilities of moving tiles, and see which ones lead to solving the puzzle, given the initial rotation state of all tiles.

Unfortunately 4.2 billion is a large number, so the code takes a very long time to be executed (like, hours or days). However, what is interesting is that there seems to be more than 1 correct way of reaching a given final state from a given initial state. For example, I had the following initial state :

0000

0000

0000

2002

where 0 represents a tile that is correct, and each time a tile rotates, it increases by +1 (modulo 4, i.e. 4=0).

I had only gone through the first billion possibilities (25%) and I had already found 16 different solutions. However, I found 0 solutions in the next billion which leads me to believe that there are only 16 solutions every time the puzzle is solvable. (since there are 4^16 final states, and 4^16 possibilities of moving tiles, if there are 16 ways of reaching some final states, that also means that only 1/16 final states are reachable, luckily the correct solution is one of them).

Anyway, apparently the initial state of the puzzle is different each time you play, so I can't just post the solution like that. Best I can do is to give you the code I used. Once you manage to run it, you just enter for each 16 tiles their current rotation state (0,1,2,3), and it finds for you how many times you have to click on each tile to solve the puzzle (for example, click twice on tile 1, don't click on tile 2, click 3 times on tile 3, etc...). The tiles are numbered as follows :

1 2 3 4

5 6 7 8

9 10 11 12

13 14 15 16

The code :

#include <iostream>

#include <vector>

using namespace std;

vector<int> increase(vector<int> init, vector<int> inc){

vector<int> fin(16);

fin[0]=(init[0]+inc[0]+inc[1]+inc[4])%4;

fin[3]=(init[3]+inc[3]+inc[2]+inc[7])%4;

fin[12]=(init[12]+inc[12]+inc[8]+inc[13])%4;

fin[15]=(init[15]+inc[15]+inc[14]+inc[11])%4;

fin[1]=(init[1]+inc[1]+inc[0]+inc[2]+inc[5])%4;

fin[2]=(init[2]+inc[2]+inc[1]+inc[3]+inc[6])%4;

fin[4]=(init[4]+inc[4]+inc[0]+inc[8]+inc[5])%4;

fin[7]=(init[7]+inc[7]+inc[3]+inc[6]+inc[11])%4;

fin[8]=(init[8]+inc[8]+inc[4]+inc[12]+inc[9])%4;

fin[11]=(init[11]+inc[11]+inc[7]+inc[15]+inc[10])%4;

fin[13]=(init[13]+inc[13]+inc[12]+inc[14]+inc[9])%4;

fin[14]=(init[14]+inc[14]+inc[13]+inc[15]+inc[10])%4;

fin[5]=(init[5]+inc[5]+inc[4]+inc[6]+inc[1]+inc[9])%4;

fin[6]=(init[6]+inc[6]+inc[5]+inc[7]+inc[2]+inc[10])%4;

fin[9]=(init[9]+inc[9]+inc[8]+inc[10]+inc[4]+inc[12])%4;

fin[10]=(init[10]+inc[10]+inc[9]+inc[11]+inc[6]+inc[14])%4;

return fin;

}

int main (int argc, char * const argv[]) {

vector<int> initvalues(16);

for(int i=0; i<16;++i){

cout << "Enter value for tile n." << i+1 << endl;

cin >> initvalues;

}

vector<int> increments(16);

vector<int> finalvalues(16);

int test=0;

int counter=0;

int solnumber=0;

for(int i1=0;i1<4;++i1){

for(int i2=0;i2<4;++i2){

for(int i3=0;i3<4;++i3){

for(int i4=0;i4<4;++i4){

for(int i5=0;i5<4;++i5){

for(int i6=0;i6<4;++i6){

for(int i7=0;i7<4;++i7){

for(int i8=0;i8<4;++i8){

for(int i9=0;i9<4;++i9){

for(int i10=0;i10<4;++i10){

for(int i11=0;i11<4;++i11){

for(int i12=0;i12<4;++i12){

for(int i13=0;i13<4;++i13){

for(int i14=0;i14<4;++i14){

for(int i15=0;i15<4;++i15){

for(int i16=0;i16<4;++i16){

++counter;

if(counter%10000000==0){

cout << "iteration n." << counter << endl;

}

increments[0]=i1;

increments[1]=i2;

increments[2]=i3;

increments[3]=i4;

increments[4]=i5;

increments[5]=i6;

increments[6]=i7;

increments[7]=i8;

increments[8]=i9;

increments[9]=i10;

increments[10]=i11;

increments[11]=i12;

increments[12]=i13;

increments[13]=i14;

increments[14]=i15;

increments[15]=i16;

finalvalues=increase(initvalues,increments);

test=0;

for(int i=0;i<16;++i){

if(finalvalues!=0){

test=1;

}

}

if(test==0){

++solnumber;

cout << "Solution n." << solnumber << ":" << endl;

for(int i=0;i<16;++i){

cout << "Tile n." << i+1 << " : " << increments << " turns." << endl;

}

}

}}}}}}}}}}}}}}}}

return 0;

}

[gutten_tag]

i-don't-understand-a-single-line-in-this-code-at-all

lol, actually your work is amazing. I won at least 50 Timburrs as well, now i think i got a way on my own to solve the problem (only work like 20-30% all the time) but this is fine. But i can't....write down something like this @_@. Why don't you use picture to describe one example about this? it could be easier to understand @@

[crashteamalphing]

i-don't-understand-a-single-line-in-this-code-at-all

lol, actually your work is amazing. I won at least 50 Timburrs as well, now i think i got a way on my own to solve the problem (only work like 20-30% all the time) but this is fine. But i can't....write down something like this @_@. Why don't you use picture to describe one example about this? it could be easier to understand @@

Hm, well if you don't know c++, you're not gonna understand the code. However, you don't need to understand it to run it. Just copy and paste the code into a text editor, and save the file as whatever.cpp. Then you'll need a program that can compile and run this code for you, but I can't really be of much help here because I'm not very knowledgeable on the subject. All I can say is that I personally use a Mac and the program I use is called Xcode. I remember using Geany on Linux once. As for PC, I don't know.

If you manage to run it though, it looks like that (using my previous example for the initial state of the tile puzzle) :

Enter value for tile n.1

0

Enter value for tile n.2

0

Enter value for tile n.3

0

Enter value for tile n.4

0

Enter value for tile n.5

0

Enter value for tile n.6

0

Enter value for tile n.7

0

Enter value for tile n.8

0

Enter value for tile n.9

0

Enter value for tile n.10

0

Enter value for tile n.11

0

Enter value for tile n.12

0

Enter value for tile n.13

2

Enter value for tile n.14

0

Enter value for tile n.15

0

Enter value for tile n.16

2

iteration n.10000000

iteration n.20000000

iteration n.30000000

iteration n.40000000

iteration n.50000000

iteration n.60000000

iteration n.70000000

iteration n.80000000

Solution n.1:

Tile n.1 : 0 turns.

Tile n.2 : 0 turns.

Tile n.3 : 1 turns.

Tile n.4 : 1 turns.

Tile n.5 : 0 turns.

Tile n.6 : 3 turns.

Tile n.7 : 2 turns.

Tile n.8 : 2 turns.

Tile n.9 : 1 turns.

Tile n.10 : 3 turns.

Tile n.11 : 0 turns.

Tile n.12 : 3 turns.

Tile n.13 : 0 turns.

Tile n.14 : 1 turns.

Tile n.15 : 0 turns.

Tile n.16 : 3 turns.

iteration n.90000000

iteration n.100000000

iteration n.110000000

iteration n.120000000

Solution n.2:

Tile n.1 : 0 turns.

Tile n.2 : 0 turns.

Tile n.3 : 1 turns.

Tile n.4 : 3 turns.

Tile n.5 : 0 turns.

Tile n.6 : 3 turns.

Tile n.7 : 0 turns.

Tile n.8 : 0 turns.

Tile n.9 : 1 turns.

Tile n.10 : 1 turns.

Tile n.11 : 0 turns.

Tile n.12 : 1 turns.

Tile n.13 : 2 turns.

Tile n.14 : 3 turns.

Tile n.15 : 2 turns.

Tile n.16 : 3 turns.

iteration n.130000000

iteration n.140000000

iteration n.150000000

iteration n.160000000

iteration n.170000000

iteration n.180000000

iteration n.190000000

iteration n.200000000

iteration n.210000000

Solution n.3:

Tile n.1 : 0 turns.

Tile n.2 : 0 turns.

Tile n.3 : 3 turns.

Tile n.4 : 1 turns.

Tile n.5 : 0 turns.

Tile n.6 : 1 turns.

Tile n.7 : 0 turns.

Tile n.8 : 0 turns.

Tile n.9 : 3 turns.

Tile n.10 : 3 turns.

Tile n.11 : 0 turns.

Tile n.12 : 3 turns.

Tile n.13 : 2 turns.

Tile n.14 : 1 turns.

Tile n.15 : 2 turns.

Tile n.16 : 1 turns.

iteration n.220000000

iteration n.230000000

iteration n.240000000

etc...

So you need to find out the initial state of your puzzle (each tile has a value between 0 and 3 with 0 corresponding to the correct orientation, and +1 each time it rotates, modulo 4), I explained in original post the numbering system for the tiles (1-16).

Then you put those values in, and the program starts going through every possibility, warning you with a iteration n.x to let you know of how many possibilities (iterations) the program has already searched (there are about 4200000000). Every once in a while it finds a solution. x turns means you've got to click x times on the given tile.

[Simon]

Um.... nice.. gonna go think about this..

[Amethyst]

you wrote a-- what

if youre this bored i dont suppose you know ruby do you

[crashteamalphing]

you wrote a-- what

if youre this bored i dont suppose you know ruby do you

No, I don't know Ruby, sorry . I actually downloaded RPGMaker just to look at how Pokemon Reborn was made and all (I wanted to try and fix the Shell Bell and Knock Off because I was tired of only gaining 1HP each turn, and not getting my 50% power boost, but I couldn't even find where the scripts that implemented Shell Bell or Knock Off were xD).

[pmegakid]

I think I go catch one of the fighting types out in wild lol sawk and the lucha is not that bad.also you forgot to round and divide lol

[Amethyst]

No, I don't know Ruby, sorry . I actually downloaded RPGMaker just to look at how Pokemon Reborn was made and all (I wanted to try and fix the Shell Bell and Knock Off because I was tired of only gaining 1HP each turn, and not getting my 50% power boost, but I couldn't even find where the scripts that implemented Shell Bell or Knock Off were xD).

I have someone helping me out with scripts and he confirmed why Knock Off isn't working, so that will be fixed for E13

Here's a tip though, and a spear behind it when in RMXP's script editor, Ctrl+Shift+F will let you search all script sections for a phrase and jump to it. So you could search for Shell Bell (or internal name SHELLBELL) which would lead you to like ~2275 in PokeBattle_Battler.

But if you don't know Ruby it may be a moot point. Still, if you were able to learn, and subsequently fix/post it, it would be much appreciate so we could integrate it with the next release.

[crashteamalphing]

I have someone helping me out with scripts and he confirmed why Knock Off isn't working, so that will be fixed for E13

Here's a tip though, and a spear behind it when in RMXP's script editor, Ctrl+Shift+F will let you search all script sections for a phrase and jump to it. So you could search for Shell Bell (or internal name SHELLBELL) which would lead you to like ~2275 in PokeBattle_Battler.

But if you don't know Ruby it may be a moot point. Still, if you were able to learn, and subsequently fix/post it, it would be much appreciate so we could integrate it with the next release.

Thanks for the tip

Also I looked at the code section for Shell Bell and I found what I think is a mistake in PokeBattle_Battler line 2253 and 2386 :

# Shell Bell

if isConst?(user.item,PBItems,:SHELLBELL) && damage>0 && user.hp>0

hpgain=user.pbRecoverHP([(damage/8).floor,1].minmax,true)

if hpgain>0

@battle.pbDisplay(_INTL("{1}'s Shell Bell restored its HP a little!",user.pbThis))

end

end

I couldn't test it on Episode 12 because I lack the PBS file to make the change and then compile the game, but I tested it in Episode 11 and it seemed to have done the trick.

[Deleted User]

Yeah I'm not familiar with Ruby, but if it says (min) and the floor is 1. That would probably explain it reaching the floor value all the time. The only thing I'm not understanding from that code is "isConst?", "PBItems", and "pbRecoverHP", ".pbThis"

What do they stand for?

[Amethyst]

..Aha, yes, that would definitely explain it. Great, thank you! I've implemented it for 13

In regards to testing things, if you're interested in helping out with more script stuff, send me a message and I can get those files to you. Lord knows there's plenty to do.

Blind can maybe answer those questions better than I can but "isConst?" asks if a constant is something. PBItems is in reference the items file list items.txt (i guess), and the other two are both functions defined elsewhere in the code. I think. I might be wrong about part of that because I've also just kind of learned as I've gone.

[Deleted User]

Ah that makes sense then. I do want to look into seeing if I can get my hands on RPG Maker for free somewhere, or if I can at least get a free trial. I'd love to be able to help out. Certainly looks easier than the C++ code which makes me feel like a foreign exchange student.

[Amethyst]

There's a free trial of RPG Maker available from a site called 2drpg.com, and if you want to continue helping past the trial date I can probably fix that up for you.

[Deleted User]

Oh absolutely, I'll take a look at it starting Sunday when I get back from Virginia, I have until about Mid August before I have anything significant on my plate.

[Arkhi]

Are you still offering RMXP past the Trial period? I'd like to see if I can learn some RGSS while helping in Reborn.

[Yash]

I'm not sure but cant the same thing be done using the gemini script editor??

EDIT: incase it can't even i would be interested in helping out..

Edited June 19, 2014 by Aquibex

[DJ Mewdeon ft Dan Punk]

Yeah I'm not familiar with Ruby, but if it says (min) and the floor is 1. That would probably explain it reaching the floor value all the time. The only thing I'm not understanding from that code is "isConst?", "PBItems", and "pbRecoverHP", ".pbThis"

What do they stand for?

Someone just showed me this thread, so briefly:

isConst? checks for matching constants, more or less.

PBItems refers to the PBItems script file.

pbRecoverHP is a function that recovers a target's HP value.

pbThis is a self-referencing variable.

That should clear things up a bit.

[Amethyst]

Are you still offering RMXP past the Trial period? I'd like to see if I can learn some RGSS while helping in Reborn.

tbh all it takes to get passed the trial is some clever googling.

keygen

[Gigamantis]

Hm, well if you don't know c++, you're not gonna understand the code. However, you don't need to understand it to run it. Just copy and paste the code into a text editor, and save the file as whatever.cpp. Then you'll need a program that can compile and run this code for you, but I can't really be of much help here because I'm not very knowledgeable on the subject. All I can say is that I personally use a Mac and the program I use is called Xcode. I remember using Geany on Linux once. As for PC, I don't know.

If you manage to run it though, it looks like that (using my previous example for the initial state of the tile puzzle) :

So you need to find out the initial state of your puzzle (each tile has a value between 0 and 3 with 0 corresponding to the correct orientation, and +1 each time it rotates, modulo 4), I explained in original post the numbering system for the tiles (1-16).

Then you put those values in, and the program starts going through every possibility, warning you with a iteration n.x to let you know of how many possibilities (iterations) the program has already searched (there are about 4200000000). Every once in a while it finds a solution. x turns means you've got to click x times on the given tile.

Sorry to bother you, but i was trying your code at www.compileonline.com/compile_cpp11_online.php and it wont let me set the values for the tiles... any help?

[crashteamalphing]

Sorry to bother you, but i was trying your code at www.compileonline.com/compile_cpp11_online.php and it wont let me set the values for the tiles... any help?

Yes, apparently you have to enter the values beforehand on the STDIN Input field, each of the 16 values separated by a space.

However, that won't work, I've tried already. I've also tried entering the values directly into the code, but it didn't work either. I'm presuming it's the length of the execution time that makes it not work. The thing is that even on my computer, it takes many hours for the code to execute, so I don't know about a web compiler..

A more complete program to compile and execute c++ codes might work better.

[Gigamantis]

Yes, apparently you have to enter the values beforehand on the STDIN Input field, each of the 16 values separated by a space.

However, that won't work, I've tried already. I've also tried entering the values directly into the code, but it didn't work either. I'm presuming it's the length of the execution time that makes it not work. The thing is that even on my computer, it takes many hours for the code to execute, so I don't know about a web compiler..

A more complete program to compile and execute c++ codes might work better.

Thanks for the heads up. Will try with a java progr