How many combinations does Android pattern have?

Rules- 1) At-least 4 and at-max 9 dots must be connected. 2) There can be no jumps

3) Once a dot is crossed, you can jump over it.

• stackoverflow.com/questions/6979524/…
– user61527
Jan 11, 2014 at 6:31
• @T.Bongers - This being a math site, maybe someone here will come up with a less "brute force" method. Jan 11, 2014 at 6:57
• Is 12364 possible by backtracking 1236(321)4? Jan 11, 2014 at 11:35
• 1236(321)4 is not possible as between 6 and 4 is 5. However, this is possible- 51236(5)4 Jan 11, 2014 at 11:51
• It's not clear whether a crossed dot that is jumped over later is counted. For example is 21(2)3654789 counted as 10 dots and hence not allowed? If so, there is a relatively simple mathematical way to find the answer. Aug 16, 2014 at 8:32

I think it's impossible to find it in a combinatory way, I used a recursive research to find it and it gave me the answer 487272. Under there is the c++ code. But a lot of sites posts a lesser answer, 389112. I'd like to see a more matematical way to solve this.

#include <iostream>
#include <stdlib.h>
using namespace std;

int combo;  //counter

void research(int Ipoints /*number of points already took*/, bool Icheck[9]/*points matrix*/,int Ilast/*last took point*/,
int Icomboval/*combination representation, only for printing purpose*/, int deep/*number of iteration, only for printing purpose*/)
{

//  int numcall = 0;  //DEBUG

for( int i=0; i<9; i++) //Controlling every free point in search of a valid way to contimue
if( Icheck[i] == false )
{
//Just for security, coping every variable in a new variable. I don't know how c++ works but I will make it works
int points = Ipoints;
int last = Ilast;
int comboval = Icomboval;
bool check[9];
for( int j=0; j<9; j++)
check[j] = Icheck[j];

int e1,e2;
int middle = -1;
e1=i; e2=last;  //Controlling duble jumps
if( e1 == 0 && e2 == 2 ) middle = 1;
if( e1 == 3 && e2 == 5 ) middle = 4;
if( e1 == 6 && e2 == 8 ) middle = 7;
if( e1 == 0 && e2 == 6 ) middle = 3;
if( e1 == 1 && e2 == 7 ) middle = 4;
if( e1 == 2 && e2 == 8 ) middle = 5;
if( e1 == 0 && e2 == 8 ) middle = 4;
if( e1 == 6 && e2 == 2 ) middle = 4;

e2=i; e1=last;  // in both way
if( e1 == 0 && e2 == 2 ) middle = 1;
if( e1 == 3 && e2 == 5 ) middle = 4;
if( e1 == 6 && e2 == 8 ) middle = 7;
if( e1 == 0 && e2 == 6 ) middle = 3;
if( e1 == 1 && e2 == 7 ) middle = 4;
if( e1 == 2 && e2 == 8 ) middle = 5;
if( e1 == 0 && e2 == 8 ) middle = 4;
if( e1 == 6 && e2 == 2 ) middle = 4;

if((middle != -1) && !(check[middle])) {
check[middle] = true;
comboval *= 10;
comboval += middle;
}

check[i] = true;
points++;           // get the point

comboval*=10;
comboval += i+1;

if(points > 3)
{
combo++; // every iteration over tree points is a valid combo

// If you want to see they all, beware because printing they all is truly slow:
// cout << "Combination n. " << combo << " found: " << comboval  << " , points " << points << " with " << deep << " iterations\n";
}

if(points > 9)   //Just for sure, emergency shutdown,
{ exit(1); }

research(points,check,i,comboval,deep+1); /*Recursive, here is the true program!*/

// numcall++; //DEBUG
}

//   cout << "Ended " << deep << " , with " << numcall << " subs called\n";   // Only for debug purposes,remove with all the //DEBUG thing

}

int main ()
{
combo = 0; //no initial knows combo
bool checkerboard[9];
for( int i=0; i<9; i++) checkerboard[i]=false; //blank initial pattern

research(0/*no point taken*/,checkerboard,-1/*just a useless value*/,0/*blank combo*/,1/*it's the firs iteration*/); //let's search!

cout << "\n"  ;
cout << "And the answer is ... " << combo << "\n"; //out

char ans='\0';
while(ans=='\0')
{                   //just waiting
cin >> ans;
}

return 0;
}

• Please add more details, what are you trying to find here? Aug 16, 2014 at 8:42
• This is a brute-force search and is a valid approach. However it does not show any mathematical way of approaching the answer. This should probably be CW. Aug 16, 2014 at 10:39
• I'm getting an even smaller answer $248408$. Here's the code if anyone wants to see pastebin.com/7Em5QthR Dec 28, 2018 at 5:40

I try with combinatorics addition and multiplication principle. I just share my try. if there is any improvement, please suggest.

• Your solution does not implement the requirement of no jumps. For example starting from button 1 you cant go straight to 3,6,7,8,9, but only to 2,4 and 5. Oct 19, 2018 at 12:33
• @JaroslawMatlak Going to $8,6$(directly from $1$) is legal Dec 28, 2018 at 4:58
• @Anvit You're right. But still 3,7 and 9 are not legal. Dec 28, 2018 at 16:45