/******************************************************************
 *						Author:	Zhou Yundong
 *						Time: 20080425 20:49
 ******************************************************************/
#include "Stdafx.h"
#include "Think.h"
#include "MySopare.h"

void getPriority()
{
	int i, j, k;
	int temp, temp2;
	int a, b, c;
	// 利用一下G[1]，特殊用法
	for(i=0; i<81; i++)
	{
		priority[i] = pDifferTop[i] + pDifferBottom[i];
	}
	for(i=0; i<27; i++)
	{
		for(j=0; j<G[0].left[i]; j++)
		{
			temp = mult162[i] + j;
			a = decompose[G[0].area[temp]];
			b = decompose[162+G[0].area[temp]];
			c = decompose[324+G[0].area[temp]];
			G[1].area[temp] = priority[a] + priority[b] + priority[c];
		}
		G[1].left[i] = G[0].left[i];
	}
	// 排序
	for(i=0; i<27; i++)
	{
		for(j=0; j<G[1].left[i]-1; j++)
		{
			for(k=j+1; k<G[1].left[i]; k++)
			{
				temp = mult162[i];
				if(G[1].area[temp+j] < G[1].area[temp+k])
				{
					temp2 = G[1].area[temp+j];
					G[1].area[temp+j] = G[1].area[temp+k];
					G[1].area[temp+k] = temp2;
					temp2 = G[0].area[temp+j];
					G[0].area[temp+j] = G[0].area[temp+k];
					G[0].area[temp+k] = temp2;
				}
			}
		}
	}
	for(i=0; i<27; i++)
	{
		G[1].left[i] = 0;
	}
}

/***********************************************
 * 同组初排法:
 * 凡是向外辐射了两个以上大于号的，最小值都要提升
 * 那么大于这些最小值的都要依次提升
 * 必须容纳在同一组下
 ***********************************************/
void initAreaPare4()
{
	int i, j;
	int groupNo;
	for(i=0; i<81; i++)
	{
		if(pDifferBottom[i] < 2 || maxBoardFlg[i]) continue;
		// 检查是否同宫
		groupNo = squareNoTbl[i];
		if(squareNoTbl[differBottom[i][0]&0xFF] == groupNo)
		{
			for(j=1; j<pDifferBottom[i]; j++)
			{
				if(squareNoTbl[differBottom[i][j]&0xFF] != groupNo)
				{
					break;
				}
			}
			if(j == pDifferBottom[i])
			{
				maxBoard[i] = 9 - pDifferBottom[i];
				continue;
			}
		}
		if(pDifferBottom[i] < 2 || maxBoardFlg[i]) continue;
		// 检查是否同行
		groupNo = rowNoTbl[i];
		if(rowNoTbl[differBottom[i][0]&0xFF] == groupNo)
		{
			for(j=1; j<pDifferBottom[i]; j++)
			{
				if(rowNoTbl[differBottom[i][j]&0xFF] != groupNo)
				{
					break;
				}
			}
			if(j == pDifferBottom[i])
			{
				maxBoard[i] = 9 - pDifferBottom[i];
				continue;
			}
		}
		if(pDifferBottom[i] < 2 || maxBoardFlg[i]) continue;
		// 检查是否同列
		groupNo = columnNoTbl[i];
		if(columnNoTbl[differBottom[i][0]&0xFF] == groupNo)
		{
			for(j=1; j<pDifferBottom[i]; j++)
			{
				if(columnNoTbl[differBottom[i][j]&0xFF] != groupNo)
				{
					break;
				}
			}
			if(j == pDifferBottom[i])
			{
				maxBoard[i] = 9 - pDifferBottom[i];
				continue;
			}
		}
	}
	for(i=0; i<81; i++)
	{
		if(pDifferTop[i] < 2 || minBoardFlg[i]) continue;
		// 检查是否同宫
		groupNo = squareNoTbl[i];
		if(squareNoTbl[differTop[i][0]&0xFF] == groupNo)
		{
			for(j=1; j<pDifferTop[i]; j++)
			{
				if(squareNoTbl[differTop[i][j]&0xFF] != groupNo)
				{
					break;
				}
			}
			if(j == pDifferTop[i])
			{
				minBoard[i] = pDifferTop[i]+1;
				continue;
			}
		}
		if(pDifferTop[i] < 2 || minBoardFlg[i]) continue;
		// 检查是否同行
		groupNo = rowNoTbl[i];
		if(rowNoTbl[differTop[i][0]&0xFF] == groupNo)
		{
			for(j=1; j<pDifferTop[i]; j++)
			{
				if(rowNoTbl[differTop[i][j]&0xFF] != groupNo)
				{
					break;
				}
			}
			if(j == pDifferTop[i])
			{
				minBoard[i] = pDifferTop[i]+1;
				continue;
			}
		}
		if(pDifferTop[i] < 2 || minBoardFlg[i]) continue;
		// 检查是否同列
		groupNo = columnNoTbl[i];
		if(columnNoTbl[differTop[i][0]&0xFF] == groupNo)
		{
			for(j=1; j<pDifferTop[i]; j++)
			{
				if(columnNoTbl[differTop[i][j]&0xFF] != groupNo)
				{
					break;
				}
			}
			if(j == pDifferTop[i])
			{
				minBoard[i] = pDifferTop[i]+1;
				continue;
			}
		}
	}
}

bool initAreaPare3(int grid, int era)
{
	if(era >= 10)
	{
		return false;
	}
	if(grid >= 9 && pare[grid+63] == 2)
	{
		if((differTop[startGrid][grid-9]>>8) < era)
		{
			differTop[startGrid][pDifferTop[startGrid]++] = (era<<8)+grid-9;
		}
		if(!initAreaPare3(grid-9, era+1)) return false;
	}
	if(mod9[grid] <= 7 && pare[grid-grid/9] == 1)
	{
		if((differTop[startGrid][grid+1]>>8) < era)
		{
			differTop[startGrid][pDifferTop[startGrid]++] = (era<<8)+grid+1;
		}
		if(!initAreaPare3(grid+1, era+1)) return false;
	}
	if(grid <= 71 && pare[grid+72] == 1)
	{
		if((differTop[startGrid][grid+9]>>8) < era)
		{
			differTop[startGrid][pDifferTop[startGrid]++] = (era<<8)+grid+9;
		}
		if(!initAreaPare3(grid+9, era+1)) return false;
	}
	if(mod9[grid] >= 1 && pare[grid-1-grid/9] == 2)
	{
		if((differTop[startGrid][grid-1]>>8) < era)
		{
			differTop[startGrid][pDifferTop[startGrid]++] = (era<<8)+grid-1;
		}
		if(!initAreaPare3(grid-1, era+1)) return false;
	}
	return true;
}

bool initAreaPare2()
{
	int i, j, k, m;
	int temp;
	for(i=0; i<81; i++)
	{
		for(j=0; j<pDifferTop[i]; j++)
		{
			differTop[i][j] = 0;
		}
		pDifferTop[i] = 0;
		for(j=0; j<pDifferBottom[i]; j++)
		{
			differBottom[i][j] = 0;
		}
		pDifferBottom[i] = 0;
	}
	// 考虑大于号发出的“列车”
	for(i=0; i<81; i++)
	{
		startGrid = i;
		if(!initAreaPare3(i, 1)) return false;
		for(j=0; j<pDifferTop[i]-1; j++)
		{
			for(k=j+1; k<pDifferTop[i]; k++)
			{
				if(differTop[i][j] < differTop[i][k])
				{
					temp = differTop[i][k];
					differTop[i][k] = differTop[i][j];
					differTop[i][j] = temp;
				}
			}
		}
		for(j=0; j<pDifferTop[i]-1; j++)
		{
			for(k=j+1; k<pDifferTop[i]; k++)
			{
				if((differTop[i][j]&0xFF) == (differTop[i][k]&0xFF))
				{
					pDifferTop[i]--;
					for(m=k; m<pDifferTop[i]; m++)
					{
						differTop[i][m] = differTop[i][m+1];
					}
					k--;
					differTop[i][m] = 0;
				}
			}
		}
	}
	// 考虑小于号发出的“列车”
	for(i=0; i<81; i++)
	{
		for(j=0; j<pDifferTop[i]; j++)
		{
			temp = differTop[i][j];
			differBottom[temp&0xFF][pDifferBottom[temp&0xFF]++] = (temp&0xFF00)+i;
		}
	}
	return true;
}

bool initAreaPare()
{
	int i, j;
	int value;
	int squareNo;
	int list[81];
	int temp, temp2;
	int pList0, pList1, pList2;
	int listStack0[9], listStack1[9], listStack2[9];
	int p0, p1, p2;
	int max, min;
	PIdx = flagAnswer = 0;
	for(i=0; i<81; i+=3)
	{
		list[i] = list[i+1] = list[i+2] = 511;
		maxBoard[i] = maxBoard[i+1] = maxBoard[i+2] = 0;
		minBoard[i] = minBoard[i+1] = minBoard[i+2] = 0;
		maxBoardFlg[i] = maxBoardFlg[i+1] = maxBoardFlg[i+2] = false;
		minBoardFlg[i] = minBoardFlg[i+1] = minBoardFlg[i+2] = false;
	}
	// board to list[81]
	for(i=0; i<81; i++)
	{
		if((value=board[i]-1) == -1) // board[i] is '0'
		{
			continue;
		}
		squareNo = squareNoTbl[i];
		temp = mult9[value] + squareNo;
		temp2 = ~areaTrans[i];
		for(j=squareNo; j<81; j+=9)
		{
			list[j] = list[j] & temp2;
		}
		list[temp] = areaTrans[i];
		if(mod3[squareNo] == 0)
		{
			list[temp+1] &= areaRow[i];
			list[temp+2] &= areaRow[i];
		}
		else if(mod3[squareNo] == 1)
		{
			list[temp-1] &= areaRow[i];
			list[temp+1] &= areaRow[i];
		}
		else
		{
			list[temp-2] &= areaRow[i];
			list[temp-1] &= areaRow[i];
		}
		if(squareNo < 3)
		{
			list[temp+3] &= areaColumn[i];
			list[temp+6] &= areaColumn[i];
		}
		else if(squareNo < 6)
		{
			list[temp-3] &= areaColumn[i];
			list[temp+3] &= areaColumn[i];
		}
		else
		{
			list[temp-6] &= areaColumn[i];
			list[temp-3] &= areaColumn[i];
		}
	}
	if(!initAreaPare2()) return false;
	// 求maxBoard[]与minBoard[]，同时受定值影响的不考虑
	for(i=0; i<81; i++)
	{
		if(pDifferBottom[i] == 0) continue;
		max = 0;
		for(j=0; j<pDifferBottom[i]; j++)
		{
			if(board[differBottom[i][j]&0xFF] != 0)
			{
				if(max < ((9-board[differBottom[i][j]&0xFF])<<8)+differBottom[i][j])
				{
					max = ((9-board[differBottom[i][j]&0xFF])<<8)+differBottom[i][j];
					maxBoardFlg[i] = true;
				}
			}
			else
			{
				if(max <= differBottom[i][j])
				{
					max = differBottom[i][j];
					maxBoardFlg[i] = false;
				}
			}
		}
		maxBoard[i] = max = 9 - (max>>8);
	}
	for(i=0; i<81; i++)
	{
		if(pDifferTop[i] == 0) continue;
		min = 0;
		for(j=0; j<pDifferTop[i]; j++)
		{
			if(board[differTop[i][j]&0xFF] != 0)
			{
				if(min < ((board[differTop[i][j]&0xFF]-1)<<8)+differTop[i][j])
				{
					min = ((board[differTop[i][j]&0xFF]-1)<<8)+differTop[i][j];
					minBoardFlg[i] = true;
				}
			}
			else
			{
				if(min <= differTop[i][j])
				{
					min = differTop[i][j];
					minBoardFlg[i] = false;
				}
			}
		}
		minBoard[i] = min = (min>>8) + 1;
	}
	initAreaPare4(); // 进一步求maxBoard[] 与 minBoard[]
	for(i=0; i<81; i++)
	{
		if(maxBoard[i] == 0) continue;
		// 清除所有大于max的
		for(j=maxBoard[i]+1; j<=9; j++)
		{
			list[squareNoTbl[i]+mult9[j-1]] &= ~areaTrans[i];
		}
	}
	for(i=0; i<81; i++)
	{
		if(minBoard[i] == 0) continue;
		// 清除所有小于min的
		for(j=1; j<minBoard[i]; j++)
		{
			list[squareNoTbl[i]+mult9[j-1]] &= ~areaTrans[i];
		}
	}
	// legal check
	for(i=0; i<81; i++)
	{
		if((value=board[i]-1) != -1 && list[mult9[value]+squareNoTbl[i]] != areaTrans[i])
		{
			return false;
		}
	}
	for(i=0; i<81; i+=3)
	{
		// compress list[81] to pList0, pList1, pList2
		pList0 = pList1 = pList2 = 0;
		while((temp=lastOneTbl[list[i]]) != 9)
		{
			listStack0[pList0++] = temp;
			list[i] = list[i] & ~(1<<temp);
		}
		while((temp=lastOneTbl[list[i+1]]) != 9)
		{
			listStack1[pList1++] = temp;
			list[i+1] = list[i+1] & ~(1<<temp);
		}
		while((temp=lastOneTbl[list[i+2]]) != 9)
		{
			listStack2[pList2++] = temp;
			list[i+2] = list[i+2] & ~(1<<temp);
		}
		// set G[0].area and G[0].left
		G[0].left[divide3[i]] = 0;
		for(p0=0; p0<pList0; p0++)
		{
			for(p1=0; p1<pList1; p1++)
			{
				temp2 = mult81[listStack0[p0]]+mult9[listStack1[p1]];
				for(p2=0; p2<pList2; p2++)
				{
					if((temp=create[temp2+listStack2[p2]]) != 162)
					{
						G[0].area[mult162[divide3[i]]+G[0].left[divide3[i]]++] = temp;
					}
				}
			}
		}
	}
	getPriority(); // 并且对27个区的各摆法排序
	for(i=0; i<27; i++)
	{
		if((temp=G[0].left[i]) == 0)
		{
			return false;
		}
	}
	return true;
}
