ブルーブリッジカップブロック数DFS検索

「数独」は今熱い知能ゲームだ.その起源は「ラテンブロック」とされ、大数学者のオラが1783年に発明した.
図[1.jpg]に示すように、6 x 6の小格子は6つの部分(図中は異なる色で区別されている)に分けられ、各部分は6つの小格子(以下、パケットとも呼ばれる)を含む.
最初は、いくつかの小格にアルファベット(ABCDEFの1つ)が記入されていました.残りのすべての小格にアルファベットを補充する必要があります.すべて記入した後、次の制約を満たさなければなりません:1.アルファベットは、A,B,C,D,E,Fのいずれかを許可します.    2. 各行の6つの小格の中で、記入したアルファベットは繰り返してはいけません.    3. 各列の6つの小格の中で、記入したアルファベットは繰り返してはいけません.    4. 各グループ(図中の異なる色の表示を参照)に含まれる6つの小格には、入力されたアルファベットは重複できません.表示上の便宜上、図[1.jpg]に対応するパケット状況(グループ番号0~5):000011 022013 221113 243324455 445555を以下の6次方程式で表す.既存のアルファベットの記入状況を以下のデータで表す.02 C 03 B 05 A 20 D 35 E 53 Fは明らかで、第1列は行番号、第2列は列番号、3列目は記入するアルファベットを表します.行番号、列番号ともに0から計算を開始します.1つの実行可能な記入案(この問題はちょうど答えが唯一です)は、E F C B D A A C E D F B D A B E C F B D C A E B D F A E C C E A A F B Dあなたの任務は、プログラムを作成し、一般的なラテンブロックの問題を解き、多くの解があれば、すべての解を見つけることです.【入力・出力フォーマット要件】ユーザはまず6行のデータを入力し、ラテンブロックのパケット状況を表す.次にユーザは整数n(n<36)を入力し、次のデータ行数を表し、次にn行データを入力し、各行は予め記入されたアルファベットを表す.プログラムは可能なすべての解を出力する(各解間の順序は重要ではない).各解は7行を占有します.すなわち,まず整数を出力し,その解のシーケンス番号(1から)を表し,次いで6 x 6のアルファベット行列を出力し,その解を表す.解のアルファベットの間をスペースで区切る.条件を満たす解が何も見つからない場合、例えば、ユーザ入力:000011 022013 2211113 243333 24455 445555 6 02 C 03 B 05 A 20 D 35 E 53 Fプログラム出力:1 EF C B D A A A C E D D A A A C E D D A B B E C F B D C A B D A A C E A A A A F B Dさらに、ユーザ入力:00111 002113 022443 022443 544433 555553 7 04 B 05 A 13 D 14 C 24 E 50 C 51 A則プログラム出力:1 D C E F B A E F A A E F A D C B A A B B F C E D B E D D A F C F D A A A A A A B E E C B E E F F 2 D C E F F A A E F A A A A A A A A A A A A A A A A A F F F D C A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A D C F E B AB E A D C F A D C F E B F B E A D C E F B C A D C A D B F E 5 D C F E B A E F A D C B A B C F E D B E D A F C F D B C A E C A E B D F 6 D C F E B A E F A D C B A B D F E C B E C A F D F D B C A E C A E B D F 7 D C F E B A E F A D C B A D B F E C B E C A F D F B D C A E C A E B D F 8 D C F E B A F E A D C B A D B C E F B F E A D C E B C F A D C A D B F E 9 D C F E B A F E A D C B A F C B E D B D E A F C E B D C A F C A B F D E
DFSのポイントは再帰関係を見つけることです.図に置くといつから、次の訪問先がどこにあるのか、これも本題の難点の一つです.以下で分析します.
一、まず、もし図を検索するならば、私达は次の(第1歩)がどこを検索するかを知っていなければならなくて、テーマを観察して、テーマの中で記入することを要求した后にすべての行のすべての列のすべての区域内のアルファベットはすべて異なって、明らかに、もし1行(1列)の中のアルファベットが多ければ多いほど、私达は残りの地方がどんなアルファベットを記入するべきかを確定しやすくて、この出発点に基づいて、プログラムは毎回このような点を探します:その行とその列の中のアルファベットの数の和が最も多くて、しかもこの位置はまだ空いていて、このような位置は1つだけではないかもしれませんが、私たちは最初に出会ったものを取ります.この演算を完了するために、hor[]とver[]の2つの配列を設定して、各行と各列に含まれるアルファベットの個数をそれぞれ記録します.
二、アルファベットを記入する位置を見つけたら、私たちはまた新しい問題に直面します.この位置はいったいどんなアルファベットを記入することができますか.タイトルに基づいて、A-Fの6文字のどちらが利用可能かを示すフラグビットuseful[]を設定し、この点がある行、所在する列、所在する領域をそれぞれスキャンします.出現したアルファベットであれば、自然に二度と現れません.ここでは、スキャン領域の方法について説明します.テーマで与えられたデータは、領域の記述に0～5の6つの数字でマークされているので、この特徴を利用して、配列を設定します.
area_used[i][j]は、i番目の領域でj+'A'というアルファベットが使用されているかどうかを示しています.この配列を利用すると、各領域に含まれるアルファベットの状況を簡単に統計することができます.
三、位置を見つけて、どれらの記入できるアルファベットを見つけたら、再帰的にアルファベットを記入することができて、1つのアルファベットを記入するたびに、次の層に入って再帰して、再帰の出口はすべてのアルファベットの数で、36に達すると自然に1組のテーマの要求に合致する解を見つけました.

#include<iostream>
#include<memory.h>
#include<stdio.h>
using namespace std;
char map[6][6];//            
char result[6][6];//      ，      
int hor[6],ver[6];//                
int last,cas;//           ，       
bool area_used[6][6];//                area_used[i][j]=true   i     j+'A'     

void getMap()//     
{
	char pre_word[3],t;
	int i,r,c,n;
	for(i=0;i<6;i++)
	cin>>map[i];
	cin>>n;
	for(i=0;i<n;i++)
	{
		cin>>pre_word;
		r=pre_word[0]-'0';
		c=pre_word[1]-'0';
		t=pre_word[2];
		ver[c]++;
		hor[r]++;
		result[r][c]=t;
		area_used[map[r][c]][t-'A']=true;
		last--;
	}
	
}

void init()//    
{
	memset(map,0,sizeof(map));
	memset(result,'*',sizeof(result));
	memset(hor,0,sizeof(hor));
	memset(ver,0,sizeof(ver));
	memset(area_used,false,sizeof(area_used));
	last=36;
	cas=0;
	for(int i=0;i<6;i++)
	result[i][6]='\0';
}

void showResult()//     
{
	int i,j;
	cout<<cas<<endl;
	for(i=0;i<6;i++)
	{
		for(j=0;j<6;j++)
		{
			cout<<result[i][j];
			if(j<5)
			cout<<' ';
		}
		cout<<endl;
	}
}

void search()//DFS   
{
	if(last==0)//     
	{
		cas++;
		showResult();
		return;
	}
	bool useful[6];//  A-F           
	int i,j,r,c,max;
	max=-1;
	memset(useful,true,sizeof(useful));
	last--;
	for(i=0;i<6;i++)//            
	{
		if(hor[i]<6)
		{
			for(j=0;j<6;j++)
			{
					if(hor[i]+ver[j]>max&&result[i][j]=='*')
					{
						max=hor[i]+ver[j];
						r=i;
						c=j;
					}
			}
		}
		
	}
	hor[r]++;
	ver[c]++;
	for(i=0;i<6;i++)//               
	{
		if(result[r][i]>='A'&&result[r][i]<='Z')
		useful[(int)(result[r][i]-'A')]=false;
		if(result[i][c]>='A'&&result[i][c]<='Z')
		useful[(int)(result[i][c]-'A')]=false;
		if(area_used[map[r][c]][i]==true)
		useful[i]=false;
	}
	
	for(i=0;i<6;i++)//                 
	{
		if(useful[i]==true)//       ，              ，       
		{
			result[r][c]=(char)(i+'A');		
			area_used[map[r][c]][i]=true;
			search();
			area_used[map[r][c]][i]=false;//  ，            
		}
	}
	hor[r]--;
	ver[c]--;
	result[r][c]='*';//             
	last++;
	
	
}
int main()
{
	init();
	getMap();
	search();
	return 0;
}