/******************************************************************
 *						Author:	Zhou Yundong
 *						Time: 20081222 23:08
 ******************************************************************/
/***************************************************
 * ① 优先格法
 * ② 一九在先法
 * ③ 三步一放法
 * ④ 同组初排法
 ***************************************************/
#include "Stdafx.h"
#include "Think.h"
#include "time.h"
#include "windows.h"
#include "MySopare.h"

struct GameBoard Gbak;
void stackToBoardPare()
{
	int i;
	int a, b, c;
	int value, temp;
	for(i=0; i<81; i++)
	{
		board[i] = 0;
	}
	for(i=0; i<SCnt; i++)
	{
		a = decompose[valueStack[i]];
		b = decompose[162+valueStack[i]];
		c = decompose[324+valueStack[i]];
		value = posStack[i] / 3 + 1;
		temp = baseIndex[posStack[i]];
		board[temp+a] = value;
		board[temp+b] = value;
		board[temp+c] = value;
	}
	for(i=21; i<24; i++)
	{
		a = decompose[valueStack[i]];
		b = decompose[162+valueStack[i]];
		c = decompose[324+valueStack[i]];
		temp = baseIndex[i-21];
		board[temp+a] = 1;
		board[temp+b] = 1;
		board[temp+c] = 1;
	}
	for(i=24; i<27; i++)
	{
		a = decompose[valueStack[i]];
		b = decompose[162+valueStack[i]];
		c = decompose[324+valueStack[i]];
		temp = baseIndex[i];
		board[temp+a] = 9;
		board[temp+b] = 9;
		board[temp+c] = 9;
	}
}

bool updateAreaPare2(int areaNo)
{
	int i, j, k, m, n;
	int pos[3], curPos;
	int value, topValue, bottomValue, temp;
	int grid;
	int bigColumn, bigRow;
	temp = G[PIdx].area[mult162[areaNo]];
	for(i=0; i<3; i++)
	{
		pos[i] = baseIndex[areaNo] + decompose[mult162[i]+temp];
	}
	value = areaNo / 3 + 1;
	// 3个索引如果触碰到bitpare表，那就反影响bitpare表所对应的另一个索引所在的区的area值
	for(i=0; i<3; i++)
	{
		curPos = pos[i];
		for(j=0; j<pDifferTop[curPos]; j++)
		{
			// 清除所有大于value-(differTop[curPos][j]>>8)的
			if((topValue=value-(differTop[curPos][j]>>8)) <= 0) return false;
			grid = differTop[curPos][j]&0xFF;
			bigColumn = divide3[grid%9];
			bigRow = grid / 27;
			temp = grid - mult27[bigRow];
			for(k=bigRow+mult3[topValue]; k<24; k+=3)
			{
				for(m=0; m<G[PIdx].left[k]; m++)
				{
					if(decompose[mult162[bigColumn]+G[PIdx].area[mult162[k]+m]] == temp)
					{
						for(n=m; n<G[PIdx].left[k]-1; n++)
						{
							G[PIdx].area[mult162[k]+n] = G[PIdx].area[mult162[k]+n+1];
						}
						if(--G[PIdx].left[k] == 0)
						{
							return false;
						}
						else if(G[PIdx].left[k] == 1)
						{
							PUSHSINGLE(k);
						}
						m--;
					}
				}
			}
		}
		for(j=0; j<pDifferBottom[curPos]; j++)
		{
			// 清除所有小于value+(differBottom[curPos][j]>>8)的
			if((bottomValue=value+(differBottom[curPos][j]>>8)) >= 10) return false;
			grid = differBottom[curPos][j]&0xFF;
			bigColumn = divide3[grid%9];
			bigRow = grid / 27;
			temp = grid - mult27[bigRow];
			for(k=bigRow+mult3[bottomValue-2]; k>=3; k-=3)
			{
				for(m=0; m<G[PIdx].left[k]; m++)
				{
					if(decompose[mult162[bigColumn]+G[PIdx].area[mult162[k]+m]] == temp)
					{
						for(n=m; n<G[PIdx].left[k]-1; n++)
						{
							G[PIdx].area[mult162[k]+n] = G[PIdx].area[mult162[k]+n+1];
						}
						if(--G[PIdx].left[k] == 0)
						{
							return false;
						}
						else if(G[PIdx].left[k] == 1)
						{
							PUSHSINGLE(k);
						}
						m--;
					}
				}
			}
		}
	}
	return true;
}

bool updateAreaPare(int i)
{
	int m, n, k;
	int thisArea, thatIndex;
	int temp;
	// self check
	thisArea = mult162[G[PIdx].area[mult162[i]]];
	for(m=trim3[i]-3; m<trim3[i]; m++)
	{
		if(m == i)
		{
			continue;
		}
		temp = G[PIdx].left[m];
		for(n=0; n<temp; n++)
		{
			thatIndex = mult162[m] + n;
			if(self[thisArea+G[PIdx].area[thatIndex]])
			{
				for(k=n; k<temp-1; k++)
				{
					G[PIdx].area[mult162[m]+k] = G[PIdx].area[mult162[m]+k+1];
				}
				if(--temp == 0)
				{
					return false;
				}
				else if(temp == 1)
				{
					PUSHSINGLE(m);
				}
				n--;
			}
		}
		G[PIdx].left[m] = temp;
	}
	// other check
	for(m=mod3[i]+3; m<24; m+=3)
	{
		if(m == i)
		{
			continue;
		}
		temp = G[PIdx].left[m];
		for(n=0; n<temp; n++)
		{
			thatIndex = mult162[m] + n;
			if(other[thisArea+G[PIdx].area[thatIndex]])
			{
				for(k=n; k<temp-1; k++)
				{
					G[PIdx].area[mult162[m]+k] = G[PIdx].area[mult162[m]+k+1];
				}
				if(--temp == 0)
				{
					return false;
				}
				else if(temp == 1)
				{
					PUSHSINGLE(m);
				}
				n--;
			}
		}
		G[PIdx].left[m] = temp;
	}
	// pare check
	return updateAreaPare2(i);
}

void backTrackPare()
{
	int i, j, k;
	int temp, temp2;
	int least;
	int multLeast;
	int leastArea[IndexEnd];
next:
	for(i=G[PIdx].SCnt; i<SCnt; i++)
	{
		if(!updateAreaPare(posStack[i]))
		{
again:		if(--PIdx == -1)
			{
				return;
			}
			least = leastArea[PIdx];
			if(G[PIdx].left[least] == 0)
			{
				goto again;
			}
			SCnt = G[PIdx+1].SCnt;
			multLeast = mult162[least];
			G[PIdx].area[multLeast] = G[PIdx].area[multLeast+G[PIdx].cntGuessed++];
			posStack[SCnt] = least;
			valueStack[SCnt++] = G[PIdx].area[multLeast];
			for(j=3; j<24; j++)
			{
				temp = G[PIdx].left[j];
				G[PIdx+1].left[j] = temp;
				temp2 = mult162[j];
				for(k=0; k<temp; k++)
				{
					G[PIdx+1].area[temp2+k] = G[PIdx].area[temp2+k];
				}
			}
			G[PIdx].left[least]--;
			PIdx++;
			G[PIdx].left[least] = 1;
			G[PIdx].cntGuessed = 0;
			G[PIdx].SCnt = SCnt-1;
			goto next;
		}
	}
	if(i == 21)
	{
		if(flagAnswer == 0)
		{
			flagAnswer = 1;
			if(underQuestion == 0)
			{
				stackToBoardPare(); // valueStack[0,1,2] to board[posStack[0,1,2]]
				moveBoard('b', 'a'); // board to answerBoard
			}
			goto again;
		}
		else
		{
			flagAnswer = 2;
			return;
		}
	}
	least = 163;
	for(i=3; i<24; i++)
	{
		if(G[PIdx].left[i] < least && G[PIdx].left[i] != 1)
		{
			least = G[PIdx].left[i];
			leastArea[PIdx] = i;
			if(least == 2)
			{
				break;
			}
		}
	}
	least = leastArea[PIdx];
	multLeast = mult162[least];
	G[PIdx].area[multLeast] = G[PIdx].area[multLeast+G[PIdx].cntGuessed++];
	posStack[SCnt] = least;
	valueStack[SCnt++] = G[PIdx].area[multLeast];
	for(j=3; j<24; j++)
	{
		temp = G[PIdx].left[j];
		G[PIdx+1].left[j] = temp;
		temp2 = mult162[j];
		for(k=0; k<temp; k++)
		{
			G[PIdx+1].area[temp2+k] = G[PIdx].area[temp2+k];
		}
	}
	G[PIdx].left[least]--;
	PIdx++;
	G[PIdx].left[least] = 1;
	G[PIdx].cntGuessed = 0;
	G[PIdx].SCnt = SCnt-1;
	goto next;
}

void otherCheckMiddle(int p0, int p1, int p2, int p24, int p25, int p26)
{
	int i, j, k, m;
	int base, count;
	int grid;
	// 他排除2到8
	for(i=3; i<24; i+=3)
	{
		base = mult162[i];
		for(j=0; j<G[0].left[i]; j++)
		{
			if(other[mult162[p0]+G[0].area[base+j]])
			{
				G[0].area[base+j] = -1;
			}
			else if(other[mult162[p24]+G[0].area[base+j]])
			{
				G[0].area[base+j] = -1;
			}
		}
	}
	for(i=4; i<24; i+=3)
	{
		base = mult162[i];
		for(j=0; j<G[0].left[i]; j++)
		{
			if(other[mult162[p1]+G[0].area[base+j]])
			{
				G[0].area[base+j] = -1;
			}
			else if(other[mult162[p25]+G[0].area[base+j]])
			{
				G[0].area[base+j] = -1;
			}
		}
	}
	for(i=5; i<24; i+=3)
	{
		base = mult162[i];
		for(j=0; j<G[0].left[i]; j++)
		{
			if(other[mult162[p2]+G[0].area[base+j]])
			{
				G[0].area[base+j] = -1;
			}
			else if(other[mult162[p26]+G[0].area[base+j]])
			{
				G[0].area[base+j] = -1;
			}
		}
	}
	// 不等号排除2和8的部分
	for(i=3; i<6; i++)
	{
next2:	for(j=0; j<G[0].left[i]; j++)
		{
			if(G[0].area[mult162[i]+j] == -1) continue;
			for(k=0; k<3; k++)
			{
				grid = baseIndex[i]+decompose[mult162[k]+G[0].area[mult162[i]+j]];
				for(m=0; m<pDifferTop[grid]; m++)
				{
					if(board[differTop[grid][m]&0xFF] != 1)
					{
						G[0].area[mult162[i]+j] = -1;
						goto next2;
					}
				}
			}
		}
	}
	for(i=21; i<24; i++)
	{
next8:	for(j=0; j<G[0].left[i]; j++)
		{
			if(G[0].area[mult162[i]+j] == -1) continue;
			for(k=0; k<3; k++)
			{
				grid = baseIndex[i]+decompose[mult162[k]+G[0].area[mult162[i]+j]];
				for(m=0; m<pDifferBottom[grid]; m++)
				{
					if(board[differBottom[grid][m]&0xFF] != 9)
					{
						G[0].area[mult162[i]+j] = -1;
						goto next8;
					}
				}
			}
		}
	}
	// 不等号排除3和7的部分
	for(i=6; i<9; i++)
	{
next3:	for(j=0; j<G[0].left[i]; j++)
		{
			if(G[0].area[mult162[i]+j] == -1) continue;
			for(k=0; k<3; k++)
			{
				grid = baseIndex[i]+decompose[mult162[k]+G[0].area[mult162[i]+j]];
				for(m=0; m<pDifferTop[grid]; m++)
				{
					if((differTop[grid][m]>>8) == 2 && board[differTop[grid][m]&0xFF] != 1)
					{
						G[0].area[mult162[i]+j] = -1;
						goto next3;
					}
				}
			}
		}
	}
	for(i=18; i<21; i++)
	{
next7:	for(j=0; j<G[0].left[i]; j++)
		{
			if(G[0].area[mult162[i]+j] == -1) continue;
			for(k=0; k<3; k++)
			{
				grid = baseIndex[i]+decompose[mult162[k]+G[0].area[mult162[i]+j]];
				for(m=0; m<pDifferBottom[grid]; m++)
				{
					if((differBottom[grid][m]>>8) == 2 && board[differBottom[grid][m]&0xFF] != 9)
					{
						G[0].area[mult162[i]+j] = -1;
						goto next7;
					}
				}
			}
		}
	}
	// 不等号排除4和6的部分
	for(i=9; i<12; i++)
	{
next4:	for(j=0; j<G[0].left[i]; j++)
		{
			if(G[0].area[mult162[i]+j] == -1) continue;
			for(k=0; k<3; k++)
			{
				grid = baseIndex[i]+decompose[mult162[k]+G[0].area[mult162[i]+j]];
				for(m=0; m<pDifferTop[grid]; m++)
				{
					if((differTop[grid][m]>>8) == 3 && board[differTop[grid][m]&0xFF] != 1)
					{
						G[0].area[mult162[i]+j] = -1;
						goto next4;
					}
				}
			}
		}
	}
	for(i=15; i<18; i++)
	{
next6:	for(j=0; j<G[0].left[i]; j++)
		{
			if(G[0].area[mult162[i]+j] == -1) continue;
			for(k=0; k<3; k++)
			{
				grid = baseIndex[i]+decompose[mult162[k]+G[0].area[mult162[i]+j]];
				for(m=0; m<pDifferBottom[grid]; m++)
				{
					if((differBottom[grid][m]>>8) == 3 && board[differBottom[grid][m]&0xFF] != 9)
					{
						G[0].area[mult162[i]+j] = -1;
						goto next6;
					}
				}
			}
		}
	}
	// 去除-1
	for(i=3; i<24; i++)
	{
		count = 0;
		for(j=0; j<G[0].left[i]; j++)
		{
			if(G[0].area[mult162[i]+j] != -1)
			{
				G[0].area[mult162[i]+count++] = G[0].area[mult162[i]+j];
			}
		}
		G[0].left[i] = count;
		if(count == 0) return;
		else if(count == 1) PUSHSINGLE(i);
	}
	backTrackPare();
}

void resumeGbak()
{
	int i, j;
	for(i=3; i<24; i++)
	{
		G[0].left[i] = Gbak.left[i];
		for(j=0; j<Gbak.left[i]; j++)
		{
			G[0].area[mult162[i]+j] = Gbak.area[mult162[i]+j];
		}
	}
}

void storeGbak()
{
	int i, j;
	for(i=3; i<24; i++)
	{
		Gbak.left[i] = G[0].left[i];
		for(j=0; j<Gbak.left[i]; j++)
		{
			Gbak.area[mult162[i]+j] = G[0].area[mult162[i]+j];
		}
	}
}

void getAnswerPare()
{
	int i, j, k, l, m, n;
	int area0[162], area1[162], area2[162], area24[162], area25[162], area26[162];
	int left[27];
	if(!initAreaPare())	return;
	storeGbak(); // 保存初始状态到Gbak
	for(i=0; i<3; i++)
	{
		left[i] = G[0].left[i];
		left[i+24] = G[0].left[i+24];
	}
	for(i=0; i<left[0]; i++)
	{
		area0[i] = G[0].area[i];
	}
	for(i=0; i<left[1]; i++)
	{
		area1[i] = G[0].area[162+i];
	}
	for(i=0; i<left[2]; i++)
	{
		area2[i] = G[0].area[324+i];
	}
	for(i=0; i<left[24]; i++)
	{
		area24[i] = G[0].area[3888+i];
	}
	for(i=0; i<left[25]; i++)
	{
		area25[i] = G[0].area[4050+i];
	}
	for(i=0; i<left[26]; i++)
	{
		area26[i] = G[0].area[4212+i];
	}
	for(i=0; i<left[0]; i++)
	{
		for(j=0; j<left[1]; j++)
		{
			if(self[mult162[area0[i]]+area1[j]]) continue;
			for(k=0; k<left[2]; k++)
			{
				if(self[mult162[area0[i]]+area2[k]] || self[mult162[area1[j]]+area2[k]]) continue;
				for(l=0; l<left[24]; l++)
				{
					if(other[mult162[area0[i]]+area24[l]]) continue;
					for(m=0; m<left[25]; m++)
					{
						if(self[mult162[area24[l]]+area25[m]] || other[mult162[area1[j]]+area25[m]]) continue;
						for(n=0; n<left[26]; n++)
						{
							if(self[mult162[area24[l]]+area26[n]] || self[mult162[area25[m]]+area26[n]] || other[mult162[area2[k]]+area26[n]]) continue;
							resumeGbak(); // 还原到G[0]
							if(flagAnswer == 2) return;
							valueStack[21] = area0[i];
							valueStack[22] = area1[j];
							valueStack[23] = area2[k];
							valueStack[24] = area24[l];
							valueStack[25] = area25[m];
							valueStack[26] = area26[n];
							PIdx = SCnt = G[0].SCnt = G[0].cntGuessed = 0;
							stackToBoardPare();
							otherCheckMiddle(area0[i], area1[j], area2[k], area24[l], area25[m], area26[n]);
						}
					}
				}
			}
		}
	}
}

void handleAnswerPare()
{
	rightStatus = 1;
	movePare('l', 'p');
	getAnswerPare(); // 启动求解过程
	if(firstIntoSodoku) // 只在第一次变成数比状态时才清右盘
	{
		firstIntoSodoku = false;
		moveSum('0', 'r');
		moveIdx('0', 'r');
		moveUniq('0', 'r');
		moveKilpare('0', 'r');
		moveSaw('0', 'r');
		moveColorSaw('l', 'r');
		moveExtra('0', 'r');
		gameKindRight = 2;
		pRightCircle = 0;
	}
	if(flagAnswer == 0)
	{
		moveBoard('0', 'r');
		movePare('0', 'r');
	}
	else
	{
		moveBoard('a', 'r');
		movePare('p', 'r');
	}
	underThinking = false;
}
