We have a square grid of n rows and n columns, i.e. it contains n*n squares in all. Each square can be either on or off. now we have a toggle operation such that if it is applied on any square it toggles all the squares that have a side common to the square(including the square itself). So, in a 3*3 matrix we have initially all off then when we perform toggle on say (2,2) then (1,2) (2,1) (2,2) (2,3) (3,2) are turned on.So, for any value of n supplied by user, we have to find a sequence of operations so that if all the squares intially are off they are turned on after that sequence.
For example, the sequences for n=1, 2, and 3 are:
n=1 (1,1)
n=2 (1,1) (1,2) (2,1) (2,2)
n=3 (1,1) (1,3) (2,2) (3,1) (3,3)
Taken from here w/0 a solution
^^ Interesting site with a lot of good questions/puzzles.
Don't read too many of them, b/c I will probably use them later :-p
Bonus (from me, not from the original puzzle) is find an algorithm that will produce a sequence that will work for an arbitrarially sized nxn matrix and only turns on a single specified square (e.g. leave a 5x5 matrix, initially off, with only the (1,3) spot on.
Also, what if the matrix was in an arbitrary initial state besides all being off and trying to turn them all on at the same time. What if some were on and others were off .... could an algorithm be devised which could take that board to a given state through a series of actions as described above?
I have no idea if either is possible....
6 comments:
what rules apply to 'edge effects'. Does your board universe wrap back onto itself from the opposite edge? I mean if you toggle a square in the middle of one edge, then it has no square to affect next to it on one side. Does it then do nothing, or does it toggle the corresponding square on the opposite edge?
my guess would be that nothing happens on that side
Some intial thoughts:
Each toggle operation toggles 5 little squares at most, when the named target is not on any edge. The 5 little squares make a T shape. An operation that names a little square on the edge toggles only 4 little squares. An operation at the corner, toggles 3 squares.
Obviously you can churn your solution by toggling unnecessarily over an over and end up with a good result, so a 'good' solution should be fairly efficient, requiring less operations.
Any odd number of toggles for an individual square leaves it in an off position. Thus in the end, each little square was toggeled an odd number of times, although not necessarily the same number of times as it's neighbors.
This make me ask, for very large n, could the middle of the space undergo only 1 toggle per little square, i.e. maximum efficiency? I tried overlapping T shapes in Visio and quickly found that one configuration does this. I'm emailing you a .bmp of the layout. this would be the ideal arrangement of T-shaped operations away from the edge. maybe you can post it as one fact.
Near the edges, one has to be wasteful, operating repeatedly on some small squares in order to get to the one's missed in the incomplete pattern. There's probably a most efficient way to do this too. The corners would then pose a special problem.
However, when you get to small n, like your three examples, the situation is reversed. The pattern affected by one operation becomes large compared to the space and it get's confusion finding an efficient heuristic. However, at the same time, the small space might allow some kind of brute force tree solution, trying every combination of nxn squares as your next 'move' and trying to explore the tree one depth at a time, to avoid churning.
Any of this make sense as a start?
Check this out.
I threw together an applet (requires jre 1.4) that lets you create arbitrary grids and click tiles on/off (off is black, colors are on) and keeps track of the sequence for you
it may help in figuring out some of the patterns.
(don't make the grids too big ... due to some rounding you can get a division by zero error that I didn't notice until later and didn't bother to fix .... also if you click on the lowest portion of the last row you "might" be able to just toggle that single square instead of the T like your supposed to ... not sure why yet)
After experimenting with your tool I realized some useful properties of the toggle operations in problem:
Property 1 - Any even number of succesive operations on the same location yields the same result. This includes zero or no operations.
Property 2 - Any odd number of successive operations on the same location yields the same result, including just a single operation.
Property 3 - Any sequence order of the same set of operations yields the same result.
Because of these properties, all proposed sequences of operations can be reduced to a simplest set, where each location is toggled either zero or one time.
Therefore the infinite set of possible sequences of operations can be reduced to a finite set. There are only 2^(nxn) unique operation sequences possible.
It was clear w/o these rules that the space can only exist in 2^(nxn) states, each square either being on or off. However the above properties and their consequence was not clear at first. It means that there is one simplest set of operations to get to any state, the order of which is irrelevant, and that the nubmer of possible operations sets exactly equals the number of possible outcomes. Doesn't this infer that there is only 1 possible solution to get from any of the states to any of the other states?
Thus a brute force method arrives . . create an algorithm that tries all 2^(nxn) simplest sets of operations sequences until one ends on the "all on" state. That sequence is the one and only one solution.
See any flaws in this thinking?
I used brute force programming to solve the 1x1 thru 4x4 problems and was surprised. At n=4 I demonstrated that some of my conclusions are incorrect. The solutions do not need to be radially symmetric and there is more than one solution possible that is not simply a rotation of a previous solution by a multiple of 90 degrees.
Note the following 16 solutions for the 4x4 case:
(2,4), (4,3), (1,2), (3,1)
(3,4), (1,3), (4,2), (2,1)
(1,4), (4,4), (2,2), (3,2), (2,1), (3,1)
(1,4), (3,3), (4,3), (3,2), (4,2), (1,1)
(2,4), (3,4), (2,3), (3,3), (1,1), (4,1)
(4,4), (1,3), (2,3), (1,2), (2,2), (4,1)
(1,4), (2,4), (1,3), (2,3), (4,3), (3,2), (2,1), (4,1)
(1,4), (3,4), (2,3), (1,2), (3,2), (4,2), (3,1), (4,1)
(2,4), (4,4), (3,3), (1,2), (2,2), (4,2), (1,1), (2,1)
(3,4), (4,4), (1,3), (3,3), (4,3), (2,2), (1,1), (3,1)
(1,4), (2,4), (3,4), (1,3), (3,3), (1,2), (3,2), (1,1), (2,1), (3,1)
(1,4), (2,4), (3,4), (4,4), (1,3), (4,3), (1,2), (2,2), (3,2), (4,2)
(1,3), (2,3), (3,3), (4,3), (1,2), (4,2), (1,1), (2,1), (3,1), (4,1)
(2,4), (3,4), (4,4), (2,3), (4,3), (2,2), (4,2), (2,1), (3,1), (4,1)
(1,4), (2,4), (4,4), (1,3), (2,3), (3,3), (2,2), (3,2), (4,2), (1,1), (3,1), (4,1)
(1,4), (3,4), (4,4), (2,3), (3,3), (4,3), (1,2), (2,2), (3,2), (1,1), (2,1), (4,1)
Also satisfying is that there exists a mere 4 toggle sequence that converts the entire 4x4 to all ON without a single small square being changed more than the minimum once.
All 3 properties still seem true, but my subsequent conclusions seem all incorrect.
Post a Comment