#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