共有回帖数 0 个
- ◣提高级源码◥ 快速九格宫求解 - Fast 8-puzzle solver.
-
只看楼主
收藏
回复
-
发布这个贴已记念一下，作为两年前的:
http://post.baidu.com/f?kz=11162185
所发游戏的一个对应.
九格宫(8-puzzle)的最优求解确实是一个头疼的问题，大致解法为，为每一个可能移法生成一个树结点，然后对这棵树进行广度优先的搜索，然而这棵树是无限层次的，所以必需对已出现的状态进行删减。 最优解及其研究可以搜索 "8 puzzle"来获得英文的一些资料，这里不想讨论这个问题。
如果要获得简单解，那么，计算的复杂度可以减少到常量级，最重要的是找到一条通用的解法，这正是代码所展示的一切：
#include stdio.h
#include stdlib.h
#include string.h
char block[10];
void moveto(int from, int to)
{
printf("'%c' 到 %dn", block[from], to);
printf("----n%c %c %cn", block[0], block[1], block[2]);
printf("%c %c %cn", block[3], block[4], block[5]);
printf("%c %c %cn----n", block[6], block[7], block[8]);
block[to] = block[from];
block[from] = '0';
}
int clearmove(int d, char *mask)
{
if (block[d] == '0') return 1;
char nmask[10];
strcpy(nmask, mask);
nmask[d] = '1';
if (d + 3 9 && nmask[d + 3] == '0') {
if (clearmove(d + 3, nmask)) {
moveto(d, d + 3);
return 1;
}
}
if (d - 3 = 0 && nmask[d - 3] == '0') {
if (clearmove(d - 3, nmask)) {
moveto(d, d - 3);
return 1;
}
}
if (d % 3 != 0 && nmask[d - 1] == '0') {
if (clearmove(d - 1, nmask)) {
moveto(d, d - 1);
return 1;
}
}
if (d % 3 != 2 && mask[d + 1] == '0') {
if (clearmove(d + 1, nmask)) {
moveto(d, d + 1);
return 1;
}
}
return 0;
}
void movex(int from, int to, char *mask)
{
int f, t;
if (from == to) return;
if (to == from + 3 || to == from - 3 ||
(to == from + 1 && to % 3 != 0) ||
(to == from - 1 && to % 3 != 2)) {
char zmask[10];
strcpy(zmask, mask);
zmask[from] = '1';
clearmove(to, zmask);
moveto(from, to);
return;
}
f = from % 3;
t = to % 3;
if (t f) {
movex(from, from + 1, mask);
movex(from + 1, to, mask);
} else if (t f) {
movex(from, from - 1, mask);
movex(from - 1, to, mask);
} else {
f = from / 3;
t = to / 3;
if (t f) {
movex(from, from + 3, mask);
movex(from + 3, to, mask);
} else if (t f) {
movex(from, from - 3, mask);
movex(from - 3, to, mask);
}
}
}
int getpos(char x)
{
int i;
for (i = 0; i 9; ++i)
if (block == x) return i;
return -1;
}
void move678()
{
int from;
from = getpos('6');
printf("6归位:n");
movex(from, 6, "000000000");
from = getpos('7');
printf("7归位:n");
movex(from, 7, "000000100");
if (block[8] == '8') return;
if (block[8] == '0' && block[5] == '8') {
moveto(5, 8);
return;
}
printf("8移动到4(中间)n");
from = getpos('8');
movex(from, 4, "000000110");
printf("6移到3:n");
movex(6, 3, "000010010");
printf("7移到6:n");
moveto(7, 6);
printf("8移到7:n");
moveto(4, 7);
printf("678还原:n");
movex(7, 8, "000100100");
moveto(6, 7);
moveto(3, 6);
}
void moverest()
{
printf("5到2:n");
movex(getpos('5'), 2, "000000111");
if (block[5] != '4') {
if (block[4] == '4' && block[5] == '0') moveto(4, 5);
else {
printf("4移到1:n");
movex(getpos('4'), 1, "001000111");
printf("位置5移到4:n");
if (block[5] != '0') movex(5, 4, "011000111");
printf("678右移:n");
moveto(8, 5);
moveto(7, 8);
moveto(6, 7);
moveto(3, 6);
printf("4移到4:n");
movex(1, 4, "001001011");
printf("678还原:n");
movex(7, 6, "001011001");
moveto(8, 7);
moveto(5, 8);
moveto(4, 5);
}
}
printf("3复原:n");
movex(getpos('3'), 3, "001001111");
printf("4复原:n");
movex(5, 4, "001100111");
printf("5复原:n");
moveto(2, 5);
moveto(1, 2);
moveto(0, 1);
}
int main(int argc, char **argv)
{
int j;
char buf[20];
scanf("%s", buf);
for (j = 0; j 9; ++j) {
block[j] = buf[j];
}
block[9] = 0;
move678();
moverest();
if (block[1] == '2') printf("无解.n");
return 0;
}
#include stdio.h
#include stdlib.h
#include string.h
char block[10];
void moveto(int from, int to)
{
printf("'%c' 到 %dn", block[from], to);
printf("----n%c %c %cn", block[0], block[1], block[2]);
printf("%c %c %cn", block[3], block[4], block[5]);
printf("%c %c %cn----n", block[6], block[7], block[8]);
block[to] = block[from];
block[from] = '0';
}
int clearmove(int d, char *mask)
{
if (block[d] == '0') return 1;
char nmask[10];
strcpy(nmask, mask);
nmask[d] = '1';
if (d + 3 9 && nmask[d + 3] == '0') {
if (clearmove(d + 3, nmask)) {
moveto(d, d + 3);
return 1;
}
}
if (d - 3 = 0 && nmask[d - 3] == '0') {
if (clearmove(d - 3, nmask)) {
moveto(d, d - 3);
return 1;
}
}
if (d % 3 != 0 && nmask[d - 1] == '0') {
if (clearmove(d - 1, nmask)) {
moveto(d, d - 1);
return 1;
}
}
if (d % 3 != 2 && mask[d + 1] == '0') {
if (clearmove(d + 1, nmask)) {
moveto(d, d + 1);
return 1;
}
}
return 0;
}
void movex(int from, int to, char *mask)
{
int f, t;
if (from == to) return;
if (to == from + 3 || to == from - 3 ||
(to == from + 1 && to % 3 != 0) ||
(to == from - 1 && to % 3 != 2)) {
char zmask[10];
strcpy(zmask, mask);
zmask[from] = '1';
clearmove(to, zmask);
moveto(from, to);
return;
}
f = from % 3;
t = to % 3;
if (t f) {
movex(from, from + 1, mask);
movex(from + 1, to, mask);
} else if (t f) {
movex(from, from - 1, mask);
movex(from - 1, to, mask);
} else {
f = from / 3;
t = to / 3;
if (t f) {
movex(from, from + 3, mask);
movex(from + 3, to, mask);
} else if (t f) {
movex(from, from - 3, mask);
movex(from - 3, to, mask);
}
}
}
int getpos(char x)
{
int i;
for (i = 0; i 9; ++i)
if (block == x) return i;
return -1;
}
void move678()
{
int from;
from = getpos('6');
printf("6归位:n");
movex(from, 6, "000000000");
from = getpos('7');
printf("7归位:n");
movex(from, 7, "000000100");
if (block[8] == '8') return;
if (block[8] == '0' && block[5] == '8') {
moveto(5, 8);
return;
}
printf("8移动到4(中间)n");
from = getpos('8');
movex(from, 4, "000000110");
printf("6移到3:n");
movex(6, 3, "000010010");
printf("7移到6:n");
moveto(7, 6);
printf("8移到7:n");
moveto(4, 7);
printf("678还原:n");
movex(7, 8, "000100100");
moveto(6, 7);
moveto(3, 6);
}
void moverest()
{
printf("5到2:n");
movex(getpos('5'), 2, "000000111");
if (block[5] != '4') {
if (block[4] == '4' && block[5] == '0') moveto(4, 5);
else {
printf("4移到1:n");
movex(getpos('4'), 1, "001000111");
printf("位置5移到4:n");
if (block[5] != '0') movex(5, 4, "011000111");
printf("678右移:n");
moveto(8, 5);
moveto(7, 8);
moveto(6, 7);
moveto(3, 6);
printf("4移到4:n");
movex(1, 4, "001001011");
printf("678还原:n");
movex(7, 6, "001011001");
moveto(8, 7);
moveto(5, 8);
moveto(4, 5);
}
}
printf("3复原:n");
movex(getpos('3'), 3, "001001111");
printf("4复原:n");
movex(5, 4, "001100111");
printf("5复原:n");
moveto(2, 5);
moveto(1, 2);
moveto(0, 1);
}
int main(int argc, char **argv)
{
int j;
char buf[20];
scanf("%s", buf);
for (j = 0; j 9; ++j) {
block[j] = buf[j];
}
block[9] = 0;
move678();
moverest();
if (block[1] == '2') printf("无解.n");
return 0;
}
楼主 2016-01-28 14:53 回复
Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号
意见反馈 |
关于直线 |
版权声明 |
会员须知
