北京理工大学2019软件工程个人项目-数独-All_in_one

    		TEST_METHOD(testGenerateSudoku)
    		{
    			std::string outFile = "./Sudoku.txt";
    			std::string num[10] = { "-10","-1", "0", "1", "10", "100",
    									"1000","10000", "100000", "1000000" };
    			for (int i = 0; i < 10; i++)
    			{
    				try{
    					SudokuGenerator g(outFile.c_str(), num[i]);
    					g.GenerateSudoku();
    				}
    				catch(std::invalid_argument e)
    				{
    					if (i >= 3)
    						Assert::Fail();
    				}
    				catch(std::exception e)
    				{
    					Assert::Fail();
    				}
    				Assert::IsTrue(this->SudokuLegal(outFile));
    			}

    		TEST_METHOD(testSolveSudoku)
    		{
    			std::string inFile = "./Sudoku.txt";
    			std::string outFile[10] = {"", ".", "emptyFile","./Sudoku1.txt", "./Sudoku10.txt",
    										"./Sudoku100.txt","./Sudoku1000.txt","./Sudoku10000.txt",
    										"./Sudoku100000.txt", "./Sudoku1000000.txt"};
    			for(int times = 0; times < 4; times++)
    				for (int i = 0; i < 10; i++)
    				{
    					try {
    						SudokuSolver g(inFile.c_str(), outFile[i]);
    						g.SolveSudoku();
    					}
    					catch (std::invalid_argument e)
    					{
    						if (i >= 3)
    							Assert::Fail();
    					}
    					catch (std::exception e)
    					{
    						Assert::Fail();
    					}
    					Assert::IsTrue(this->SolutionLegal(inFile, outFile[i]));
    				}
    
    		}

    void SudokuGenerator::GenerateSudoku()
    {
    	const int basicSudokuNumber = this->sudokuNum / 72 + 1;
    	this->GenerateBaseSudoku(basicSudokuNumber);
    	this->PrintSudoku();
    }

      int n = 0;

    	do
    	{
    		sudoku[n].SetRow(this->firstRow, 0);
    		sudoku[n].ConstructFromFirstRow();
    		n++;
    	} while (n < num && std::next_permutation(this->firstRow + 1, this->firstRow + 9));

    void Sudoku::SetRow(const int row[9], int row_num)

    {
    	memcpy(this->data[row_num], row, sizeof(int) * 9);
    }
    
    void Sudoku::ConstructFromFirstRow()
    {
    	int f[10] = { 0,3,6,1,4,7,2,5,8 };
    	for(int i = 1; i < 9; i++)
    	{
    		for(int j = 0; j < 9; j++)
    		{
    			this->data[i][j] = data[0][(j - f[i] + 9) % 9];
    		}
    	}
    }

    void SudokuGenerator::PrintSudoku() const

    {
    	const int basicSudokuNumber = this->sudokuNum / 72 + 1;
    	const int restSudokuNumber = this->sudokuNum % 72;
    	if (restSudokuNumber == 0)
    	{
    		for (int i = 0; i < basicSudokuNumber - 2; i++)
    		{
    			this->sudoku[i].PrintExpandedSudoku(this->outputFile, -1);
    		}
    		this->sudoku[basicSudokuNumber - 2].PrintExpandedSudoku(this->outputFile, 71);
    		fprintf(this->outputFile, "\n\n");
    		this->sudoku[basicSudokuNumber - 1].PrintExpandedSudoku(this->outputFile, 1);
    	}
    	else
    	{
    		for (int i = 0; i < basicSudokuNumber - 1; i++)
    		{
    			this->sudoku[i].PrintExpandedSudoku(this->outputFile, -1);
    		}
    		this->sudoku[basicSudokuNumber - 1].PrintExpandedSudoku(this->outputFile, restSudokuNumber);
    	}
    }

    void Sudoku::PrintExpandedSudoku(FILE* fp, int maxSudokuPrinted) const

    {
    	char row[9][19];
    	memset(row, 0, sizeof(row));
    	for (int i = 0; i < 9; i++)
    	{
    		for (int j = 0; j < 9; j++)
    		{
    			row[i][j<<1] = '0' + this->data[i][j];
    			row[i][(j << 1) + 1] = ' ';
    		}
    		row[i][17] = 0;
    	}
    	int outputOrder[9];
    	memset(outputOrder, 0, sizeof(outputOrder));
    
    	int firstBlock[2][3] = { {0,1,2},{0,2,1} };
    	int secondBlock[6][3] = { {3,4,5},{3,5,4},{4,3,5},{4,5,3},{5,3,4},{5,4,3} };
    	int thirdBlock[6][3] = { {6,7,8},{6,8,7},{7,6,8},{7,8,6},{8,6,7},{8,7,6} };
    	for (int firstBlockOrder = 0; firstBlockOrder < 2; firstBlockOrder++)
    	{
    		for (int secondBlockOrder = 0; secondBlockOrder < 6; secondBlockOrder++)
    		{
    			for (int thirdBlockOrder = 0; thirdBlockOrder < 6; thirdBlockOrder++)
    			{
    				if (maxSudokuPrinted == 0)
    					return;
    				else
    					maxSudokuPrinted--;
    				fprintf(fp, "%s\n", row[firstBlock[firstBlockOrder][0]]);
    				fprintf(fp, "%s\n", row[firstBlock[firstBlockOrder][1]]);
    				fprintf(fp, "%s\n", row[firstBlock[firstBlockOrder][2]]);
    				
    				fprintf(fp, "%s\n", row[secondBlock[secondBlockOrder][0]]);
    				fprintf(fp, "%s\n", row[secondBlock[secondBlockOrder][1]]);
    				fprintf(fp, "%s\n", row[secondBlock[secondBlockOrder][2]]);
    				
    				fprintf(fp, "%s\n", row[thirdBlock[thirdBlockOrder][0]]);
    				fprintf(fp, "%s\n", row[thirdBlock[thirdBlockOrder][1]]);
    				fprintf(fp, "%s", row[thirdBlock[thirdBlockOrder][2]]);
    
    				if (maxSudokuPrinted != 0)
    				{
    					fprintf(fp, "\n\n");
    				}
    				else
    				{
    					return;
    				}
    			}
    		}
    	}
    }

    void SudokuSolver::SolveSudoku()
    {
    	bool firstSolution = true;
    	bool lastSolution = false;
    	while (true)
    	{
    		char cdata[9][20];
    		memset(cdata, 0, sizeof(cdata));
    		memset(this->isEmpty, 0, sizeof(isEmpty));
    		memset(this->sudoku, 0, sizeof(this->sudoku));
    		memset(this->constraint, 0, sizeof(this->constraint));
    		for(int i = 0; i < 9; i++)
    		{
    			const size_t res = fread_s(cdata[i], (size_t)20, sizeof(char), (size_t)18, this->inputFile);
    			if (res == 0)
    			{
    				lastSolution = true;
    				break;
    			}
    		}
    		if (lastSolution)
    			break;
    		if (!firstSolution)
    			fprintf(this->outputFile, "\n\n");
    		else
    			firstSolution = false;
    		found = false;
    		
    		for (int i = 0; i < 9; i++)
    			for (int j = 0; j < 9; j++)
    			{
    				sudoku[i][j] = cdata[i][j<<1] - '0' - 1;
    				isEmpty[i][j] = (sudoku[i][j] == -1);
    				if (!isEmpty[i][j]) updateConstraint(i, j, 1);
    			}
    		this->backtracing(0, 0);
    		fread_s(cdata, 20, sizeof(char), 1, this->inputFile);
    	}
    }

    void SudokuSolver::backtracing(int x, int y)
    {
    	if (found)
    		return;
    	if (y == 9)
    	{
    		x++;
    		y = 0;
    	}
    	while (x <= 8 && !isEmpty[x][y])
    	{
    		y++;
    		if (y == 9)
    		{
    			x++;
    			y = 0;
    		}
    	}
    	if (x > 8)
    	{
    		found = true;
    		for (int i = 0; i < 9; i++)
    			for (int j = 0; j < 9; j++)
    				sudoku[i][j]++;
    		Sudoku(sudoku).PrintToFile(this->outputFile);
    		return;
    	}
    	while (~(sudoku[x][y] = nextVal(x, y, sudoku[x][y] + 1)))
    	{
    		updateConstraint(x, y, true);
    		backtracing(x, y + 1);
    		updateConstraint(x, y, false);
    	}
    }