All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers > Sequences
123…9 door to door (Posted on 2022-10-27) Difficulty: 3 of 5
Consider the sequence of 9 non zero distinct digits arranged in a 3 by 3 grid , like
547
398
162
Clearly there are 9! (=362880) ways to do it.
If we demand that the consecutive numbers are next-door neighbours
( horizontally or vertically) like
167
258
349
then the number is significantly lower, say N.

Find N & provide your reasoning.

See The Solution Submitted by Ady TZIDON    
Rating: 5.0000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution computer solution; note on patterns | Comment 5 of 27 |
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


  Posted by Larry on 2022-11-02 14:43:55
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (9)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information