matrix.cpp

8_puzzle问题

/* just for 分支界限法
* 9 格方块的摆放
*/
#define DEBUG
#pragma warning(disable:4786)
#include <string>
#include <vector>
#include <stack>
#include <assert.h>
#include <algorithm>
#include <iostream>
using namespace std;

int target[9] = {1,2,3,8,0,4,7,6,5};
int state[9] = {2,3,0,5,1,4,6,8,7};
struct chart
{
	int matrix[9];
	int steps;
	int trace;
	int distance;
};
typedef struct chart chart_t;

int distance (chart_t *a)
{
	int i;
	int space = 0;
	for (i = 0; i < 9; i++)
	{
		if (a->matrix[i] != target[i])
			space++;
	}
	
	return space;
}
int init (chart_t *a)
{
	int i;
	for (i = 0; i < 9; i++)
	{
		a->matrix[i] = state[i];
	}
	a->steps = 0;
	a->trace = 0;
	a->distance = distance (a);
	
	return 0;
}
int show_chart (chart_t *a)
{
	int i;
	for (i = 0; i < 9; i++)
	{
		printf ("%d ", a->matrix[i]);
		if (i % 3 == 2)
			printf ("\n");
	}
	//printf ("\n");
	printf ("steps= %d  ", a->steps);
	printf ("trace= %d  ", a->trace);
	printf ("distance= %d\n\n", a->distance);
	
	return 0;
}
int find_pos (chart_t *a)
{
	int i;
	for (i = 0; i < 9; i++)
	{
		if (a->matrix[i] == 0)
			return i;
	}
	return -1;
}
int copy_chart (chart_t *src, chart_t *dst)
{
	int i;
	for (i = 0; i < 9; i++)
	{
		dst->matrix[i] = src->matrix[i];
		dst->steps = src->steps;
		dst->trace = src->trace;
	}
	
	return 0;
}
int run (chart_t *a, chart_t *result)
{
	stack<chart_t *> sa;
	stack<chart_t *> sb;
	
	stack<chart_t *> *src;
	stack<chart_t *> *dst;
	stack<chart_t *> *val;
	src = &sa;
	dst = &sb;
	
	src->push(a);
	int i;
	int direct[4] = {-3, 3, -1, 1};
	int pos;
	chart_t *obj;
	int bound = 9;
	int limit = bound;
	while (1)
	{
		while (! src->empty())
		{
#ifdef DEBUG
			printf ("src = %d, dst = %d\n", src->size(), dst->size());
#endif
			obj = src->top();
			src->pop();
			if (obj->distance > (bound + 2))
				continue;
			
			pos = find_pos(obj);
			for (i = 0; i < 4; i++)
			{
				if (obj->trace == direct[i])
					continue;
				if ((pos + direct[i] >= 0) && (pos + direct[i] <= 8))
				{
					if ((pos == 2) && (pos + direct[i] == 3))
						continue;
					if ((pos == 3) && (pos + direct[i] == 2))
						continue;
					if ((pos == 5) && (pos + direct[i] == 6))
						continue;
					if ((pos == 6) && (pos + direct[i] == 5))
						continue;
					
					chart_t *elem = (chart_t *)malloc (sizeof(chart_t));
					copy_chart (obj, elem);
					
					int temp;
					temp = elem->matrix[(pos + direct[i])];
					elem->matrix[(pos + direct[i])] = elem->matrix[pos];
					elem->matrix[pos] = temp;
					elem->distance = distance (elem);
					//
#ifdef DEBUG
					printf ("-------------------\n");
					//show_chart (obj);
					//show_chart (elem);
					//getchar();
#endif
					
					if (distance(elem) == 0)
					{
						copy_chart (elem, result);
						show_chart (elem);
						return 0;
					}
					elem->steps++;
					elem->trace = direct[i];
					dst->push(elem);
					//
					if (elem->distance < limit)
						limit = elem->distance;
				}
			}
			//
			bound = limit;
		}
#ifdef DEBUG
			printf ("src = %d, dst = %d\n", src->size(), dst->size());
#endif
		val = src;
		src = dst;
		dst = val;
		if ((src->size () == 0) && (dst->size () == 0))
			return 0;

	}
	
	return 0;
}
int main (void)
{
	chart_t a;
	chart_t result;
	memset (&result, 0, sizeof (chart_t));
	init (&a);
	show_chart (&a);
	run(&a, &result);
	show_chart (&result);
	return 0;
}