How many passwords can be formed from this maze?

Question

We are all familiar with the $9$-dotted maze lock screen password that we get in all mobiles phones today.Now if minimum of $3$ consecutive dots can be joined to form a password total how many passwords can be formed?

My attempt:-$${9\choose 3}+{9\choose4}+...+{9\choose8}+{9\choose9}.$$

Now, I suspect this is wrong as when I write $9\choose3$,I choose any 3 dots among the $9$ dots that appear but this can't be as only $3$ consecutive dots can be chosen but here,we are not doing it.

So, what is the correct method to do it?

Definition of password for help:-Look at the figure.The numbers that can be joined are $1-2$,$1-4$ or $1-5$.But ,dots cannot be joined skipping any dot in between.For eg.$1-3,1-6,1-7,1-8$ or $1-9$ cannot be joined.Interestingly it can be noted,dot $5$ can be joined with all other dots(it is the mid-point).Also you can't overwrite over any line-For eg $1-2-1$ is invalid but you can cross over a line at a point.For eg $1-2-6-3-5$ is valid although there is an intersection of two lines.

So,total how many passwords can be formed?

Thanks for any help!!

Answer 1

If a maximum of three dots is used with not allowing to go back, one can try this. I just simplified the problem so that you only speak of Corner (1,3,7,9), Side (2,4,6,8,) Middle (5).

In that case there are only 7 decisions possible:

Corner-Side = 4*2*(5-1)   = 32 (so 4 Corners, from a Corner you can move to only 2 Sides and from Side you can move only in 5 directions to the final dot, but one was already visited because it was the start so subtract 1)
Corner-Middle = 4*1*(8-1) = 28
Middle-Corner = 1*4*(3-1) = 8
Middle-Side = 1*4*(5-1)   = 16
Side-Corner = 4*2*(3-1)   = 16
Side-Middle = 4*1*(8-1)   = 28
Side-Side = 4*2*(5-1)     = 32

This gives a total of 160 possible passwords with 3 dots. Perhaps this is reducible to a formula, but I don't know how yet.

Answer 2

I used a similar method but a tree diagram

Corners (C), Side (S) and Middle (M)

4 C - 2 S then x4 options = 32

      - 1 M then x7 options = 28 totals 60

4 S - 2 C then x2 options = 16

      - 2 S then x4 options = 32

      - 1 M then x7 options = 28 totals 76

1 M - 4 C then x2 options = 8

      - 4 S then x4 options = 14 totals 24

Totals 160.

Interestingly you have the least possibilities when you start in the centre, and most when you start on the side.

Answer 3

Ok my friends I've solved it by a Brute Force algorithm, I'm so happy I managed it. The script I made is in R, so if you want to test it at home you need to install that statistical program.

The main idea of the algorithm is that I just walk through all possibilities that are possible. At every new move (level) I evaluate the coordinates of the neighbors. When I reach maximum depth or the desired length of the password I add 1 to the total of possibilities and move one level up and get the coordinate of the new neighbor.

I made a YouTube video of the script so you can see what it is doing: https://www.youtube.com/watch?v=6uOWSM3N7u8

So for the password lengths I calculated the following number of possibilities:

1. = 9
2. = 40
3. = 160 (just as we determined manually!)
4. = 496
5. = 1208
6. = 2240
7. = 2984
8. = 2384
9. = 784

Note that the number of possibilities tends to decline with larger lengths of passwords. This is because there are more restrictions as some moves lead to "dead-ends" and thus not reaching max_level.

We can also see that all outcomes are divisible by 4 (except for max_level=1). This was something I noticed when calculating manually in my first post. The possibilities are divisible by 4 for length > 1, because there are 4 corners and 4 sides. This means that there are 4 symmetric paths from a corner, 4 symmetric paths from a side. If length > 1 than from the middle you will be forced into either a corner or side, meaning that again there are 4 symmetrical paths. This symmetry could be used to speed up the algorithm and just calculate one of the 4 paths and afterwards multiply by 4.

Ok so there you go, implementing "knight-jumps" will take some extra effort but will also be doable. Then you can also calculate for the real-life thing where these swipes are allowed.

If you want to check out or use the code, go here: https://github.com/sjorsvanheuveln/Android_Lock_Combinations

Answer 4

I have written Python code (Hopefully the Link Works) to answer this question. I have calculated the answer in two different ways and the answer I got agrees in both cases: $$10256$$ The first way is just a brute force depth first search on all keys, based on the adjacency graph of the keypad. The search only counts paths of length $3$ or more, i.e. depth $2$ or more. The second approach exploits symmetry, performing only the depth first search on one corner, one side (non-corner), and the centre. It then multiplies the corner and side results by $4$. If the code link doesn't work I can post the code here upon request. You may also be interested in these numbers:

• Passwords starting from any corner: $1369$
• Passwords starting from any side: $1031$
• Passwords starting from the centre: $656$

I have cross checked my answer against that given by Ansjovis86 and it indeed checks out. Success! To be more explicit, summing up all paths of length $3$ or more from Ansjovis' answer we get:

$$160 + 496 + 1208 + 2240 + 2984 + 2384 + 784 = 10256$$

Answer 5

I think there's a possibility to find some order in this mess, but it's not that easy. The easiest solution seem to be to write a program that enumerates and count the passwords, but a manual solution is certainly within reach.

The breakdown of the problem is to study center-avoiding sequences, because we know that every password can be constructed by combining the five and center-avoiding sequences. There are some facts about these that makes them not too difficult to categorize and count.

First of all we can prove that every center-avoiding sequence can be contained in a minimal sector with angle between $0$ and $7\pi/8$. This is because the argument around the $5$ varies continuously and the argument will have a minimum and a maximum and we can't have them $2\pi$ apart or more. We can't have $2\pi$ because that would mean that it will cross the same digit at the minimum and maximum. It can't be larger because that would mean that between the maximum and minimum there will be an edge that it will have to pass round both the maximum and minimum.

Next fact is that the direction (clockwise/anti-clockwise) can not change arbitrarily. In fact it can only change near either of the ends of the chain. We can see this because if it's to change direction it must return to an argument that has been skipped on the way to the endpoint and the only possibilities are the corner which are surrounded by two edges and it must have come from one of them, turning at the other and then it's locked into the corner.

Third is that given that the chain doesn't change direction, the chain is uniquely determined by the minimal sector containing it, the corners that are skipped and the direction taken.

Similar it's the same given that the chain changes direction at the end of the chain, similar for given that the chain changes direction at the start of the chain and similar given that the chain changes direction at both ends. Given that we identify the direction change as when the chain turns into a corner where it's trapped (eg the sequence 2-6-3 changes direction at the end since it's the 3 that gets trapped).

Fourth if the chain changes direction at either end the minimal sector has to end on an edge at that end and the nearest corner in the sector cannot be skipped. Otherwise any corner can be skipped in the sector.

Fifth sectors of same even length are all congruent since they have a corner in one end and an edge in the other. Sectors of the same odd length however differ in that they have either corners or edges in both ends, but given they have the same kind in the ends they are congruent. The exception of the difference is sectors of length 1 that are all congruent.

Now we're ready to catalogize the chains and count them. We will categorize them by the kind of minimal sector they are in together with the number of corners that are skipped and whether they turn at the ends (not taking into account that they can take two direction for sectors of length larger than 1):

$$\begin{array}{c|cccccc} & 0 & -1 & -2 & -3 & 0_t & -1_t & -2_t & 0_{tt} & -1_{tt} \\ \hline \\ 1 & 1 & & & & \\ 2 & 1 & & & & \\ 3_c & 1 & & & & \\ 3_e & 1 & 1 & & & 1 \\ 4 & 1 & 1 & & & 1 \\ 5_c & 1 & 1 & & & \\ 5_e & 1 & 2 & 1 & & 1 & 1 & & 1\\ 6 & 1 & 2 & 1 & & 1 & 1 & &\\ 7_c & 1 & 2 & 1 & & \\ 7_e & 1 & 3 & 3 & 1 & 1 & 2 & 1 & 1 & 1\\ 8 & 1 & 3 & 3 & 1 & 1 & 2 & 1\\ \end{array} $$

One can note that the table is populated with binomial coefficients, the columns for singly turning chains is empty on the line $5_c$ and $7_c$ because for the chain to turn at one end of the sector the sector would have to end on an edge. For the same reason the even lines are empty for doubly turning chains since they only end on an edge at one of it's ends.

We then can sum up the rows to count all the chains of each type of sector:

$$\begin{array}{c|cccccc} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \hline \\ 1 & 1 \\ 2 & & 1 \\ 3_c & & & 1 \\ 3_e & & 1 & 3 \\ 4 & & & 1 & 2 \\ 5_c & & & & 1 & 1 \\ 5_e & & & 1 & 4 & 4 \\ 6 & & & & 1 & 3& 2 \\ 7_c & & & & & 1 & 2 & 1 \\ 7_e & & & & 1 & 5 & 8 & 4 \\ 8 & & & & & 1 & 4 & 5 & 2 \\ \end{array}$$

Then it's a matter of counting possibilities. For example if we wish to count the number of passwords with four digits we have it to be either a center-avoiding chain of length 4, a center-avoiding chain of length 3 with a 5 at either end or two center-avoiding chains of length 2 and 1 with a 5 inbetween.

According to the chains of length 4 are $96$, we here use that the number of even length sector are eight of each kind and of odd length they are four of each kind. The chains of length 3 are $56$ and these add to two solutions for each (one that starts with 5 and one that ends with 5). Finally the number of chains of length 2 are 24 and the possible number of chains of length 1 that doesn't intersect the first is 6 (because any other of the eight numbers will do), this makes for two set of solutions (starting or ending with a chain of length two) of 144 cases. Adding them up gives:

$$96 + 56 + 56 + 144 + 144 = 496$$

For longer solutions we will run into next complication, when considering solution consisting of a chain of length longer than one followed by 5 and ending in a chain of length longer than one we will have to have that the minimal sector for the chains may not intersect - we cannot use the corners skipped by the other chain since we would get trapped then (we could for length one since that's not a problem then).

For the case of five we start of by counting the chains of length five which are 152 by the same method as shown earlier, we already know that the chains of length four are 96 (each corresponding to two possibilities, with the 5 at the start or end), the chains of length three are 56 and the accopanying chain of length one are 5 for each here to we have two cases for each pair - starting or ending with chain of length one. Now for the case where we have two chains of length two we have to consider each pair category of sectors. We have the cases of two sectors of length two where we can pair them in 40 ways (first we can select any of the eight, but that leaves only five possibilities to select the second). Each section has two chains so we have 160 solutions of this case. In similar way we can see combining a sector of length 2 and one of length 3 (edge-edge) can be done in 16 ways (first selecting the sector of length 3 in four ways and then leaving only four possibly sectors of length 2), each one of these has two chains and we can start or end in the sector of length two, this gives 128 possibilities. Finally we have pair of sectors of length 3, once selecting the first it will only leave one behind and we have two chains each giving 16 possibilities:

$$152 + 96 + 96 + 280 + 280 + 160 + 128 + 16 = 1208$$

On the other hand if it's only the grand total number of combinations that is of interest it's probably easier to calculate that more directly. In order to do this we have to consider each of the pair of the sector types and how many chains these contain no matter of the chain length. In addition we need to know the number of chain of different length to count the number of passwords containing a chain of length larger than one followed by five and a chain of length one. Then we need to consider all chains followed or preceeded by five. And the combination chain of length one a five and a chain of length one and finally the sole five:

$$ 160+128+512+576+128+576+384+16+256+192+288+256+768+256+288+\\ 288+560+768+912+704+240+\\ 24+48+24+96+144+48+216+288+96+432+576+\\ 56+1 = 10305 $$

This method of solving this explains some of the observations made by other solutions:

The reason the number of passwords of length longer than one is divisible by four (in fact eight) follows because of the construction with center-avoiding chains (there are four or eight sectors of each kind and each sector contains chains determined by among other the general direction of the chain).

The reason there are more solutions starting at an edge or corner is because the ones starting at the center is only the single 5 or a 5 followed by a chain, while the one starting at an edge or corner includes both all chains (which already makes them one less than the ones starting at the center) and a chain followed by a five (which doubles the possibilities), then we have all that then continues with a chain.