Jtdylktuy

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.

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;

                        points++;                      //adding middle points

                        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 << " iterationsn"; 

              }



              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 calledn";   // 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='';

    while(ans=='')

    {                   //just waiting

    cin >> ans;

    }



    return 0;

}

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