Already solved by Charlie and Steven Lord, but I proceeded with a computer solution and got the same answer: 40.
---------- Here is my Python code: ---------
/* (since lists in Python are zero based, I defined locations as:
012
345
678
and thus the neighbor locations for location 0, for example, are locations 1 and 3.) */
----------
from itertools import permutations
digits = [1,2,3,4,5,6,7,8,9]
nbr_locs = [[1,3],[0,2,4],[1,5],[0,4,6],[1,3,5,7],[2,4,8],[3,7],[4,6,8],[5,7]]
def isAdjacent(aPerm):
for n in range(1,9):
loc = aPerm.index(n)
other_locs = nbr_locs[loc]
adj = False
for otloc in other_locs:
if aPerm[otloc] == n+1:
adj = True
if not adj:
return False
return True
goodOnes = []
countall = 0
countNbr = 0
for perm in permutations(digits):
countall += 1
if isAdjacent(perm):
countNbr += 1
goodOnes.append(perm)
print(countall)
print(countNbr)
for t in goodOnes:
a=100*t[0]+10*t[1]+t[2]
b=100*t[3]+10*t[4]+t[5]
c=100*t[6]+10*t[7]+t[8]
print('',a,'\n',b,'\n',c)
print('')
------------------------
Since any solution is also a solution if rotated 90 degrees (4 ways), or flipped over (2 ways), at first I thought there should be 5 solutions each with 8 different equivalent rotations/reflections. In fact there are only three patterns which I call the "S", the "G", and the "R". There are 8 instances of the S pattern, and 16 each of the other 2 patterns. The reason is there is one more degree of freedom with the latter two patterns: repeating the pattern going from 1 up to 9 is different than the same pattern going from 9 down to 1.
S 8
G 16
R 16
Technically, I guess you could subdivide "G" and "R" into G up, G down, R up, and R down and thus have 5 patterns each with 8 reflections/rotations.
=======================
123 S
654
789
123 R
874
965
123 G
894
765
129 R
438
567
145 R
236
987
167 S
258
349
187 G
296
345
189 R
276
345
321 S
456
987
321 R
478
569
321 G
498
567
329 G
418
567
345 G
216
987
345 R
276
189
345 G
296
187
349 S
258
167
541 R
632
789
543 G
612
789
543 R
672
981
543 G
692
781
567 G
418
329
567 R
438
129
567 G
498
321
569 R
478
321
761 S
852
943
765 G
814
923
765 R
834
921
765 G
894
123
781 G
692
543
789 G
612
543
789 R
632
541
789 S
654
123
921 R
834
765
923 G
814
765
943 S
852
761
965 R
874
123
981 R
672
543
987 G
216
345
987 R
236
145
987 S
456
321