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.
$\begingroup$
$\endgroup$
6
$\begingroup$
$\endgroup$
3
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;
}
-
$\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
$\begingroup$
$\endgroup$
3
I try with combinatorics addition and multiplication principle. I just share my try. if there is any improvement, please suggest.
-
$\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
12364possible by backtracking1236(321)4? $\endgroup$ – Peter Taylor Jan 11 '14 at 11:35