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 '14 at 6:31
  • $\begingroup$ @T.Bongers - This being a math site, maybe someone here will come up with a less "brute force" method. $\endgroup$ – nbubis Jan 11 '14 at 6:57
  • $\begingroup$ Is 12364 possible by backtracking 1236(321)4? $\endgroup$ – Peter Taylor Jan 11 '14 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$ – travis bickle Jan 11 '14 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 '14 at 8:32
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$ – Petite Etincelle Aug 16 '14 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$ – Ali Caglayan Aug 16 '14 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 '18 at 5:40
-2
$\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$ – Jaroslaw Matlak Oct 19 '18 at 12:33
  • 1
    $\begingroup$ @JaroslawMatlak Going to $8,6$(directly from $1$) is legal $\endgroup$ – Anvit Dec 28 '18 at 4:58
  • $\begingroup$ @Anvit You're right. But still 3,7 and 9 are not legal. $\endgroup$ – Jaroslaw Matlak Dec 28 '18 at 16:45

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.