Define a Board :
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 |
| 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 |
| 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 |
| 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 |
| 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 |
| 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 |
Define a Reverse-Board
| 64 | 63 | 62 | 61 | 60 | 59 | 58 | 57 |
| 56 | 55 | 54 | 53 | 52 | 51 | 50 | 49 |
| 48 | 47 | 46 | 45 | 44 | 43 | 42 | 41 |
| 40 | 39 | 38 | 37 | 36 | 35 | 34 | 33 |
| 32 | 31 | 30 | 29 | 28 | 27 | 26 | 25 |
| 24 | 23 | 22 | 21 | 20 | 19 | 18 | 17 |
| 16 | 15 | 14 | 13 | 12 | 11 | 10 | 9 |
| 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
A 'Move' is defined as a horizontal or vertical swap between adjacent cells on the board.
The puzzle is -- How many minimum Moves are required to transform Board to Reverse-Board.
2 comments:
2*p*(p+1)*(p-1)/3
So solve this problem we can think of layers. The outer layer rotates a complete circle thus having 14 moves for each piece. There are 14 pieces in the outer layer so there are 14 * 14 moves to get the outer layer perfectly from Board to Reverse-Board. Similarly doing for all the layers for this particular case, the solution is
14^2 + 10^2 + 6^2 + 2^2 = 336
Pratik and Santosh correctly generalized this case, for a p x p Board to Reverse-Board the number of moves required are 2p(p^2-1)/3
Post a Comment