罗马尼亚度假问题MFC实现

罗马尼亚度假问题MFC实现

#include “stdafx.h“
#include “Manage.h“


Manage::Manage（）
{
}


Manage::~Manage（）
{
}

int * Manage::Recall（int n int &row int *Result_vec）{
	row++;
	for （int i = 0; i		if （Is_Allowed_place（row i Result_vec））{    //如果在row行i列放置不产生冲突
			Result_vec[row] = i;                      //记录下列值
			Recall（n row Result_vec）;              //到下一行放置下一个皇后
		}
	}
	if （row == 0）                                   //没找到解
		return NULL;
	else if （row >= n）                             //一种解法回溯结束
		return Result_vec;
	else                                         //回溯
		row--;
}
bool Manage::Is_Allowed_place（int row int col int *Result_vec）{
	for （int i = 0; i		if （（col == Result_vec[i]） || （abs（row - i） == abs（col - Result_vec[i]）））   //如果同列或者对角线
			return false;
	}
	return true;
}

void Manage::Recall（int n int row vector &Result_vec）{
	row++;  //row表示当前递归的行
	for （int i = 0; Result_vec.size（） != n&&i		if （Is_Allowed_place（row i Result_vec））{
			Result_vec.push_back（i）;    //找到当前行合适位置，放入结果数组
			Recall（n row Result_vec）;   //递归
		}
	}
	if （Result_vec.size（） == 0 || Result_vec.size（） == n）  //判断结束标志没 
		return;
	Result_vec.pop_back（）;  //死路，删除当前行退回上一行
}
bool Manage::Is_Allowed_place（int row int col vectorResult_vec）{
	for （int i = 0; i		if （（col == Result_vec[i]） || （abs（row - i） == abs（col - Result_vec[i]）））
			return false;
	}
	return true;
}


void Manage::CSP_alg（int n int  **&chessboard_vec int *queen）{

	int *sign = new int[n];
	for （int i = 0; i		sign[i] = 0;
	}
	int num = 0;
	while （!CSP_is_end（n chessboard_vec queen））{   //当CSP算法还未结束即总冲突值不为0
		num++;
		if （num >= n）{
			for （int i = 0; i				sign[i] = 0;
			}
			num = 0;
		}
		int min_crash = n;  //记录最小冲突
		int min_row old_row old_col;
		int random = rand（） % n;
		for （int k = 0 i = random; k			if （i == n）
				i = 0;
			for （int j = 0; j				if （chessboard_vec[i][j]					min_row = i;
					old_col = j;
					min_crash = chessboard_vec[i][j];
					if （min_crash == 0）
						break;
				}
			}
			if （min_crash == 0）
				break;
		}
		sign[old_col] = 1;
		old_row = queen[old_col];
		queen[old_col] = min_row;
		CSP_change_crash（n old_row old_col min_row chessboard_vec queen）;   //修改同行同列同斜线上格子的冲突值
	}
	delete sign;


}
void Manage::CSP_Init_place（int n int **&chessboard_vec int *queen）{
	chessboard_vec = new int *[n];
	for （int i = 0; i		chessboard_vec[i] = new int[n];
	}

	for （int i = 0; i		queen[i] = rand（） % n;   //第i列的皇后随机放置在一个位置
		for （int j = 0; j			chessboard_vec[j][i] = 0;
	}

	int row_temp1 col_temp1 row_temp2 col_temp2
		row_temp3 col_temp3 row_temp4 col_temp4;
	for （int i = 0; i		row_temp1 =

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件      10137  2016-11-30 01:25  N皇后问题\QueenTest\Manage.cpp

     文件       1929  2016-11-29 16:06  N皇后问题\QueenTest\Manage.h

     文件     109652  2016-11-29 10:15  N皇后问题\QueenTest\QueenTest.aps

     文件       2413  2016-11-28 16:17  N皇后问题\QueenTest\QueenTest.cpp

     文件        461  2016-11-28 16:17  N皇后问题\QueenTest\QueenTest.h

     文件      12746  2016-11-29 10:15  N皇后问题\QueenTest\QueenTest.rc

     文件       6317  2016-11-28 19:06  N皇后问题\QueenTest\QueenTest.vcxproj

     文件       2427  2016-11-28 19:06  N皇后问题\QueenTest\QueenTest.vcxproj.filters

     文件      10801  2016-11-29 10:21  N皇后问题\QueenTest\QueenTestDlg.cpp

     文件       1128  2016-11-29 09:21  N皇后问题\QueenTest\QueenTestDlg.h

     文件       4074  2016-11-28 16:17  N皇后问题\QueenTest\ReadMe.txt

    .......     67777  2013-07-22 01:18  N皇后问题\QueenTest\res\QueenTest.ico

     文件        674  2016-11-28 16:17  N皇后问题\QueenTest\res\QueenTest.rc2

     文件       2154  2016-11-28 19:21  N皇后问题\QueenTest\resource.h

     文件       1133  2016-11-28 22:18  N皇后问题\QueenTest\ShowDlg.cpp

     文件        505  2016-11-28 22:18  N皇后问题\QueenTest\ShowDlg.h

     文件        142  2016-11-28 16:17  N皇后问题\QueenTest\stdafx.cpp

     文件       1578  2016-11-28 16:17  N皇后问题\QueenTest\stdafx.h

     文件        234  2016-11-28 16:17  N皇后问题\QueenTest\targetver.h

     文件        973  2016-11-28 16:17  N皇后问题\QueenTest.sln

    ..A..H.     29184  2016-11-30 22:42  N皇后问题\QueenTest.v12.suo

     目录          0  2016-11-28 16:17  N皇后问题\QueenTest\res

     目录          0  2016-11-30 23:55  N皇后问题\QueenTest

     目录          0  2016-11-30 23:55  N皇后问题

----------- ---------  ---------- -----  ----

               266439                    24