display.cpp

来自「一个在VISUAL C++下编程的soduku系统 里面有界面 有出盘 也比较简」· C++ 代码 · 共 1,214 行 · 第 1/3 页

	r = row - (row % 3);
	c = col - (col % 3);

	for (j=r; j<r+3; j++){
		for (k=c; k<c+3; k++){
			if (NoOfPoss(all[j][k]) <= poss){
				if ( (all[j][k] & ~cell) == 0 ){
					found++;
					if (!QuickSolve && setBlue)
						BlueBits[j][k] = cell;
				}
			}
		}
	}
	return found;
}

/*------------------------------------------------------------
  Eliminate values defined by cell from a row
------------------------------------------------------------*/
unsigned CDisplay::eliminate_row_dup(unsigned row, unsigned cell)
{
	unsigned i, eliminated;
	
	eliminated = 0;
	
	for (i=0; i<9; i++){
		if ( (all[row][i] & cell) && ((all[row][i] & ~cell) != 0) ) {
			all[row][i] &= ~cell;
			if (!QuickSolve)
				RedBits[row][i] = cell;
			eliminated++;
		}
	}
	return eliminated;
}

/*------------------------------------------------------------
  Eliminate values defined by cell from a col
------------------------------------------------------------*/
unsigned CDisplay::eliminate_col_dup(unsigned col, unsigned cell)
{
	unsigned i, eliminated;
	
	eliminated = 0;
	
	for (i=0; i<9; i++){
		if ( (all[i][col] & cell) && ((all[i][col] & ~cell) != 0) ) {
			all[i][col] &= ~cell;
			eliminated++;
			if (!QuickSolve)
				RedBits[i][col] = cell;
		}
	}
	return eliminated;
}

/*------------------------------------------------------------
  Eliminate values defined by cell from a 3x3
------------------------------------------------------------*/
unsigned CDisplay::eliminate_3x3_dup(unsigned row, unsigned col, unsigned cell)
{

	unsigned r, c, j, k, eliminated;
	
	eliminated = 0;
	r = row - (row % 3);
	c = col - (col % 3);

	for (j=r; j<r+3; j++){
		for (k=c; k<c+3; k++){
		if ( (all[j][k] & cell) && ((all[j][k] & ~cell) != 0) ) {
				all[j][k] &= ~cell;
				eliminated++;
				if (!QuickSolve)
					RedBits[j][k] = cell;
			}
		}
	}
	return eliminated;
}

/*------------------------------------------------------------
  Calculate no of values to eliminate
------------------------------------------------------------*/
unsigned CDisplay::total_poss()
{
	unsigned char j,k;
	unsigned t=0;
	
	for (j=0; j<9; j++)
		for (k=0; k<9; k++){
			t += NoOfPoss( all[j][k] ) - 1;
		}
	return t;
}

signed CDisplay::solve()
{
	unsigned t, left, this_loop, j, k;
	int 	tt;
	
	printf("Orignal puzzle is\n");
	//dump_all();
	
	msgstr = _T("");
	for (j=0; j<9; j++)
		for (k=0; k<9; k++)
			pCell[j][k]->SetBackgroundColor(FALSE, cellDefaultColor);

	//printf("Total nos to eliminate are %d\n", total_poss());
		if (total_poss()==0){
			dump_all();
			AfxMessageBox("   ***SOLVED***   ");
			return 0;
		}
	
	do{
		this_loop = 0;
		//dump_all();

		left = total_poss();
		//WaitForButton();

		if (!left)
			break;

		t = 1;
		tt = remove_dup(t);
		if (tt == -1)
			return -1;
			
		this_loop += tt;
		if (tt)
			continue;
		
		tt = eliminate_lonely();
		this_loop += tt;
		if (tt)
			continue;
		
		t = 2;
		tt = remove_dup(t);
		this_loop += tt;
		if (tt)
			continue;
					
		t = 3;
		tt = remove_dup(t);
		this_loop += tt;
		if (tt)
			continue;
		
		t = 4;
		tt = remove_dup(t);
		this_loop += tt;
		if (tt)
			continue;
	
		t = 5;
		tt = remove_dup(t);
		this_loop += tt;
		if (tt)
			continue;

		t = 6;
		tt = remove_dup(t);
		this_loop += tt;
		if (tt)
			continue;

		t = 7;
		tt = remove_dup(t);
		this_loop += tt;
		if (tt)
			continue;

		tt = eliminate_lonely_cross();
		this_loop += tt;

	}while(0);
	dump_all();
	if (!this_loop)
		AfxMessageBox("Sorry, that's the best I can do without guessing\nYou can try 'QuickSolve' button for complete solution");
	
	return this_loop;	
}

unsigned CDisplay::dump_all()
{
#if 1
	//CString str = _T("{\\rtf1\\ansi\\ansicpg1252\\deff0\\deflang1031{\\fonttbl{\\f0\\fnil\\fcharset0 Courier New;}}{\\colortbl ;\\red0\\green0\\blue0;\\red255\\green0\\blue0;\\red0\\green255\\blue0;\\red0\\green0\\blue255;}");
	//CString str = _T("{\\rtf1\\ansi\\ansicpg1252\\deff0\\deflang1031{\\fonttbl{\\f0\\fnil\\fcharset0 Arial;}}{\\colortbl ;\\red0\\green0\\blue0;\\red255\\green0\\blue0;\\red0\\green255\\blue0;\\red0\\green0\\blue255;}");
	CString str = _T("{\\rtf1\\ansi\\ansicpg1252\\deff0\\deflang1031{\\fonttbl{\\f0\\fnil\\fcharset0 Courier New;}}{\\colortbl ;\\red140\\green140\\blue140;\\red255\\green0\\blue0;\\red67\\green186\\blue50;\\red0\\green0\\blue255;}");
	CString cellstr, tmpstr, strempty=_T("");
	char buf[100];
	unsigned int j, k, val, bm;

	for (j=0; j<9; j++){
		for (k=0; k<9; k++){
			cellstr = str;
			if ( NoOfPoss(all[j][k]) == 1 && NoOfPoss(RedBits[j][k]) == 0){
				cellstr += "\\fs40 ";
				if (NoOfPoss(BlueBits[j][k]) == 0)
					cellstr += "\\cf3 \\b ";
				else
					cellstr += "\\cf4 \\b ";

				for (val=0,bm=all[j][k]; bm!=0; val++,bm>>=1);
				tmpstr.Format("%d", val);
				cellstr += tmpstr;
				setRTF(pCell[j][k], cellstr);
			} else {
				cellstr += "\\fs19 ";
				for (val=1; val<=9; val++){
					bm = 0x1 << (val-1);
					if (RedBits[j][k] & bm)
						cellstr += "\\cf2 \\b ";
					else if (BlueBits[j][k] & bm)
						cellstr += "\\cf4 \\b ";
					else
						cellstr += "\\cf1 \\b0 ";
					 if ( (RedBits[j][k] & bm) || (all[j][k] & bm) || (BlueBits[j][k] & bm))
						 tmpstr.Format("%d", val);
					 else
						 tmpstr.Format(".");
					 cellstr += tmpstr;
					 if (val==5){
						 cellstr += "\\par ";
					 }
				}
				cellstr += " ";
				setRTF(pCell[j][k], cellstr);
			}
			RedBits[j][k] = BlueBits[j][k] = 0;
		}
	}

	return total_poss();
#else
	return 0;
#endif
}

unsigned CDisplay::DoQuickSolve()
{
	unsigned this_loop, j, k, bm, last, org_all[9][9], left;
	int	tt;

	do{
		this_loop = 0;
		left = total_poss();

		if (!left)
			break;

		tt = remove_dup(1);
		if (tt == -1)
			return 0;
			
		this_loop += tt;
		if (tt)
			continue;
		
		tt = eliminate_lonely();
		this_loop += tt;
		if (tt)
			continue;
		
		tt = remove_dup(2);
		this_loop += tt;
		if (tt)
			continue;
					
		tt = remove_dup(3);
		this_loop += tt;
		if (tt)
			continue;
		
		tt = remove_dup(4);
		this_loop += tt;
		if (tt)
			continue;
	
		tt = eliminate_lonely_cross();
		this_loop += tt;

	}while(this_loop);
	
	if (total_poss()){
		for (j=0; j<9; j++){
			for (k=0; k<9; k++){
				if (NoOfPoss( all[j][k]) > 1){
					memcpy(org_all, all, 9*9*sizeof(unsigned));
					for (bm=0x1; bm<=0x100; bm<<=1){
						if (all[j][k] & bm){
							last = all[j][k];
							all[j][k] = bm;
							if (StopGuess)
								return 0;
							if (total_guesses && !(total_guesses % 300)){
								CString str;
								str.Format("So far I've guessed %d values\nAnd had found %d solution(s)\nDo you want me to look for more?", total_guesses, NoOfSol);
								if (AfxMessageBox(str, MB_YESNO | MB_ICONQUESTION) == IDNO){
									StopGuess = 1;
									return 0;
								}
							}
							total_guesses++;
							if (DoQuickSolve() ) {
								memcpy(all, org_all, 9*9*sizeof(unsigned));
								all[j][k] = last;
								//return 1;
							}else{
								memcpy(all, org_all, 9*9*sizeof(unsigned));
								all[j][k] = last;
							}
								
						}
					}
					return 0;
				}
			}
		}
	}else{
		if (NoOfSol >= 1000){
			CString str;
			str.Format("I've found %d solutions already\nI don't think even YOU have time to view all %d solutions", NoOfSol, NoOfSol);
			AfxMessageBox(str, MB_ICONEXCLAMATION);
			StopGuess = 1;
			return 0;
		}
		solutions[NoOfSol] = (unsigned int *) malloc(sizeof(unsigned)*9*9);
		if (solutions == NULL){
			AfxMessageBox("Not enough memory");
			return 0;
		}
		memcpy(solutions[NoOfSol], all, 9*9*sizeof(unsigned));
		NoOfSol++;
		return 1;
	}

	return 0;
}

void CDisplay::OnQuicksolve() 
{
	// TODO: Add your control notification handler code here
	unsigned i;
	CString str;
	float t;

	QuickSolve = 1;
	StopGuess = 0;
	total_guesses = 0;
	if (NoOfSol)
		for (i=0; i<NoOfSol; i++)
			if (solutions[i])
				free(solutions[i]);

	NoOfSol = 0;
	dur_time.Start();
	if (DoQuickSolve() == 0 && !NoOfSol){
		AfxMessageBox("Invalid puzzle, can not be solved");
	}
	dur_time.Stop();
	/*if (total_guesses > 1000){
		AfxMessageBox("Limiting number of guesses to 200");
	}*/

	QuickSolve = 0;
	if (NoOfSol > 1){
		memcpy(all, solutions[0], sizeof(unsigned)*9*9);
		dump_all();
		MultiSol dlg;

		dlg.NoOfSol = NoOfSol;
		dlg.solutions = solutions;

		dlg.DoModal();

	/*unsigned int **solutions, NoOfSol, CurrentSol;*/
	} else {
		t = dur_time.GetDuration()/(double)1000;
		str.Format("%f ms", t);
		m_Time.SetWindowText(str);
		memcpy(all, solutions[0], sizeof(unsigned)*9*9);
		dump_all();
	}

	
}

void CDisplay::setRTF(CRichEditCtrl *pCell, CString text) 
{

	// This is hard-coded for example purposes. It is likely this would
	// be read from file or another source.
	EDITSTREAM es;
	es.dwCookie = (DWORD)&text; // Pass a pointer to the CString to the callback function
	es.pfnCallback = MEditStreamInCallback; // Specify the pointer to the callback function

	pCell->StreamIn(SF_RTF,es); // Perform the streaming
}