6
$\begingroup$

My phone is unlocked using a security pattern. This is a path drawn through a 3x3 grid of dots with the following rules:

  • The path can start at any dot
  • The path visits neighbouring dots: horizontally, vertically or diagonally
  • The path visits every dot exactly once and it cannot cross itself

Now I am wondering how secure is this system - how many legal patterns would a hacker need to try in order to find mine and unlock the phone?

$\endgroup$
  • $\begingroup$ is the condition of atleast 4 dots to be connected for a pattern included in the problem statement :P? $\endgroup$ – Sagar Chand Jun 4 at 5:37
  • 2
    $\begingroup$ That condition creates too many paths. So I made it that you must visit EVERY dot. $\endgroup$ – Dmitry Kamenetsky Jun 4 at 5:42
  • $\begingroup$ How is this a puzzle? $\endgroup$ – melfnt Jun 4 at 9:26
  • 1
    $\begingroup$ I was about to post an answer when I realised I'd solved a different problem to the one asked, having failed to notice the "it cannot cross itself" condition - which seems weird, as practically every time I've seen those kinds of security patterns used, the path DOES cross itself (e.g. 159863247 would be valid). Another surprising discovery was that (on at least the modified problem I solved), there are MORE paths if you stop at (say) 5 dots rather than insisting on visiting all 9. $\endgroup$ – Steve Jun 4 at 16:25
  • $\begingroup$ Steve I would be interested to see your answer to the crossing paths version anyway. Feel free to post it. $\endgroup$ – Dmitry Kamenetsky Jun 4 at 23:45
9
$\begingroup$

It is easiest to focus on the middle dot, which must be visited at some point. The other 8 dots are in a ring and all connected to the middle dot.

Let's first ignore diagonal steps between edge dots, i.e. only look at paths along the black edges in this diagram:

enter image description here

This splits into several cases.
1. The path starts at the middle dot. The next dot can be any of the other $8$, and then the rest can be visited clockwise or anti-clockwise. This gives $16$ paths.
2. The path ends at the middle dot. Same as above but in reverse. Again $16$ paths.
3. The middle dot is internal to the path, so there is a next and a previous dot.
3a. The next and previous dots are adjacent. There are $8$ possibilities for the next dot, and then $2$ possibilities for the previous adjacent dot. The remaining 6 dots can be split between the head and tail of the path, and this can be done in $7$ ways (the head can have any length 0 to 6). This gives $8*2*7=112$ paths.
3b. The next and previous dots are non-adjacent. There are $8$ possibilities for the next dot, and $5$ for the non-adjacent previous dot. The head/tail must go in the same direction but can be clockwise or anti-clockwise. This gives $8*5*2=80$ paths.

The total number of paths is $16+16+112+80=224$.

What remains is to count the paths that use one or more of the off-diagonals that were so far ignored.

The path cannot use two of those off-diagonals steps one after the other. This would split the rest of the dots into 3 disjoint regions, and we only have two ends of the path to fill them.
The only way to use two of the diagonals is to use two opposite ones. This gives you essentially this unique path:
enter image description here
Counting rotations, reflections, and path direction, this accounts for $8$ solutions.
The last case is to count those paths that use exactly one of the off-diagonals. One end of the path ends at the corner that is cut off by the off-diagonal step.
enter image description here
The other end must visit the 5 remaining outer dots and the centre dot. There are 6 choices of when to visit the centre dot (visiting 0 to 5 of the other dots first). Once that is decided, there is no choice for which dots to visit before reaching the centre. Once in the centre, the remaining dots can be visited in clockwise or anti-clockwise order, provided there are 2 or more remaining. This gives a total of 10 ways to finish the path.
Rotating, reflecting, and reversing these 10 paths gives $10*4*2*2=160$ solutions.

The total number of solution paths is therefore:

224+168=392

I wrote a C# program to check this, and it gives the same answer. Here is the code:

  using System;
  namespace TempProg
  {
     class PSEPhone
     {
        private static readonly int[][] Adjacent = 
        {  // The neighbours for each dot.
           new[] {1, 3, 4}, new[] {0, 2, 3, 4, 5}, new[] {1, 4, 5},
           new[] {0, 1, 4, 6, 7}, new[] {0, 1, 2, 3, 5, 6, 7, 8}, new[] {1, 2, 4, 7, 8},
           new[] {3, 4, 7}, new[] {3, 4, 5, 6, 8}, new[] {4, 5, 7}
        };
        //{
        //   // only main diagonals. off-diagonals excluded
        //   new[] {1, 3, 4}, new[] {0, 2, 4}, new[] {1, 4, 5},
        //   new[] {0, 4, 6}, new[] {0, 1, 2, 3, 5, 6, 7, 8}, new[] {2, 4, 8},
        //   new[] {3, 4, 7}, new[] {4, 6, 8}, new[] {4, 5, 7}
        //};

        private static readonly int[][] Crossing =
        {
           new[] {0, 4, 1, 3}, new[] {1, 5, 2, 4},
           new[] {3, 7, 4, 6}, new[] {4, 8, 5, 7},
        };

        public static void Main()
        {
           int[] path = new int[9];
           bool[] used = new bool[9];
           int count = 0;
           for (int i = 0; i < 9; i++)
           {  // for each starting dot
              path[0] = i;
              used[i] = true;
              count += SearchPath(path, used, 1);
              used[i] = false;
           }
           Console.WriteLine(count);
        }

        private static int SearchPath(int[] path, bool[] used, int ix)
        {
           if (ix == 9)
           {  // found a path
              for (int i = 0; i < 9; i++)
                 Console.Write(path[i]+1);
              Console.WriteLine();
              return 1;
           }
           int count = 0;
           foreach (int next in Adjacent[path[ix-1]])
           {  //for each neighbour
              if (!used[next])
              {  // that hasn't already been used
                 path[ix] = next;
                 if (HasCrossing(path, ix)) continue;
                 used[next] = true;
                 count += SearchPath(path, used, ix + 1);
                 used[next] = false;
              }
           }
           return count;
        }

        private static bool HasCrossing(int[] path, int ix)
        {  // check whether path just crossed itself
           int a = path[ix];
           int b = path[ix-1];
           foreach (int[] crs in Crossing)
           {
              if (crs[0] == a && crs[1] == b) return HasDiagonal(path, ix, crs[2], crs[3]);
              if (crs[0] == b && crs[1] == a) return HasDiagonal(path, ix, crs[2], crs[3]);
              if (crs[2] == a && crs[3] == b) return HasDiagonal(path, ix, crs[0], crs[1]);
              if (crs[2] == b && crs[3] == a) return HasDiagonal(path, ix, crs[0], crs[1]);
           }
           return false;
        }

        private static bool HasDiagonal(int[] path, int ix, int v1, int v2)
        {  // check whether path uses given (diagonal) edge
           for (int i = 1; i < ix; i++)
           {
              int a = path[i];
              int b = path[i - 1];
              if (a == v1 && b == v2)
                 return true;
              if (a == v2 && b == v1)
                 return true;
           }
           return false;
        }
     }
  }
| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ If we label the dots with numpad numbers, your solution doesn't count, for example, the paths 598741263 and 142357869. $\endgroup$ – Magma Jun 4 at 12:39
  • $\begingroup$ Thank you Magma! Tick removed for now. $\endgroup$ – Dmitry Kamenetsky Jun 4 at 14:12
  • 1
    $\begingroup$ @Magma Very good observation. I had completely overlooked those diagonals. I'll see if I can count those. $\endgroup$ – Jaap Scherphuis Jun 4 at 14:25
  • 1
    $\begingroup$ I also wrote a computer program to verify it, just to be sure. $\endgroup$ – Jaap Scherphuis Jun 5 at 7:43
  • 1
    $\begingroup$ @DmitryKamenetsky: I added the program code. $\endgroup$ – Jaap Scherphuis Jun 5 at 11:35
3
$\begingroup$

[As commented, this started by answering a different problem with a different answer... I didn't exclude crossing paths, giving a larger figure than the intended answer]

Given the small size of the problem space, I did a somewhat inelegant "brute force" search (not even using the symmetry of the problem to reduce the search space in any way).

The total number of paths found was

784

Although the puzzle didn't call for a solution, it'd still be nicer to see a more elegant solution that could be followed "by hand" - and while I was away from the computer, I see the other answer was indeed updated to make it much clearer...

Using minor variations of the program, I also checked the number of valid codes for other maximum counts:

MaxCount: 1 - Total: 9
MaxCount: 2 - Total: 40
MaxCount: 3 - Total: 160
MaxCount: 4 - Total: 496
MaxCount: 5 - Total: 1208
MaxCount: 6 - Total: 2240
MaxCount: 7 - Total: 2984
MaxCount: 8 - Total: 2384
MaxCount: 9 - Total: 784
MaxCount: 10 - Total: 0

This was found using the following C# program:

static readonly int[][] AdjacentIds = new[]
{
  new[]{ 1,2,3,4,5,6,7,8,9 },
  new[]{ 2,4,5 },
  new[]{ 1,3,4,5,6 },
  new[]{ 2,5,6 },
  new[]{ 1,2,5,7,8 },
  new[]{ 1,2,3,4,6,7,8,9 },
  new[]{ 2,3,5,8,9},
  new[]{ 4,5,8 },
  new[]{ 4,5,6,7,9 },
  new[]{ 5,6,8 },
};

static int MaxCount = 9;

static IEnumerable<List<int>> GetPaths(int from, int doneMask, int doneCount)
{
  if (doneCount == MaxCount)
    yield return new List<int>(9);
  else
  {
    foreach (var to in AdjacentIds[from])
    {
      int thisMask = 1 << to;
      if ((doneMask & thisMask) == 0)
      {
        foreach (var result in GetPaths(to, doneMask | thisMask, doneCount + 1))
        {
          result.Add(to);
          yield return result;
        }
      }
    }
  }
}


static public void Main()
{
  int count = 0;
  foreach (IEnumerable<int> path in GetPaths(0, 1, 0))
  {
    Console.Write($"{string.Join("", path.Reverse())} ");
    count++;
  }
  Console.WriteLine($"\nTotal: {count}");
}

... the output of which was as follows:

123547869 123547896 123569847 123569874 123574869 123574896 123596847 123596874 123654789 123657489 123659847 123659874 123684759 123687459 123689547 123689574 123695478 123695487 123695748 123695784 123695847 123695874 123698457 123698475 123698547 123698574 123698745 123698754 124536987 124578963 124753689 124753698 124758963 124759863 124785369 124785963 124786359 124786953 124789536 124789563 124789635 124789653 124875369 124875963 124896357 125369847 125369874 125478963 125748963 126354789 126357489 126359847 126359874 126984753 126987453 142356987 142357869 142357896 142359687 142365789 142365987 142368759 142368957 142369578 142369587 142369857 142369875 142536987 142578963 142635789 142635987 142698753 145236987 145326987 145789623 145789632 147523689 147523698 147532689 147532698 147589623 147589632 147598623 147598632 147852369 147853269 147859623 147859632 147862359 147863259 147869523 147869532 147895236 147895263 147895326 147895362 147895623 147895632 147896235 147896253 147896325 147896352 147896523 147896532 148752369 148753269 148759623 148759632 148962357 148963257 152369847 152369874 152478963 153247869 153247896 153269847 153269874 153624789 153698742 154236987 154789623 154789632 156324789 156987423 157423689 157423698 157489623 157489632 157842369 157896324 158742369 158963247 159632478 159632487 159687423 159863247 159874236 159874263 214536987 214578963 214753689 214753698 214758963 214759863 214785369 214785963 214786359 214786953 214789536 214789563 214789635 214789653 214875369 214875963 214896357 215369847 215369874 215478963 215748963 235147869 235147896 235698741 235968741 236514789 236598741 236874159 236895147 236895741 236951478 236951487 236957841 236958741 236984157 236984751 236985147 236985741 236987415 236987451 236987514 236987541 241536987 241578963 247896351 251478963 253698741 263514789 263598741 269874153 321456987 321457869 321457896 321459687 321475689 321475698 321475869 321475896 321475968 321475986 321478569 321478596 321478659 321478695 321478956 321478965 321486957 321487569 321487596 321489657 321547869 321547896 321569847 321569874 321574869 321574896 321596847 321596874 324156987 324157869 324157896 324159687 324786951 324789651 325147869 325147896 325698741 325968741 326514789 326598741 326874159 326895147 326895741 326951478 326951487 326957841 326958741 326984157 326984751 326985147 326985741 326987415 326987451 326987514 326987541 351247869 351247896 351269847 351269874 351426987 351478962 352147869 352147896 352698741 354126987 354789621 356214789 356987412 356987421 357412689 357412698 357489621 357841269 357896214 357896241 358741269 358962147 359621478 359621487 359687412 359687421 359862147 359874126 362145789 362145987 362147589 362147598 362147859 362147895 362148759 362148957 362154789 362157489 362159847 362159874 362415789 362415987 362478951 362514789 362598741 365124789 365214789 365987412 365987421 368741259 368742159 368951247 368952147 368957412 368957421 369512478 369512487 369521478 369521487 369578412 369578421 369587412 369587421 369841257 369842157 369847512 369847521 369851247 369852147 369857412 369857421 369874125 369874152 369874215 369874251 369874512 369874521 369875124 369875142 369875214 369875241 369875412 369875421 412356987 412357869 412357896 412359687 412365789 412365987 412368759 412368957 412369578 412369587 412369857 412369875 412536987 412578963 412635789 412635987 412698753 415236987 415326987 415789623 415789632 421536987 421578963 423698751 451236987 457896321 475123689 475123698 475896321 475986321 478512369 478596321 478632159 478695123 478695321 478951236 478951263 478953621 478956321 478962153 478962351 478963215 478963251 478963512 478963521 478965123 478965321 487512369 487596321 489632157 512369847 512369874 512478963 514236987 514789623 514789632 521478963 523698741 532147869 532147896 532698741 536214789 536987412 536987421 541236987 547896321 563214789 569874123 574123689 574123698 574896321 578412369 578963214 578963241 587412369 589632147 596321478 596321487 596874123 598632147 598741236 598741263 621478953 623514789 623598741 632145789 632145987 632147589 632147598 632147859 632147895 632148759 632148957 632154789 632157489 632159847 632159874 632415789 632415987 632478951 632514789 632598741 635124789 635214789 635987412 635987421 653214789 659874123 687412359 689532147 689574123 695321478 695321487 695784123 695874123 698412357 698475123 698475321 698532147 698574123 698741235 698741253 698741523 698741532 698742153 698742351 698745123 698745321 698751423 698753214 698753241 698754123 741235689 741235698 741235869 741235896 741235968 741235986 741236589 741236598 741236859 741236895 741236958 741236985 741253689 741253698 741258963 741259863 741263589 741263598 741268953 741269853 741523689 741523698 741532689 741532698 741589623 741589632 741598623 741598632 742153689 742153698 742158963 742159863 742368951 742369851 745123689 745123698 745896321 745986321 748512369 748596321 748632159 748695123 748695321 748951236 748951263 748953621 748956321 748962153 748962351 748963215 748963251 748963512 748963521 748965123 748965321 751236984 751248963 751423689 751423698 751489623 751489632 752148963 752369841 753214869 753214896 753269841 753621489 753698412 753698421 754123689 754123698 754896321 756321489 756984123 758412369 758963214 758963241 759632148 759684123 759841236 759841263 759863214 759863241 784123569 784123596 784123659 784123695 784125369 784125963 784126359 784126953 784152369 784153269 784159623 784159632 784215369 784215963 784236951 784512369 784596321 785142369 785412369 785963214 785963241 786321459 786324159 786951423 786953214 786953241 786954123 789514236 789514263 789536214 789536241 789541236 789541263 789563214 789563241 789621453 789623514 789623541 789624153 789632145 789632154 789632415 789632451 789632514 789632541 789635124 789635142 789635214 789635241 789635412 789635421 789651423 789653214 789653241 789654123 841236957 847512369 847596321 857412369 859632147 863214759 869532147 869574123 874123569 874123596 874123659 874123695 874125369 874125963 874126359 874126953 874152369 874153269 874159623 874159632 874215369 874215963 874236951 874512369 874596321 875142369 875412369 875963214 875963241 895362147 895632147 895741236 895741263 896214753 896235147 896235741 896321457 896321475 896321547 896321574 896324157 896324751 896325147 896325741 896351247 896352147 896357412 896357421 896532147 896574123 951236847 951236874 951247863 951423687 951478623 951478632 952147863 952368741 953214786 953268741 953621478 953621487 953687412 953687421 954123687 954786321 956321478 956321487 956874123 957412368 957486321 957841236 957841263 957863214 957863241 958632147 958741236 958741263 962147853 962148753 962351478 962351487 962357841 962358741 963214578 963214587 963214758 963214785 963214857 963214875 963215478 963215487 963215748 963215784 963215847 963215874 963241578 963241587 963247851 963248751 963251478 963251487 963257841 963258741 963512478 963512487 963521478 963521487 963578412 963578421 963587412 963587421 965321478 965321487 965784123 965874123 968412357 968475123 968475321 968532147 968574123 968741235 968741253 968741523 968741532 968742153 968742351 968745123 968745321 968751423 968753214 968753241 968754123 984123657 984126357 984751236 984751263 984753621 984756321 985362147 985632147 985741236 985741263 986214753 986235147 986235741 986321457 986321475 986321547 986321574 986324157 986324751 986325147 986325741 986351247 986352147 986357412 986357421 986532147 986574123 987412356 987412365 987412536 987412563 987412635 987412653 987415236 987415263 987415326 987415362 987415623 987415632 987421536 987421563 987423651 987426351 987451236 987451263 987453621 987456321 987514236 987514263 987536214 987536241 987541236 987541263 987563214 987563241
Total: 784

I subsequently modified the program to answer the actual question, by classifying each path according to how many crossings it included. (Only the added and changed function are shown below)

static int CountCrossings(List<int> path)
{
  // crossing occurs iff two pairs of consecutive digits have the same total with a difference of 2 or 4
  var totalsSeen = new HashSet<int>();
  int crossings = 0;
  for (int i = 0; i < path.Count - 1; i++)
  {
    int diff = Math.Abs(path[i + 1] - path[i]);
    if ((diff == 2 || diff == 4) && totalsSeen.Add(path[i + 1] + path[i]) == false)
    {
      crossings++;
      path[i] *= -1; // after reversing and printing, this will show the crossing as a '-' between numbers!
    }
  }
  return crossings;
}

static public void Main()
{
  var countByCrossings = new int[4];
  int count = 0;
  foreach (var path in GetPaths(0, 1, 0))
  {
    int crossings = CountCrossings(path);
    Console.Write($"{string.Join("", ((IEnumerable<int>)path).Reverse())}({crossings}) ");
    count++;
    countByCrossings[crossings]++;
  }
  Console.WriteLine($"\n0 crossings: {countByCrossings[0]}, 1 crossing: {countByCrossings[1]}, 2 crossing: {countByCrossings[2]}, 3 crossing: {countByCrossings[3]}, Total: {count}");
}

The final line of output (the rest became uglier and was mainly used for debug purposes!) was as follows:

0 crossings: 392, 1 crossing: 352, 2 crossing: 40, 3 crossing: 0, Total: 784

Which agrees with the total shown in the better answer.

Once again modifying for different totals:

MaxCount 0 - 0 crossings: 1, 1 crossing: 0, 2 crossing: 0, 3 crossing: 0, Total: 1
MaxCount 1 - 0 crossings: 9, 1 crossing: 0, 2 crossing: 0, 3 crossing: 0, Total: 9
MaxCount 2 - 0 crossings: 40, 1 crossing: 0, 2 crossing: 0, 3 crossing: 0, Total: 40
MaxCount 3 - 0 crossings: 160, 1 crossing: 0, 2 crossing: 0, 3 crossing: 0, Total: 160
MaxCount 4 - 0 crossings: 464, 1 crossing: 32, 2 crossing: 0, 3 crossing: 0, Total: 496
MaxCount 5 - 0 crossings: 1032, 1 crossing: 176, 2 crossing: 0, 3 crossing: 0, Total: 1208
MaxCount 6 - 0 crossings: 1712, 1 crossing: 512, 2 crossing: 16, 3 crossing: 0, Total: 2240
MaxCount 7 - 0 crossings: 1976, 1 crossing: 944, 2 crossing: 64, 3 crossing: 0, Total: 2984
MaxCount 8 - 0 crossings: 1344, 1 crossing: 928, 2 crossing: 112, 3 crossing: 0, Total: 2384
MaxCount 9 - 0 crossings: 392, 1 crossing: 352, 2 crossing: 40, 3 crossing: 0, Total: 784
MaxCount 10 - 0 crossings: 0, 1 crossing: 0, 2 crossing: 0, 3 crossing: 0, Total: 0

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ That's a nice and concise program! Great work. It is interesting that your answer is exactly double of Jaap's answer. If there is one crossing path for every non-crossing path, then perhaps there is a one-to-one correspondence between the two sets? Can we find it? $\endgroup$ – Dmitry Kamenetsky Jun 5 at 6:57
  • 1
    $\begingroup$ @DmitryKamenetsky I think it is mostly a coincidence that the number is doubled, but not entirely. If you have one crossing in a path, then you can replace the crossing diagonal edges by two horizontal edges or two vertical edges, but there is only one way you can do that to get a valid path. Therefore every crossing path is mapped to a non-crossing path. This accounts for most but not all cases. Unfortunately this is mapping is not surjective and not injective. These exceptions are much rarer, and I think it is a coincidence that this balances out exactly. $\endgroup$ – Jaap Scherphuis Jun 5 at 8:10
  • 1
    $\begingroup$ @DmitryKamenetsky a path with $n$ crossings can certainly be converted to one with $n-1$ crossings, by converting the "crossing" section to two parallel lines, but not all non-crossing paths can be converted to crossing ones. The path using two off-diagonals in the answer from JaapScherphuis cannot be trivially converted to a "crossing" path for example. It appears to be a numerical co-incidence. $\endgroup$ – Steve Jun 5 at 8:11
  • $\begingroup$ Thank you both for the explanation. $\endgroup$ – Dmitry Kamenetsky Jun 5 at 8:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.