Imagine there is a 7x7 grid of lights, and only the
middle in the grid is on.
The lights are wired such that when you flip the switch for one light (from on to off or off to on) the others next to it (not diagonally) flip as well.
Using this weird wiring of lights, what is the fewest number of switch changes it takes to turn all the lights off, and which lights should you switch?
Note: Assume all the switches work in the manner explained, and there is one switch for each of the lights.
The code below does not require recursion as each row's switches are completely determined by the previous row's lights. The results of the first found solution through n=21 follow the listing.
An observation is that most of the solutions could, in one rotation or another, be done by marking off a corner by a diagonal of flipped switches forming a triangle of non-flipped switches.
I was going to say that 13 is an exception, but in this case, the diagonal is of length of only 2, with the degenerate triangle being a single non-flipped switch (zero). It's symmetric so it appears in all four corners and the solution is therefore completely unique.
clearvars,clc
for sz=3:2:21
disp(' ')
fprintf('%s %3d\n','size',sz)
rowChoice={}; found=false;
for k=0:sz
c=nchoosek(2:sz+1,k);
for i=1:size(c,1)
rowChoice{end+1}=c(i,:);
end
end
middle=ceil(sz/2);
lowest=999;
for whichSwitches=1:length(rowChoice)
lights=zeros(sz+2); lights(middle+1,middle+1)=1;
switches=zeros(sz+2);
which = rowChoice{whichSwitches};
switches(2,:)=zeros(1,sz+2);
for i=1:length(which)
switches(2,which(i))=1;
for dr=-1:1
for dc=-1:1
if dr==0 || dc==0
lights(2+dr,which(i)+dc)=1-lights(2+dr,which(i)+dc);
end
end
end
end
for row=3:sz+1
switches(row,2:sz+1)=lights(row-1,2:sz+1);
for col=2:sz+1
if switches(row,col)
for dr=-1:1
for dc=-1:1
if dr==0 || dc==0
lights(row+dr,col+dc)=1-lights(row+dr,col+dc);
end
end
end
end
end
end
if isequal(lights(sz+1,2:sz+1),zeros(1,sz))
fprintf([repmat('%2d',1,sz) '\r'],switches(2:sz+1,2:sz+1))
disp(' ')
found=true;
break
% disp(lights(2:sz+1,2:sz+1))
% disp(' ')
% disp(' ')
end
end
end
size 3
0 1 0
1 1 1
0 1 0
size 5
1 0 1 1 0
1 0 0 0 1
0 1 1 0 1
0 0 1 0 0
0 0 0 1 1
size 7
0 0 0 1 0 0 0
0 0 1 1 1 0 0
0 1 0 0 0 1 0
1 1 0 1 0 1 1
0 1 0 0 0 1 0
0 0 1 1 1 0 0
0 0 0 1 0 0 0
size 9
1 1 1 0 0 0 1 1 0
0 1 0 1 0 1 0 0 1
0 0 1 1 0 1 0 0 1
0 0 0 1 0 0 1 1 0
0 0 0 0 1 0 0 0 0
0 0 0 0 0 1 1 1 0
0 0 0 0 0 0 1 0 1
0 0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0 1
size 11
0 1 0 0 0 1 0 1 0 0 0
1 1 1 0 1 1 0 1 1 0 0
0 0 0 0 0 1 0 1 0 1 0
1 1 1 0 0 0 0 0 1 1 1
0 1 0 1 0 1 0 0 0 0 0
0 0 1 1 0 1 1 0 1 1 1
0 0 0 1 0 0 0 0 0 1 0
0 0 0 0 1 1 1 0 0 0 0
0 0 0 0 0 1 0 1 0 1 0
0 0 0 0 0 0 1 1 0 1 1
0 0 0 0 0 0 0 1 0 1 0
size 13
0 1 1 1 0 1 1 1 0 1 1 1 0
1 0 1 0 0 0 1 0 0 0 1 0 1
1 1 0 0 0 0 0 0 0 0 0 1 1
1 0 0 0 0 0 1 0 0 0 0 0 1
0 0 0 0 0 1 1 1 0 0 0 0 0
1 0 0 0 1 0 0 0 1 0 0 0 1
1 1 0 1 1 0 1 0 1 1 0 1 1
1 0 0 0 1 0 0 0 1 0 0 0 1
0 0 0 0 0 1 1 1 0 0 0 0 0
1 0 0 0 0 0 1 0 0 0 0 0 1
1 1 0 0 0 0 0 0 0 0 0 1 1
1 0 1 0 0 0 1 0 0 0 1 0 1
0 1 1 1 0 1 1 1 0 1 1 1 0
size 15
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 1 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 1 0 0 0 0 0
0 0 0 0 1 1 0 1 0 1 1 0 0 0 0
0 0 0 1 0 1 0 1 0 1 0 1 0 0 0
0 0 1 1 1 0 0 0 0 0 1 1 1 0 0
0 1 0 0 0 0 0 1 0 0 0 0 0 1 0
1 1 0 1 1 0 1 1 1 0 1 1 0 1 1
0 1 0 0 0 0 0 1 0 0 0 0 0 1 0
0 0 1 1 1 0 0 0 0 0 1 1 1 0 0
0 0 0 1 0 1 0 1 0 1 0 1 0 0 0
0 0 0 0 1 1 0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
size 17
1 0 1 0 1 1 0 0 0 1 1 1 0 1 1 1 0
1 0 1 0 0 0 1 0 1 0 1 0 0 0 1 0 1
0 0 0 1 1 0 1 0 1 1 0 0 0 0 0 1 1
1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1
1 1 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 1 1
1 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1
1 0 1 0 1 0 1 0 1 1 0 0 0 1 1 1 0
0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0
1 0 1 1 0 0 0 1 1 0 1 0 1 0 1 1 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 1 1 1 0 0 0 1 1 0 1 0 1 0 1 0 1
0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0
0 0 0 1 1 0 1 0 1 1 0 0 0 0 0 1 1
0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 1 1 0 1 1 0 1 1 1 0 1 1
size 19
0 1 0 1 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0
1 1 0 1 0 1 1 0 0 0 0 0 1 1 0 1 1 0 0
0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 1 0 1 0
0 0 1 1 1 0 1 1 1 0 1 1 1 0 0 0 1 1 1
0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 1 1 0 1 1 1 0 0 0 1 1 1
0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 1 0 1 0
0 0 0 0 0 0 1 1 1 0 0 0 1 1 0 1 1 0 0
0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0
0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 1 0 0
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
size 21
0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 1 0 1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 1 1 0 1 0 1 0 1 0 1 1 0 0 0 0 0
0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 0
0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0
0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0
0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0
1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 1
1 1 0 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 0 1 1
1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 1
0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0
0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0
0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0
0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 0
0 0 0 0 0 1 1 0 1 0 1 0 1 0 1 1 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 1 0 1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0
|
|
Posted by Charlie
on 2022-11-13 11:32:26 |
Cleaned-up code for the extension and an observation
