Place 9 non-zero digits into the squares of a 3x3 chessboard so that any 2 consecutive digits share a common side of 2 neighboring squares.
In how many ways can this task be achieved?
The assumption here, from the title's "routes" that we want paths using all the digits from 1 to 9 in order forming a path, or route, through the chessboard grid.
clc, clearvars
global n n2 grid howMany history dupCt
n=3; n2=n*n; howMany=0; history = {}; dupCt=0;
grid=zeros(n);
for r1=1:n
for c1=1:n
grid(r1,c1)=1;
r=r1; c=c1;
addon(1,r,c)
end
end
disp([howMany dupCt howMany-dupCt])
function addon(wh,r,c)
global n n2 grid howMany history dupCt
grid(r,c)=wh;
if wh<n2
for dr=-1:1
for dc=-1:1
if (dr~=0 || dc~=0) && (dr==0 || dc==0)
row=r+dr; col=c+dc;
if row>0 && col>0
if row<=n && col<=n
if grid(row,col)==0
addon(wh+1,row,col)
end
end
end
end
end
end
else
% disp(grid)
% disp(' ')
howMany=howMany+1;
history{end+1,1}=grid;
if howMany>1
dup=false;
for i=1:4
for j=1:howMany-1
if isequal(grid,history{j,1})
dup=true;
break
end
if dup break
end
end
grid=rot90(grid);
end
gridf=flip(grid);
for i=1:4
for j=1:howMany-1
if isequal(gridf,history{j,1})
dup=true;
break
end
if dup break
end
end
gridf=rot90(gridf);
end
if dup
% disp('dup')
dupCt=dupCt+1;
else
disp(grid) % this version does not display trivial
disp(' ') % rotations and reflections
end
end
% disp(' ')
end
grid(r,c)=0;
end
finds 40 distinct paths, but 35 are rotations or reflections of others, marked as dup below the grid in the list below:
1 2 3
6 5 4
7 8 9
1 2 3
8 7 4
9 6 5
1 2 3
8 9 4
7 6 5
1 2 9
4 3 8
5 6 7
1 4 5
2 3 6
9 8 7
dup
1 6 7
2 5 8
3 4 9
dup
1 8 7
2 9 6
3 4 5
dup
1 8 9
2 7 6
3 4 5
dup
3 2 1
4 5 6
9 8 7
dup
3 2 1
4 7 8
5 6 9
dup
3 2 1
4 9 8
5 6 7
dup
9 2 1
8 3 4
7 6 5
dup
5 4 1
6 3 2
7 8 9
dup
7 6 1
8 5 2
9 4 3
dup
7 8 1
6 9 2
5 4 3
dup
9 8 1
6 7 2
5 4 3
dup
3 2 9 (here is another
4 1 8 non-duplicate)
5 6 7
9 2 3
8 1 4
7 6 5
dup
3 4 5
2 1 6
9 8 7
dup
9 8 7
2 1 6
3 4 5
dup
5 4 3
6 1 2
7 8 9
dup
7 8 9
6 1 2
5 4 3
dup
5 6 7
4 1 8
3 2 9
dup
7 6 5
8 1 4
9 2 3
dup
3 4 5
2 7 6
1 8 9
dup
3 4 5
2 9 6
1 8 7
dup
3 4 9
2 5 8
1 6 7
dup
9 8 7
2 3 6
1 4 5
dup
5 6 7
4 3 8
1 2 9
dup
7 6 5
8 9 4
1 2 3
dup
9 6 5
8 7 4
1 2 3
dup
7 8 9
6 5 4
1 2 3
dup
5 4 3
6 7 2
9 8 1
dup
5 4 3
6 9 2
7 8 1
dup
9 4 3
8 5 2
7 6 1
dup
7 8 9
6 3 2
5 4 1
dup
7 6 5
8 3 4
9 2 1
dup
5 6 7
4 9 8
3 2 1
dup
5 6 9
4 7 8
3 2 1
dup
9 8 7
4 5 6
3 2 1
dup
40 35 5
Again, the five that are non-duplicates of previous paths (not rotations or reflections) are:
1 2 3
6 5 4
7 8 9
1 2 3
8 7 4
9 6 5
1 2 3
8 9 4
7 6 5
1 2 9
4 3 8
5 6 7
3 2 9
4 1 8
5 6 7
A case could be made that, for example the path with 1 in the center (#5), spiralling out counterclockwise is basically the same as the one with 9 in the center and spiralling out clockwise down to 1 (#3). Similarly, if traced out, #2 looks like #4 traced backward and rotated. The rotation-catching feature of the program already caught the reverse path of the first example when it looked at
9 8 7
4 5 6
3 2 1
from the viewpoint of starting with 1 at the lower right.
That leaves only three that are fundamentally different shaped paths:
1 2 3
6 5 4
7 8 9
1 2 3
8 7 4
9 6 5
1 2 3
8 9 4
7 6 5
The others are rotations, reflections, or reversals from 1-9 to 9-1.
Edited on June 24, 2021, 11:45 am
|
|
Posted by Charlie
on 2021-06-24 11:43:36 |
solution and discussion
