求九宫问题程序（C语言实现）

来源：百度知道 编辑：UC知道 时间：2024/05/27 17:59:32
题目要求：在一个3*3正方形盘中，放入8个大小相等的方块，每个方块上分别标有数字1－8。游戏的要求为从任意一个方块的初始布置出发，每次平移一个方块，怎样用最少步数，达到最终状态。当然，并不是所有初始状态都能平移到目标状态。你的程序对任意给定的一个初始状态，能够判断出是否能够移动到目标状态，如果能，给出最少的移动方案。
如：开始状态：
3 8
2 5 7
6 1 4
结束状态：
1 2 3
8 4
7 6 5

【转】
/*九宫图算法说明：根据分析，九宫图中间一位一定是5，另外关于中间位置
对称的每两个数字相加等于10，所以对于一个九宫图只通过其相邻位置的数
字就能计算出其他所有位置的数字，而且相邻位置的数字必然一个比5大，一
个比5小
算法设计思想：先根据选取规则，从剩下八个数里面选一大一小，再使用目
标函数检测选取是否正确，如果正确则打印出，否则重新选取，选数的过程
使用回溯法*/

#include<stdio.h>

int place(int*);

void main(void){/*九宫图算法*/

int a[9]={1,2,3,4,5,6,7,8,9};

int b[9]={0};/*表示数字的位置状态*/

int j,k,i;

for(k=0;k<=3;k++){/*对于所有比5小的数*/

b[1]=a[k];/*选一比5小的数放到第一行第二列*/

for(j=8;j>=5;j--){/*对于所有比5大的数*/

if(k!=(8-j)){/*不选择前面已选小数所对应的大数*/

b[0]=a[j];/*选一比5大的数放到第一行第一列*/

if(place(b)){/*若得到一解，则打印出*/

printf("\n 九宫图\n\n");

for(i=0;i<=8;i++){