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.
(In reply to
re(2): extension of the problem by Steven Lord)
In response to the idea I extended my program.
Originally I sought the smallest number of switches toggled, but it was taking too long, so as soon as one solution was found, I had it stop looking for that size.
The program is recursive so it only tries all possibilities a row at a time, and as soon as failure is assured (as in any line found that has any lights remaining even after the next line goes through all possibilities), no further work is done along that branch (pruning the tree).
clearvars,clc
global rowChoice lights switches sz lowest found
for sz=3:2:15
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
rowChoice;
middle=ceil(sz/2);
lights=zeros(sz+2); lights(middle+1,middle+1)=1;
switches=zeros(sz+2);
lowest=999;
addon(2); % row and column numbers are 1 higher to provide a surrounding buffer
end
function addon(row)
global rowChoice lights switches sz lowest found
for i=1:length(rowChoice)
if found
break
end
saveLights=lights; saveSwitches=switches;
w=rowChoice{i};
switches(row,:)=0;
for j=1:length(w)
switches(row,w(j))=1;
for c=w(j)-1:2:w(j)+1
lights(row,c)=xor(lights(row,c),1);
end
for r=row-1:row+1
lights(r,w(j))=xor(lights(r,w(j)),1);
end
end
if row>2
if ~isequal(lights(row-1,2:sz+1),zeros(1,sz))
lights=saveLights; switches=saveSwitches;
continue
end
end
if row==sz+1
if ~isequal(lights(row,2:sz+1),zeros(1,sz))
lights=saveLights; switches=saveSwitches;
continue
end
if sum(switches(2:sz+1,2:sz+1),'all') >= lowest
continue
end
lowest=sum(switches(2:sz+1,2:sz+1),'all');
found=true;
disp(switches(2:sz+1,2:sz+1))
disp(' ')
% disp(lights(2:sz+1,2:sz+1))
% disp(' ')
disp(sum(switches(2:sz+1,2:sz+1),'all'))
disp(' ')
else
addon(row+1)
end
lights=saveLights; switches=saveSwitches;
end
end
size 3
0 1 0
1 1 1
0 1 0
5 switches flipped
size 5
1 1 0 0 0
0 0 1 0 0
1 0 1 1 0
1 0 0 0 1
0 1 1 0 1
11
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
17
size 9
1 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0
1 0 1 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0
0 1 1 0 0 1 0 0 0
1 0 0 1 0 1 1 0 0
1 0 0 1 0 1 0 1 0
0 1 1 0 0 0 1 1 1
25
size 11
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 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
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 1 0 0 0 1 0
43
As I'm posting, it's still trying to find a solution for 13x13.
|
|
Posted by Charlie
on 2022-11-11 12:41:43 |
re(3): extension of the problem
