Not all of them will have a solution !!

While i take sometime to explain the code i have written to generate the same using flex, i was thinking if all the puzzles that get generated randomly will have a solution or not?

Well the Answer is NO... Not all of them will lead to a solution...

Can i prove it?

There are different ways of proving it.

a) What are the possible number of cubes that can come of this format. 9! (nine factorial - Empty cube can occur in 9 positions and all the other 8 numbers can come at each position without repetetion i.e., 9x8! = 9!). We have to prove all 9! cubes will lead to a solution..

b) Prove using induction. Say Cube n has a solution, Cube k+1 has a solution if, k+n has a solution then all 9! cubes will have a solution

c) Proof by contradiction. Find one cube among the 9! that does not have a solution which proves that not all of them will have a solution....

 

I tried the third way - "Proof by Contradiction"... (not sure if this is the name i have to give it for)..

If you start looking at a 2X2 Cube. You will find that there is one possible way by which you cannot reach to a solution... What is it ?? See below:

    

Can you arrange it in the order so that it becomes 1,2,3 (1 and 2 in the first row in that order)?

No you cannot. Reason... Imagine 2x2 Cube elements as running in circle... (circular list!) 1->3->2 and remember even if you go back or forth, possible combinations are the following

• 1->3->2
• 2->1->3
• 3->2->1

Its very simple that we cant get any order other than this. So we cannot reach 1->2->3 state at all.

Now i say that every Cube will have atleast one 2X2 cube inside it. See the example below for a 3x3 cube where assume all the other cells have "Valid Data already filled" and only this 2X2 data forms a circular loop... Now does it have a solution? I say NO.

Here is an application if you want to try it out...