能力值：
( LV4，RANK：50 )
|
-
-
2 楼
注册机代码
作为习题，请修改打印出所有注册码
#include <iostream>
#include <iomanip>
#include <iterator>
using namespace std;
int table[8*9]={ //表格，根据调试时内存中数据所得
0,0,0,0,0,0,0,0,0, //no use
0,0,0,1,1,1,0,0,0,
0,0,0,1,1,1,0,0,0,
0,1,1,1,1,1,1,1,0,
0,1,1,1,3,1,1,1,0,
0,1,1,1,1,1,1,1,0,
0,0,0,1,1,1,0,0,0,
0,0,0,1,1,1,0,0,0
};
const int MAX=32;
int tablePath[MAX][8*9];
int serial[MAX];
bool searchLevel(int level);
//复制当前表格状态，以便修改后不影响回溯
void copyTableTo(int level)
{
if(level>=MAX) return; //最后一个禁止拷贝，不然就溢出了，当然，也可以给tablePath加一维
memcpy(tablePath[level], tablePath[level-1], 8*9*sizeof(int));
}
//用x匹配注册码中第level个数值（level从0开始）
//核心算法
bool doSearch(int level, int x)
{
int ecx=(x/4)%7+1;
int edx=((x/4)/7)%7+1;
int edi=x&3;
int offset=ecx+9*edx;
bool ok=false;
switch(edi) {
case 0:
if(tablePath[level][offset-9]==1
&& tablePath[level][offset-0x12]==3) {
serial[level]=x;
copyTableTo(level+1);
tablePath[level+1][offset]=3;
tablePath[level+1][offset-9]=3;
tablePath[level+1][offset-0x12]=1;
ok=true;
}
break;
case 1:
if(tablePath[level][offset+1]==1
&& tablePath[level][offset+2]==3) {
serial[level]=x;
copyTableTo(level+1);
tablePath[level+1][offset]=3;
tablePath[level+1][offset+1]=3;
tablePath[level+1][offset+2]=1;
ok=true;
}
break;
case 2:
if(tablePath[level][offset+9]==1
&& tablePath[level][offset+0x12]==3) {
serial[level]=x;
copyTableTo(level+1);
tablePath[level+1][offset]=3;
tablePath[level+1][offset+9]=3;
tablePath[level+1][offset+0x12]=1;
ok=true;
}
break;
case 3:
if(tablePath[level][offset-1]==1
&& tablePath[level][offset-2]==3) {
serial[level]=x;
copyTableTo(level+1);
tablePath[level+1][offset]=3;
tablePath[level+1][offset-1]=3;
tablePath[level+1][offset-2]=1;
ok=true;
}
break;
}
if(ok)
return searchLevel(level+1);
else
return false;
}
//搜索序列号第level个数值（level从0开始）
bool searchLevel(int level)
{
if(level>=MAX) return true;
cout<<"Searching on level: "<<level<<endl;
for(int x=0;x<=0xff;x++) {
if(doSearch(level, x))
return true;
}
cout<<"Failed on level:"<<level<<endl;
return false;
}
int main()
{
/* 我是据此发现x/7跟代码中HIGHDWORD的等价性的
unsigned long long m=0x92492493;
for(unsigned long long i=0;i<=0x3f;i++) {
unsigned long long r = m*i;
cout << i << ":" << (r>>32)/4 << ":" << i/28<< endl;
}
*/
memcpy(tablePath[0], table, 8*9*sizeof(int));
if(searchLevel(0)) {
cout<<"Serial found!\n";
//copy(serial, serial+32, ostream_iterator<int>((cout<<setw(2)<<setfill('0')<<setiosflags(ios::hex)), ""));
for(int i=0;i<MAX;i++) {
cout<<hex<<setw(2)<<setfill('0')<<serial[i];
}
}
return 0;
}
|
能力值：
( LV2，RANK：10 )
|
-
-
3 楼
厉害
!!!是很晚了,应该休息了
|
能力值：
( LV15，RANK：2473 )
|
-
-
4 楼
如果楼主用ida辅助分析的话就会少走一些弯路了，有些其实是vc提供的库函数
.text:00401171 call _isxdigit
...
.text:0040128A call _sscanf
...
还有这个游戏的名字叫“独立钻石”，网上可以搜一下
|
能力值：
( LV4，RANK：50 )
|
-
-
5 楼
哦，原来是这样，我还以为你故意的，呵呵
机器上没装IDA，这个东西od没有办法搞定么？
是VC以源代码方式提供的？exe里似乎没有看到VC相关的dll
|
能力值：
( LV15，RANK：2473 )
|
-
-
6 楼
如果od能解决所有问题，ida还能卖的出去吗
|
能力值：
![]()
(RANK：410 )
|
-
-
7 楼
是递归搜索吗？
|
能力值：
( LV4，RANK：50 )
|
-
-
8 楼
恩，是递归，也是回溯，同时也是DFS
|
能力值：
![]()
(RANK：410 )
|
-
-
9 楼
oh.这就是传说的DFS。学习了。是个好方法。
不过得不到最优解吧。
|
能力值：
( LV4，RANK：50 )
|
-
-
10 楼
恩……不知道你说的最优解是指什么？因为这里所有的解都是得到1000分，无所谓最优吧？
是指搜索速度么？
|
能力值：
![]()
(RANK：410 )
|
-
-
11 楼
恩，最少步数。你的算法已经简介高效的完成了任务。
我只是想了解有没有最优解的算法。
|
能力值：
( LV4，RANK：50 )
|
-
-
12 楼
其实这个独立钻石游戏的步数显然是固定的，游戏每步移掉一个棋子，一共32个棋子，因此步数肯定是31步
他的算法还根据x&3限定了跳的方向，我不知道为什么
而且我怀疑他是否漏了一个检查，即检查原处是否有棋子，看这个if判断：
if(tablePath[level][offset-9]==1 //被跳处是否有棋
&& tablePath[level][offset-0x12]==3) { //对面是否是空位
似乎还应该加上tablePath[level][offset]的判断
造成的影响就是有时候棋子会增加……-_-
对于真正的独立钻石游戏的搜索，我想可以通过下面两条来加快搜索速度：
1. 只搜索空位附近的棋子（前期应该可以剪掉很多搜索分支）
2. 用hash保存棋盘状态，防止重复搜索（类似DP，即动态规划）
你有兴趣的话可以做做：）
|
能力值：
![]()
(RANK：410 )
|
-
-
13 楼
根据网上查的关于“独钻”的资料，只剩一字的为大师，只剩一子且该子居中，则为天才。天才又根据步数分等。最早有人发现19步解法。后又发现18步的2种解法。
所以我猜想该crack应该是有很多种解法的，但最优解只有两种。这个crack没有仔细跟（我看的太慢，所以没跟），不知他做了什么限定没有。有空去研究下。
|
能力值：
( LV4，RANK：50 )
|
-
-
14 楼
哦，原来真正的独钻是可以跳过多个棋子的……怪不得步数会不一样
|
能力值：
( LV15，RANK：2473 )
|
-
-
15 楼
只有上下左右4个方向啊,为什么不可以限制方向？
应该是漏掉了这个检查
|
能力值：
( LV4，RANK：50 )
|
-
-
16 楼
但是你的坐标是根据x得出来的阿
而任何一个坐标处的棋子应该可以有四个自由度把，你这样的话一个坐标上的棋子只能往一个方向跳了
|
能力值：
( LV15，RANK：2473 )
|
-
-
17 楼
难道 &3不是表示4个自由度吗？
|
能力值：
( LV2，RANK：10 )
|
-
-
18 楼
算法啊，头疼，头疼，我还是走爆爆的路吧，学不会啊
|
能力值：
( LV4，RANK：50 )
|
-
-
19 楼
但是对于某个特定坐标上的棋子不是阿，始终是往x&3那个方向跳的，对么？
当然，也可以认为是特殊的限制条件，但是如果加上上面那个检查，很可能是无解的……
btw: 加上那个检查可以增加很多计算量，搜索算法需要做优化，我搜了很久都没搜完……
|
能力值：
![]()
(RANK：1060 )
|
-
-
20 楼
and 3d = and 11b 保留2bit，表示范围0~2^2-1=0-3=0 1 2 3，相当于mod 4, 四个方向
|
能力值：
( LV12，RANK：570 )
|
-
-
21 楼
顶，我也下去破了一下。蛮有趣的，绕一个大弯子然后再……其乐无穷。作者写的真的很好，我顶。
|
能力值：
( LV4，RANK：50 )
|
-
-
22 楼
哦，你说得对，是我搞错了，可以是从0-0xff的，方向信息已经包含在其中了。
另外给出针对ccfer本意的注册机（即加上棋子检查后）：
#include <iostream>
#include <iomanip>
#include <iterator>
#include <map>
#include <vector>
using namespace std;
const int STEP=31;
const int SIZE=7;
int _table[SIZE*SIZE]={ //表格，根据调试时内存中数据所得
0,0,1,1,1,0,0,
0,0,1,1,1,0,0,
1,1,1,1,1,1,1,
1,1,1,3,1,1,1,
1,1,1,1,1,1,1,
0,0,1,1,1,0,0,
0,0,1,1,1,0,0
};
vector<int> table(_table, _table+SIZE*SIZE);
vector<int> tablePath[STEP+1];
map<vector<int>, bool> failedTables[STEP];
int serial[STEP];
bool searchLevel(int level);
//复制当前表格状态，以便修改后不影响回溯
void copyTableTo(int level)
{
tablePath[level]=tablePath[level-1];
}
//用x匹配注册码中第level个数值（level从0开始）
//核心算法
bool doSearch(int level, int pos)
{
int row=((pos/4)/SIZE)%SIZE;
int col=(pos/4)%SIZE;
int d=pos&3;
int offset=SIZE*row+col;
bool ok=false;
if(tablePath[level][offset]!=1) return false;
switch(d) {
case 0:
//jump up
if(row>2 && tablePath[level][offset-7]==1 && tablePath[level][offset-14]==3) {
copyTableTo(level+1);
tablePath[level+1][offset]=3;
tablePath[level+1][offset-7]=3;
tablePath[level+1][offset-14]=1;
ok=true;
}
break;
//jump right
case 1:
if(col<5 && tablePath[level][offset+1]==1 && tablePath[level][offset+2]==3) {
copyTableTo(level+1);
tablePath[level+1][offset]=3;
tablePath[level+1][offset+1]=3;
tablePath[level+1][offset+2]=1;
ok=true;
}
break;
case 2:
//jump down
if(row<5 &&tablePath[level][offset+7]==1 && tablePath[level][offset+14]==3) {
copyTableTo(level+1);
tablePath[level+1][offset]=3;
tablePath[level+1][offset+7]=3;
tablePath[level+1][offset+14]=1;
ok=true;
}
break;
case 3:
//jump left
if(col>2 && tablePath[level][offset-1]==1 && tablePath[level][offset-2]==3) {
copyTableTo(level+1);
tablePath[level+1][offset]=3;
tablePath[level+1][offset-1]=3;
tablePath[level+1][offset-2]=1;
ok=true;
}
break;
}
if(ok) {
serial[level]=pos;
return searchLevel(level+1);
}
return false;
}
//搜索序列号第level个数值（level从0开始）
bool searchLevel(int level)
{
if(level>=STEP) return (tablePath[level][3*7+3]==1);
if(failedTables[level].find(tablePath[level])!=failedTables[level].end()) return false;
for(int pos=0;pos<0xff;pos++) {
if(doSearch(level, pos)) {
return true;
}
}
//纪录失败状态（包括因对称性而存在的等价状态），防止重复搜索
vector<int> tempTable(tablePath[level]);
failedTables[level][tempTable] = false;
for(int x=0;x<SIZE;x++)
for(int y=0;y<SIZE;y++)
tempTable[SIZE*x+y]=tablePath[level][SIZE*y+x];
failedTables[level][tempTable] = false;
for(int x=0;x<SIZE;x++)
for(int y=0;y<SIZE;y++)
tempTable[SIZE*x+y]=tablePath[level][SIZE*x+(6-y)];
failedTables[level][tempTable] = false;
for(int x=0;x<SIZE;x++)
for(int y=0;y<SIZE;y++)
tempTable[SIZE*x+y]=tablePath[level][SIZE*(6-x)+y];
failedTables[level][tempTable] = false;
for(int x=0;x<SIZE;x++)
for(int y=0;y<SIZE;y++)
tempTable[SIZE*x+y]=tablePath[level][SIZE*(6-y)+6-x];
failedTables[level][tempTable] = false;
return false;
}
int main()
{
tablePath[0]=table;
if(searchLevel(0)) {
cout<<"Serial found!\n";
for(int i=0;i<STEP;i++) {
cout<<hex<<setw(2)<<setfill('0')<<serial[i];
}
cout<<endl;
} else {
cout<<"No serial found...\n";
}
return 0;
}
|
能力值：
( LV2，RANK：10 )
|
-
-
23 楼
OD 里面菜单 调试 - 加入库文件，把MFC或用到的DLL的 lib文件加进去就可以识别调用的函数名了
|
|
|
|
