以下是一個生成數(shù)獨的程序，利用深度優(yōu)先遍歷的方式。每次生成的數(shù)獨是隨機的。

對于判斷一個點是否正確擺放的函數(shù)IsRightPlace()，要注意幾個關(guān)鍵點。

//mySIZE是數(shù)獨棋盤的邊長，棋盤是mySIZE*mySIZE的大小
int mySIZE = 9;

void print(const vector<vector<int>> &num)
{
	for (int i = 0; i < mySIZE; i++)
	{
		for (int j = 0; j < mySIZE; j++)
		{
			cout << num[i][j] << " ";
		}
		cout << endl;
	}
}

bool IsRightPlace(vector<vector<int>> &num, int row, int col)
{
	int n = num[row][col];
	//注意i < row
	for (int i = 0; i < row; i++)
	{
		if (num[i][col] == n)
			return false;
	}
	//注意i < col
	for (int i = 0; i < col; i++)
	{
		if (num[row][i] == n)
			return false;
	}
	int row_start = row / 3;
	row_start *= 3;
	int row_end = row_start + 2;
	int col_start = col / 3;
	col_start *= 3;
	int col_end = col_start + 2;
	int i = row_start, j = col_start;
	//注意 k <= 8
	for (int k = 1; k <= 8; k++)
	{
		if (row != i || col != j)
		{
			if (num[i][j] == n)
				return false;
		}
		else
			break;
		if (j == col_end)
		{
			//注意j = col_start ！不要搞錯換行時列的起始點！
			j = col_start;
			i = i + 1;
		}
		else
		{
			j = j + 1;
		}
	}
	return true;
}

bool generate_core(vector<vector<int>> &num, int row, int col)
{
	
	vector<int> number;
	for (int i = 1; i <= 9; i++)
		number.emplace_back(i);
	while (!number.empty())
	{
		int randindex = rand() % number.size();
		int randnum = number[randindex];
		number.erase(number.begin() + randindex);
		num[row][col] = randnum;
		if (IsRightPlace(num, row, col) == false)
			continue;
		if (row == mySIZE - 1 && col == mySIZE-1)
		{
			return true;
		}
		int nextrow, nextcol;
		if (col == mySIZE-1)
		{
			nextrow=row + 1;
			nextcol = 0;
		}
		else
		{
			nextrow = row;
			nextcol = col + 1;
		}
		bool next = generate_core(num, nextrow, nextcol);
		if (next)
			return true;
	}
	if (number.empty())
	{
		num[row][col] = -5;
		return false;
	}		
}

void generate()
{
	vector<vector<int>> num(mySIZE, vector<int>(mySIZE, -1));
	srand((unsigned)time(NULL));
	if( generate_core(num, 0, 0) )
		print(num);
}

標(biāo)簽：

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請與原作者聯(lián)系。