Math Like question

Alright, so I foind this game online
http://www.ebaumsworld.com/sloyd.html

Now, what I want to know, what is the minimum possible moves to complete this puzzle in, mathmatically speaking... Just kind of curious

Thread moved from 'General Chat' to 'Programming Theory' by Matt.

Reason: You'll get a better answer here.

This is far from a complete proof, but it's a start:

There are 2,050,860,883,500 possible patterns (that's 27!/(9!*9!*8!)).
Since we don't care which of the 9 squares in the yellow side ends up with the blank, 9 of those are equally valid end states.

The average branching factor for any move is 2.333.
Reason: 2 moves for each of the 3 outside corners, 3 moves for the 12 outside edges, and 4 moves for the 12 interior squares. You have to subtract one move from each though since you had to get there somehow and one move would simply go backwards. So the average is 63/27 = 2.333.

So, 34 (= ceil(log 2050860883500 base 2.333)) moves is theoretcially enough to reach all possible states. I'm sure there are multiple ways to reach some states though, so you might need a little more room. I'd expect the lowest possible score to be less than 36 or 37 though.

coolness, thanks