【原创】关于 "马踏棋盘" 的回溯算法问题
问题背景:
国际象棋的棋盘为 8 * 8 的方格棋盘,现将 "马" 放在任意指定的方格中, 按照 "马走日" 的规则将 "马" 进行移动,要求每个方格只能进入一次,最终使得 "马" 走遍棋盘64个方格。
问题说明:
作者自行实现的代码好像有BUG,分享出来,望不吝赐教。
实现源码:
#include <stdio.h> #include <stdlib.h> #define ROW 8 #define COL 8 #define TOTAL ROW * COL #define TOTAL_NUMBER_WITH_FOOT_POSITION 8 typedef struct cache { int (*pline)[COL]; int col; int val; }Cache; void initChess(int (*p)[COL]); void showChess(int (*p)[COL]); void showAddress(); void showFoot(); void findNextPosition(Cache *pcache); int isPositionUsed(int n); int isAddressValid(int *p); Cache *getOnePossiblePositon(int index, Cache *pcache); int global_foot[TOTAL]; int *global_address[TOTAL]; int main() { int data[ROW][COL] = {0}; Cache cache, *pc; pc = &cache; pc->col = 4; pc->pline = data; initChess(data); showChess(data); /*showAddress();*/ //设定一初始位置 global_foot[0] = *(*pc->pline + pc->col); findNextPosition(pc); showFoot(); return 0; } void findNextPosition(Cache *pcache) { int i = 0; static int counter = 0; Cache *pcache2; if(counter > TOTAL) return; for(i = 1; i <= TOTAL_NUMBER_WITH_FOOT_POSITION; i++) { pcache2 = getOnePossiblePositon(i, pcache); if(pcache2 == NULL) continue; int ok = 1; if(isPositionUsed(pcache2->val)) ok = 0; //找到了一个可用位置 if(ok == 1) { global_foot[++counter] = pcache2->val; /*printf("%02d-%d\n", counter, pcache2->val);*/ findNextPosition(pcache2); } } } void initChess(int (*p)[COL]) { int i, k = 0; for(i = 0; i < TOTAL; i++) { *(*p + i) = ++k; } } Cache *getOnePossiblePositon(int index, Cache *pcache) { Cache cache2, *pcache2; int t1, t2; pcache2 = &cache2; if(index == 1) { pcache2->pline = pcache->pline - 2; pcache2->col = pcache->col - 1; } else if(index == 2) { pcache2->pline = pcache->pline - 2; pcache2->col = pcache->col + 1; } else if(index == 3) { pcache2->pline = pcache->pline - 1; pcache2->col = pcache->col + 2; } else if(index == 4) { pcache2->pline = pcache->pline + 1; pcache2->col = pcache->col + 2; } else if(index == 5) { pcache2->pline = pcache->pline + 2; pcache2->col = pcache->col + 1; } else if(index == 6) { pcache2->pline = pcache->pline + 2; pcache2->col = pcache->col - 1; } else if(index == 7) { pcache2->pline = pcache->pline + 1; pcache2->col = pcache->col - 2; } else if(index == 8) { pcache2->pline = pcache->pline - 1; pcache2->col = pcache->col - 2; } if(pcache2->col < 0 || pcache2->col > COL - 1) return NULL; t1 = isAddressValid(*pcache2->pline); if(0 == t1) return NULL; t2 = isAddressValid(*pcache2->pline + pcache2->col); if(0 == t2) return NULL; pcache2->val = *(*pcache2->pline + pcache2->col); return pcache2; } void showChess(int (*p)[COL]) { int i; putchar('\n'); for(i = 0; i < TOTAL; i++) { printf("%3d ", *(*p + i), *p + i); if((i + 1) % COL == 0) putchar('\n'); global_address[i] = *p + i; } putchar('\n'); } void showAddress() { int i; for(i = 0; i < TOTAL; i++) { printf("%p ", global_address[i]); if((i + 1) % COL == 0) putchar('\n'); } putchar('\n'); } int isPositionUsed(int n) { int i; for(i = 0; i < TOTAL; i++) { if(n == global_foot[i]) { return 1; } } return 0; } int isAddressValid(int *p) { int i; for(i = 0; i < TOTAL; i++) { if(p == global_address[i]) { return 1; } } return 0; } void showFoot() { int i = 0; printf("宝马依次走过的足迹为:\n\n"); for(i = 0; i < TOTAL; i++) { printf("%d ", global_foot[i]); } putchar('\n'); putchar('\n'); }
版权声明:除非注明,本文由( blogdaren )原创,转载请保留文章出处。
用户评论:
2020-12-28 21:18
发表评论: