用C++解跳棋问题的代码

可以采用广度优先搜索，程序如下：

#include <iostream>

#include <string>

#include <algorithm>

#include <set>

#include <queue>

using namespace std

struct node{

string str, step

node(){}

node(string str, string step = ""): str(str), step(step){}

}

int main(){

string start = "0111222", dest = "2221110"

node n

queue<node> Open

set<string> Close

Open.push(node(start))

while(1){

n = Open.front()

Open.pop()

Close.insert(n.str)

if(n.str == dest)break

int l = n.str.find("0"做搭)

for(int i=-3 i<=3 i++){

if(!i || l+i<0 || l+i>=dest.size())

continue

string 纯迟拿s(n.str)

s[l] = s[l+i]

s[l+i] = '0'

if(Close.find(s) == Close.end())

Open.push(node(s, n.step + char('0'+l+i) + " "))

}

}

cout << n.step

}

程序输出：

1 旦没4 2 5 6 3 0 2 5 6

// 表示每一步移动哪个棋子，最开始棋子编号0

算法优化：可考虑使用A*算法进行启发式搜索

不知道你是想要什么类型的，是人与人对弈，还是人与机对弈

人与人的比较好办，把棋盘分为20*20的点（比如的，我不知道跳棋棋盘准确棋点）

你用一个string[20][20]表示这个棋盘上所有的点，

string[20][20]=1表示红方有子在这个点上

=2表示另一方的子在这上，这样棋盘就有了

再写个算法确定一下跳棋哪大的走法兆配

这样人与人对弈的程序李猜竖就差不多了，人与机对弈难度太大，不建议你写

回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。用回溯算法解决问题的一般步骤为： 1、定义一个解空间，它包含问题的解。 2、利用适于搜索的方法组织解空间。 3、利用深度优先法搜索解空间。 4、利用限界函数避免移动到不可能产生解的子空间。 问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。1.跳棋问题：33个方格顶点摆放着32枚棋子，仅中央的顶点空着未摆放棋子。下棋的规则是任一棋子可以沿水平或成垂直方向跳过与其相邻的棋子，进入空着的顶点并吃掉被跳过的棋子。试设计一个算法找出一种下棋方法，使得最终棋盘上只剩下一个棋子在棋盘中央。算法实现提示利用回溯算法，每次找到一个可橘判以走的棋子走动，并吃掉。若走到无子可走还是剩余多颗，则回溯，走下一颗可以走动的棋子。当吃掉31颗时说明只剩一颗，程序结束。2.中国象棋马行线问题：中国象棋半圆枝改张棋盘如图1(a)所示。马自左下角往右上角跳。今规定只许往右跳，不许往左跳。比如图4（a）中所示为一种跳行路线，并将所经路线打印出来。打印格式为：0，0->2,1->3,3->1,4->3,5->2,7->4,8…算法分析：如图1(b),马最多有四个方向，若原来的横坐标为j、纵坐标为i,则四个方向的移动可表示为：1: （i,j）→（i+2,j+1）； (i<3,j<8)2: （i,j）→（i+1,j+2）； (i<4,j<7)3: （i,j）→（i-1,j+2）； (i>0,j<7) 4: （i,j）→（i-2,j+1）； (i>1,j<8)搜索策略：S1:Ａ[１]:=(0,0)S2:从Ａ[1]出发，按移动规则依次选定某个方向，如果达到的是（4,8）则转向S3,否则继续搜索下一个到达的顶点；S3:打印路径。算法设计：procedure try(i:integer)var j:integerbeginfor j:=1 to 4 do if 新坐标满足条件 thenbegin记录新坐标if 到达目的地 then print else try(i+1)退回到上一个搭镇坐标，即回溯endend

---