The numeric keyboards of a telephone (left) and a pocket calculator (right) differ in the arrangement of the keys.

123   789
456   456
789   123
  0      0

What is the least number of moves necessary to transfer the keys of the first arrangement into the other arrangement?
One move consists of switching the position of two neighbouring keys (Horizontal, vertical or diagonal) of which the sum is 9, 10 or 11.
Example: In the starting position you can switch 6 and 3, 5 and 6, 4 and 5, 7 and 4, 0 and 9

 

Looking at the possible pairings {(1,9),(1,8),(2,9),(2,8),(2,7),(3,8),(3,7),(3,6),(4,7),(4,6),(4,5),(5,6)}  The toughest numbers to move are 1 and 9.  To move a nine into its final spot will require the 1 or 2.  This is where I started . . . it took me 31 moves. Might be something better if some form of symmetry can be found. Read left to right.

 

123

456

789

 

123   123   123   123   127   127   127   127   187

465   645   675   475   435   485   485   685   625

789   789   489   689   689   639   369   349   349

 

182   182   812   312   318   318   318   318   618

675   635   635   685   625   675   645   465   435

349   749   749   749   749   249   279   279   279

 

418   481   431   431   431   439   489   489   489

635   635   685   625   695   615   685   635   635

279   279   279   879   872   872   172   172   127

 

489   789   789   789

675   645   465   456

123   123   123   123

Edited on July 6, 2005, 7:11 pm

Posted by Leming on 2005-07-06 19:07:24