There are 16 buttons in a four by four array. Each button has a horizontal arrow, pointing left or right, and a vertical arrow, pointing up or down. Initially, all arrows point towards the center of the array. In the below diagram, U is up, D is down, R is right, and L is left.
DR DR DL DL
DR DR DL DL
UR UR UL UL
UR UR UL UL
When you press a button, all other buttons in the direction of its horizontal arrow flip their vertical arrows, while all other buttons in the direction of the vertical arrow flip their horizontal arrows. The following diagram is the result after pressing the button in the upper left corner.
DR UR UL UL
DL DR DL DL
UL UR UL UL
UL UR UL UL
Find the least number of button presses required to get to the position in which all arrows point away from the center of the array.
(In reply to
re(4): Solution by Penny)
If the solution requires, say, 10 button pushings, and you're hoping for random presses to come up with a solution, there are 16^10 sequences of 10 to test (or 4*16^9 if you use Tristan's symmetrybased reduction). That's 1,099,511,627,776 (or 274,877,906,944). And it multiplies 16fold for each additional move it might take for the solution.
And you have to decide how long a sequence to allow for, in spacing the resets to the initial position.
Those are big haystacks, so even if there are more than one solution, they're hard to find by randomly peeking around.

Posted by Charlie
on 20061106 09:39:22 