8
$\begingroup$

Example

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

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

$\endgroup$
6
  • $\begingroup$ stackoverflow.com/questions/6979524/… $\endgroup$
    – user61527
    Jan 11, 2014 at 6:31
  • $\begingroup$ @T.Bongers - This being a math site, maybe someone here will come up with a less "brute force" method. $\endgroup$ Jan 11, 2014 at 6:57
  • $\begingroup$ Is 12364 possible by backtracking 1236(321)4? $\endgroup$ Jan 11, 2014 at 11:35
  • $\begingroup$ 1236(321)4 is not possible as between 6 and 4 is 5. However, this is possible- 51236(5)4 $\endgroup$ Jan 11, 2014 at 11:51
  • $\begingroup$ 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. $\endgroup$
    – user21820
    Aug 16, 2014 at 8:32

2 Answers 2

1
$\begingroup$

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 << " 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;
}
$\endgroup$
3
  • $\begingroup$ Please add more details, what are you trying to find here? $\endgroup$ Aug 16, 2014 at 8:42
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 16, 2014 at 10:39
  • $\begingroup$ I'm getting an even smaller answer $248408$. Here's the code if anyone wants to see pastebin.com/7Em5QthR $\endgroup$
    – Anvit
    Dec 28, 2018 at 5:40
-1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Oct 19, 2018 at 12:33
  • 1
    $\begingroup$ @JaroslawMatlak Going to $8,6$(directly from $1$) is legal $\endgroup$
    – Anvit
    Dec 28, 2018 at 4:58
  • $\begingroup$ @Anvit You're right. But still 3,7 and 9 are not legal. $\endgroup$ Dec 28, 2018 at 16:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .