20# gogdizzy
我之前跟你有同样的质疑，
目前也还没深入看 无心大神的 代码,猜想是做了标记。
从跑的结果来看，无心人没有错，所以 能计算出所有合法的情况。
21# wayne
跑了一下无心人的程序，结果中确实没有5 2 7 3 4
wayne确认一下这个序列是合法的吗？
如果是合法的，那么就有可能你俩都错了。反倒是你之前给的结果数目较多，有可能正确。
22# gogdizzy
是合法的。
那我再看看我的代码
我修改了一下无心人的代码，添加了一个next2的数组，这个数组用来查找跳跃关系，
例如next2[*] = 3,2,3,5,9,4,7,0,0,0,
表示对于1，有3种跳跃可能，当2被mask了，就可以跳到3，当5被mask了，就可以跳到9，当4被mask了，就可以跳到7.
代码如下：
#include <stdio.h>
int mask = {1,0,0,0,0,0,0,0,0,0};
int next =
{0,0,0,0,0,0,0,0,0,0,
5,2,4,5,6,8,0,0,0,0,
7,1,3,4,5,6,7,9,0,0,
5,2,4,5,6,8,0,0,0,0,
7,1,2,3,5,7,8,9,0,0,
8,1,2,3,4,6,7,8,9,0,
7,1,2,3,5,7,8,9,0,0,
5,2,4,5,6,8,0,0,0,0,
7,1,3,4,5,6,7,9,0,0,
5,2,4,5,6,8,0,0,0,0,
};
int next2 = {
0,0,0,0,0,0,0,0,0,0,
3,2,3,5,9,4,7,0,0,0,
1,5,8,0,0,0,0,0,0,0,
3,2,1,5,7,6,9,0,0,0,
1,5,6,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,
1,5,4,0,0,0,0,0,0,0,
3,4,1,5,3,8,9,0,0,0,
1,5,2,0,0,0,0,0,0,0,
3,6,3,5,1,8,7,0,0,0,
};
int counter = {0,0,0,0,0,0,0,0,0,0};
int graph = {0,0,0,0,0,0,0,0,0,0};
int nextNumber = 0;
int graphPostion = 0;
void circle( int graphPostion )
{
int i, k;
int noPostion = 1;
int n = graph;
for (i = 1; i <= next; i ++)
{
if (mask] == 0)
{
noPostion = 0;
mask] = 1;
graph = next;
counter ++;
printf( "find%d: ", graphPostion + 1 );
for( int z = 0; z < graphPostion + 1; ++z ) printf( "%d ", graph );
puts( "" );
circle( graphPostion + 1 );
mask] = 0;
}
}
for (i = 1, k = 1; i <= next2; i ++, k += 2) {
if (mask] == 1 && mask] == 0 ) {
mask] = 1;
graph = next2;
counter ++;
printf( "2find%d: ", graphPostion + 1 );
for( int z = 0; z < graphPostion + 1; ++z ) printf( "%d ", graph );
puts( "" );
circle( graphPostion + 1 );
mask] = 0;
}
}
}
void first( void )
{
int i;
for (i = 1; i <= 9 ; i ++)
{
mask = 1;
graph = i;
counter ++;
circle( graphPostion + 1 );
mask = 0;
}
}
int main ( void )
{
int i;
first( );
for (i = 1; i <= 9; i ++)
printf("%d: %d\n", i, counter);
return 0;
}
最后运行结果：
1: 9
2: 56
3: 320
4: 1624
5: 7152
6: 26016
7: 72912
8: 140704
9: 140704
和你最开始给的答案一致。
24# gogdizzy
对16# 代码做了一点点的改动，跟楼上的gogdizzy结果对上了，也跟我最开始的结果对上了。，:handshake
所以，我也知道我和无心人错在哪了。
有时候结果一致，不一定就是正确的哈，:lolPointsToBeChecked[{{a_,b_},{c_,d_}}]:=Module[{g=GCD},If,{}]];
n=3;ddd=Flatten,1];
bb=Table[{ii,Product,ddd=Select&/@Complement-1,1],ii],{ii,ddd}],1],Length]],#[]]]==0&];Length},{ii,2,n^2}]
gogdizzy ,:victory:
有木有兴趣试试 4×4的情况
17# wayne
更正如下，求核对：
2,172
3,1744
4,16880
5,154680
6,1331944
7,10690096
后面的，我的改进版的程序也还是力不从心了，
在我2G内存的工作电脑上，Mathematica 抱怨：No more memory available.
Mathematica kernel has shut down.
Try quitting other applications and then retry.
wayne 发表于 2013-6-24 16:34
gogdizzy ,
有木有兴趣试试 4×4的情况
哎，刚才试了一下，根本就算不过来，因为即使不考虑跳跃，每个数周围平均大概有10个可以连的。否则可能性更多，而最长的一条线应该是16个都用上，那就是10^15量级的搜索量，如果考虑跳跃，就是（10+x）^15了。我这里修改了一个通用程序，然后在circle里做了剪枝（超过一定长度就不计算了），结果如下：
1 : 16
2 : 172
3 : 1744
4 : 16880
5 : 154680
6 : 1331944
7 : 10690096
======添加一个结果=======
8 : 79137824
9 : 533427944
10 : 3221413136
11 : 17068504632 // 这个算了一个小时，再长一位可能又要增加10倍时间了。
12 : 77129797424
13 : 285415667080
最前沿的结果
程序代码：#include <cstdio>
#include <vector>
using namespace std;
#defineLEN4
#definePTS(LEN * LEN)
int mask = {0};
int counter = {0};
int graph = {0};
int neibNumber = 0;
int graphPostion = 0;
vector< int > neib;
intgcd( int a, int b ) {
intt;
while( b ) {
t = a % b;
a = b;
b = t;
}
returna;
}
voidinit_neib() {
// init counter
for( int i = 0; i < LEN; ++i )
for( int j = 0; j < PTS; ++j ) {
neib.clear();
neib.push_back( 0 );
}
#defineXY2IDX( r, c ) ( ( r ) * LEN + ( c ) )
#defineCHECK( r0, c0, r1, c1 ) \
do { intrd = abs( r0 - r1 ); \
intcd = abs( c0 - c1 ); \
intgd = gcd( rd, cd ); \
intrs = ( r1 - r0 ) / gd; \
intcs = ( c1 - c0 ) / gd; \
intidx0 = XY2IDX( r0, c0 ); \
intidx1 = XY2IDX( r1, c1 ); \
for( int i = 1; i <= gd; ++i ) neib.push_back( XY2IDX( r0 + i * rs, c0 + i * cs ) ); \
++neib; \
rs = -rs; cs = -cs; \
for( int i = 1; i <= gd; ++i ) neib.push_back( XY2IDX( r1 + i * rs, c1 + i * cs ) ); \
++neib; \
} while(0)
intr0, c0, r1, c1;
for( r0 = 0; r0 < LEN; ++r0 ) {
for( c0 = 0; c0 < LEN; ++c0 ) {
for( r1 = r0; r1 < LEN; ++r1 ) {
for( c1 = ( r1 == r0 ? c0 + 1 : 0 ); c1 < LEN; ++c1 ) {
CHECK( r0, c0, r1, c1 );
}
}
}
}
}
voidcircle( int pos ) {
if( pos > 6 ) return; // 剪枝了，计算量太大。
inti, j, k, step;
bool ok;
intn = graph;
for( step = 1; step < LEN; ++step ) {
for( i = 0, k = 1; i < neib; ++i, k += step ) {
ok = true;
for( j = 0; j < step - 1; ++j )
if( mask[ neib ] == 0 ) { ok = false; break; }
if( ok && mask[ neib ] == 0 ) {
mask[ neib ] = 1;
{
graph = neib;
counter++;
circle( pos + 1 );
}
mask[ neib ] = 0;
}
}
}
}
voidfirst() {
inti;
for( i = 0; i < PTS; ++i ) {
mask = 1;
{
graph = i;
counter++;
circle( graphPostion + 1 );
}
mask = 0;
}
}
voidprint_vec( vector< int > & x ) {
for( int i = 0; i < x.size(); ++i ) {
printf( "%d ", x );
}
puts( "" );
}
int main ( void )
{
init_neib();
//for( int i = 1; i < LEN; ++i ) {
// for( int j = 0; j < PTS; ++j ) print_vec( neib );
// puts( "" );
//}
first();
for( int i = 0; i <= PTS; ++i ) {
printf( "%d : %d\n", i, counter );
}
return 0;
}
补充内容 (2013-7-2 09:31):
12 : 77129797424
补充内容 (2013-7-2 17:10):
代码里的counter数组用了int，会溢出，后来改成int64了。
补充内容 (2013-7-3 09:57):
如果考虑对称关系，可以提速。只需要计算1/8个象限内的起始点就可以了，当然因为对角线上的点必需计算，所以计算量略多于1/8。
补充内容 (2013-7-3 13:09):
13 : 285415667080 // 用了对称关系，所以这个结果也在几个小时内计算出来了。
gogdizzy 发表于 2013-7-1 15:15
哎，刚才试了一下，根本就算不过来，因为即使不考虑跳跃，每个数周围平均大概有10个可以连的。否则可能 ...
看到程序里的CHECK宏函数了，看来跟我的思路是一样的。:)
在我的代码里，不存在7-3的链接，
因为，7-3必定过5，是不存在的
不过我刚验证了你说的情况
可能是我还是没理解这个图案的禁断的判定吧