/*
回溯法解電路板問題
設x表示n塊電路板的一個排列，即在機箱的第i個插槽中插入電路板x[i]
x所確定的電路板排列密度density(x)定義為跨越相鄰電路板插槽的最大連接數
在設計機箱，插槽一側的布線間隙由電路板排列的密度所確定
因此電路板排列問題要求對于給定電路板連接條件（連接塊），確定電路板的最佳排列，使
其具有最小的密度
    算法中用整型數組B表示輸入。B[i][j]的值為1當且僅當電路板i在連接塊Nj中。設
total[j]是連接塊Nj中的電路板數。對于電路板的部分排列x[1:i]，設now[j]是x[1:i]中所
包含的Nj中的電路板數。由此可知，連接塊Nj的連線跨越插槽i和i+1當且僅當now[j]》0
且now[j]!=total[j]。我們可以利用這個條件來計算插槽i和插槽i+1之間的連線密度。
*/
#include<iostream>
using namespace std;

class Board
{
	friend Arrangement(int **,int,int,int[]);
private:
	void Backtrack(int i,int cd);
	//第一個參數搜索第i層，此時密度為cd
	int n;
	//電路板數，決定要搜索的排列樹層數
	int m;
	//連接塊數
	int *x;
	//當前解
	int *bestx;
	//當前最優解
	int bestd;
	//當前最優密度
	int *total;
	//total[j]=連接塊j的電路板數
	int *now;
	//now[j]當前解中所含連接塊j的電路板數
	int **B;
	//連接塊數組
};

void Board::Backtrack(int i,int cd)
//回溯搜索排列樹
{
	if ( i == n )
	{
		cout<<"處理最后部分"<<endl;
		for( int j = 1; j <= n; ++j )
		{
			bestx[j] = x[j];
		}
		bestd = cd;
		//得到所有的序列，并更新表示最小密度的變量
		cout<<"結束處理最后部分"<<endl;
	}
	else
	{
		for( int j = i; j <= n; ++j )
		//選擇x[j]為下一塊電路板
		{
			cout<<"開始"<<endl;
			int ld = 0;
			//臨時變量，記錄增加一筆記錄后密度是多少
			//密度最大就是塊數
			for( int k = 1; k <= m; ++k )
			{
				now[k] += B[x[j]][k];
				if ( now[k] >0 && total[k]!= now[k] )
				{
					++ld;
				}
			}
			//更新ld
			if ( cd > ld )
			{
				ld = cd;
			}
			cout<<"結束"<<endl;
			
			cout<<"before"<<endl;
			if ( ld < bestd )
			//搜索子數，搜索前先交換被選中的到當前位置i處
			{
				int temp;
				temp = x[i];
				x[i] = x[j];
				x[j] = temp;
				Backtrack(i+1,ld);
				//返回上層要更新信息
				temp = x[i];
				x[i] = x[j];
				x[j] = temp;
				for( int k = 1; k <= m; ++k )
				{
					now[k] -= B[x[j]][k];
				}

			}
			cout<<"after"<<endl;
			
		}
	}

}

int Arrangement( int **B, int n, int m, int *bestx )
{
	Board X;
	X.x = 0;
	X.x = new int[n+1];
	if ( 0 == X.x )
	{
		return -1;
	}
	X.total = 0;
	X.total = new int[m+1];
	if ( 0 == X.total )
	{
		return -1;
	}
	X.now = 0;
	X.now = new int[m+1];
	if ( 0 == X.now )
	{
		return -1;
	}
	X.B = B;
	X.n = n;
	X.m = m;
	X.bestx = bestx;
	X.bestd = m + 1;
	//初始化total和now
	for( int i = 1; i <= m; ++i )
	{
		X.total[i] = 0;
		X.now[i] = 0;
	}
	//初始化x為單位排列計算total
	for( i = 1; i <= n; ++i )
	{
		X.x[i] = i;
		for( int j = 1; j <= m; ++j )
		{
			X.total[j] += B[i][j];
		}
	}
	//回溯搜索
	X.Backtrack( 1, 0 );
	for( i = 1; i <= n; ++i )
	{
		cout<<bestx[i]<<" ";
	}
	
	if ( 0 != X.x )
	{
		delete []X.x;
	}
	if ( 0 != X.total )
	{
		delete []X.total;
	}
	if ( 0 != X.now )
	{
		delete []X.now;
	}
	cout<<endl;
	cout<<X.bestd<<endl;
	return X.bestd;
}

/*
在電路板排列問題解空間的排列樹的每個結點處，函數Backtrack花費O(m)計算時間
為每個兒子結點計算密度。因此，計算密度所耗費的總計算時間為O(mn!)。另外，生成排列樹
需要O(n!)時間。更新當前最優解需要O(mn)時間。這是每次更新當前最優解至少使bestd減少1，
而算法運行結束時候bestd>=0。因此最優解被更新的次數為O(m)。
綜上可知，解電路板排列問題的回溯算法Backtrack所需要的計算時間為O(mn!)
*/
int main()
{
	int **B = 0;
	B = new int*[9];
	if ( 0 == B )
	{
		return -1;
	}
	for( int i = 0; i < 9; ++ i )
	{
		B[i] = 0;
		B[i] = new int[6];
		if ( 0 == B[i] )
		{
			return -1;
		}
		for( int j = 0; j < 6; ++j )
		{
			B[i][j] = 0;
		}
	}

	B[4][1] = 1;
	B[5][1] = 1;
	B[6][1] = 1;

	B[2][2] = 1;
	B[3][2] = 1;

	B[1][3] = 1;
	B[3][3] = 1;

	B[3][4] = 1;
	B[6][4] = 1;

	B[7][5] = 1;
	B[8][5] = 1;

	int n = 8;
	int m = 5;

	int *bestx = new int[9];
	for( int s = 0; s < 9; ++s )
	{
		for( int s1 = 0; s1 < 6; ++s1 )
		{
			cout<<B[s][s1]<<" ";
		}
		cout<<endl;
	}
	Arrangement( B, n, m, bestx );
	
	return 0;
}