題干：
https://leetcode.cn/problems/sudoku-solver/

創(chuàng)新互聯(lián)公司是一家專業(yè)提供荷塘企業(yè)網(wǎng)站建設(shè),專注與成都網(wǎng)站建設(shè)、網(wǎng)站設(shè)計(jì)、HTML5、小程序制作等業(yè)務(wù)。10年已為荷塘眾多企業(yè)、政府機(jī)構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)網(wǎng)站制作公司優(yōu)惠進(jìn)行中。

• 使用“有效的數(shù)獨(dú)”中的函數(shù)，代碼如下：

class Solution {private:
    bool answer{false };//用來(lái)遞歸時(shí)，判斷是否找到了答案

public:
	//自己寫的檢驗(yàn)數(shù)獨(dú)合法的代碼效率似乎有點(diǎn)低，頻繁調(diào)用影響有點(diǎn)大
	//isValidSudoku(),這是借用官方的代碼
    bool isValidSudoku(vector>& board) {int rows[9][9];
        int columns[9][9];
        int subboxes[3][3][9];

        memset(rows, 0, sizeof(rows));
        memset(columns, 0, sizeof(columns));
        memset(subboxes, 0, sizeof(subboxes));
        for (int i = 0; i< 9; i++) {for (int j = 0; j< 9; j++) {char c = board[i][j];
                if (c != '.') {int index = c - '0' - 1;
                    rows[i][index]++;
                    columns[j][index]++;
                    subboxes[i / 3][j / 3][index]++;
                    if (rows[i][index] >1 || columns[j][index] >1 || subboxes[i / 3][j / 3][index] >1) {return false;
                    }
                }
            }
        }
        return true;
    }

	//解數(shù)獨(dú)的函數(shù)
    void solveSudoku(vector>& board) {backTracking(0, 0, board);
    }

	//遞歸的函數(shù)
    //對(duì) board[row][col] 位置，插入數(shù)字(參數(shù)的解釋)
    void backTracking(int row,int col,vector>& board) {while (row != 9 && board[row][col] != '.') {row = row + (col + 1) / 9;
            col = (col + 1) % 9;
        }//找空格（如果遞歸完了，row可能會(huì) == 9，所以退出遞歸的條件放在后面）

        if (row == 9) {answer = true;
            return;
        }//找到了答案,退出遞歸的條件
        
		for (char i = '1'; i<= '9'; i++)//對(duì) board[row][col] 位置，填入數(shù)字
		{	board[row][col] = i;
			if (isValidSudoku(board)) {		backTracking(row + (col + 1) / 9, (col + 1) % 9, board);//填入i合法，遞歸轉(zhuǎn)向下一格
            }
            else {continue;
            }	
            //重點(diǎn)：回溯
            if (answer) return;//如果歸來(lái)時(shí)已經(jīng)找到了答案，就不用繼續(xù)遞歸尋找答案（不能放在for頭部，否則 i==9 歸來(lái)時(shí)如果已經(jīng)找到了答案，如果不在這里return，退出循環(huán)了會(huì)被置為空格）
		}
        //重點(diǎn)：回溯
        board[row][col] = '.';//9歸來(lái)時(shí)都沒(méi)有找到答案，說(shuō)明這個(gè)節(jié)點(diǎn)的1-9都不行，恢復(fù)為空，返回上一格
        return;
    }
};

• 上面的代碼效率其實(shí)不算太高，原因在于每一次填入數(shù)字時(shí)都調(diào)用了 isValidSudoku() 函數(shù)判斷是否合法。這導(dǎo)致了兩個(gè)缺點(diǎn)：1、頻繁調(diào)用該函數(shù)，對(duì) isValidSudoku() 函數(shù)的效率比較敏感；2、在某個(gè)位置填入數(shù)字后，沒(méi)有必要檢驗(yàn)整個(gè)數(shù)獨(dú)，只需要檢驗(yàn)該位置所在行、列、和九宮格。代碼如下：

class Solution {private:
	bool answer{false };//用來(lái)遞歸時(shí)，判斷是否找到了答案

public:
	//判斷是否滿足數(shù)獨(dú)條件
	bool isvalid(int row, int col, vector>& board) {unordered_sethashSet_row{};//判斷行的哈希表
		unordered_sethashSet_col{};//判斷列的哈希表
		unordered_sethashSet_box{};//判斷九宮格的哈希表

		for (int i = 0; i< board.size(); i++) {	if (board[row][i] != '.') {		if (hashSet_row.find(board[row][i]) == hashSet_row.end()) //判斷行符合
				{hashSet_row.insert(board[row][i]);
				}
				else {return false; }
			}
			
			if (board[i][col] != '.') {		if (hashSet_col.find(board[i][col]) == hashSet_col.end()) //判斷列符合
				{hashSet_col.insert(board[i][col]);
				}
				else {return false; }
			}
		}
		//判斷九宮格符合
		//(row/3)*3,(col/3)*3是所在九宮格的起始位置
		int rowStart = (row / 3) * 3;
		int colStart = (col / 3) * 3;

		for (int i = 0; i< 3; i++) {	for (int j = 0; j< 3; j++) {		if (board[rowStart + i][colStart + j] != '.') {if (hashSet_box.find(board[rowStart + i][colStart + j]) == hashSet_box.end()) {hashSet_box.insert(board[rowStart + i][colStart + j]);
					}
					else {return false; }
				}			
			}
		}

		//經(jīng)過(guò)了考驗(yàn)
		return true;
	}



	void solveSudoku(vector>& board) {backTracking(0, 0, board);
	}

	//對(duì) board[row][col] 位置，插入數(shù)字
	void backTracking(int row, int col, vector>& board) {while (row != 9 && board[row][col] != '.') {	row = row + (col + 1) / 9;
			col = (col + 1) % 9;
		}//找到空格

		if (row == 9) {	answer = true;
			return;
		}//找到了答案,退出遞歸的條件

		for (char i = '1'; i<= '9'; i++)//填入數(shù)字,合法就轉(zhuǎn)向下一格
		{	board[row][col] = i;
			if (isvalid(row, col, board)) {		backTracking(row + (col + 1) / 9, (col + 1) % 9, board);
			}
			else {		continue;
			}
			//重點(diǎn)：回溯
			if (answer) return;//如果歸來(lái)時(shí)已經(jīng)找到了答案，就不用繼續(xù)遞歸尋找答案（不能放在for頭部，否則9歸來(lái)時(shí)如果已經(jīng)找到了答案，退出循環(huán)會(huì)被置為空格）
		}
		//重點(diǎn)：回溯
		board[row][col] = '.';//9歸來(lái)時(shí)都沒(méi)有找到答案，說(shuō)明這個(gè)節(jié)點(diǎn)的1-9都不行，恢復(fù)為空，返回上一格
		return;
	}
};

• 似乎使用了哈希表 unordered_set ，效率會(huì)降低。真是難受啊。對(duì)于判斷數(shù)獨(dú)是否符合條件，還是用數(shù)組吧…

class Solution {private:
	bool answer{false };//用來(lái)遞歸時(shí)，判斷是否找到了答案

public:
	//判斷填入數(shù)字后數(shù)獨(dú)是否合法（默認(rèn)初始數(shù)獨(dú)合法）
	bool isvalid(int row, int col, vector>& board) {//數(shù)組模擬哈希表
		char arrRow[10]{0 };//判斷行的數(shù)組,arrRow[k] 保存 字符'k'出現(xiàn)的次數(shù)
		char arrCol[10]{0 };//判斷列的數(shù)組,arrCol[k] 保存 字符'k'出現(xiàn)的次數(shù)
		char arrBox[10]{0 };//判斷行的數(shù)組,arrBox[k] 保存 字符'k'出現(xiàn)的次數(shù)

		for (int i = 0; i< board.size(); i++) {	//判斷行符合
			if (board[row][i] != '.') {		int index = board[row][i] - '0';//index 對(duì)于字符 board[row][i] 在數(shù)組中的下標(biāo)
				if (arrRow[index] == 0) {arrRow[index] = 1;
				}
				else {return false; }
			}
			//判斷列符合
			if (board[i][col] != '.') {		int index = board[i][col] - '0';//index 對(duì)于字符 board[i][col] 在數(shù)組中的下標(biāo)
				if (arrCol[index] == 0) {arrCol[index] = 1;
				}
				else {return false; }
			}
		}
		//判斷九宮格符合
		//(row/3)*3,(col/3)*3是所在九宮格的起始位置
		int rowStart = (row / 3) * 3;
		int colStart = (col / 3) * 3;

		for (int i = 0; i< 3; i++) {	for (int j = 0; j< 3; j++) {		if (board[rowStart + i][colStart + j] != '.') {int index = board[rowStart + i][colStart + j] - '0';//index 對(duì)于字符 board[rowStart + i][colStart + j] 在數(shù)組中的下標(biāo)
					if (arrBox[index] == 0) {arrBox[index] = 1;
					}
					else {return false; }
				}
			}
		}

		//經(jīng)過(guò)了考驗(yàn)
		return true;
	}



	void solveSudoku(vector>& board) {backTracking(0, 0, board);
	}

	//對(duì) board[row][col] 位置，插入數(shù)字
	void backTracking(int row, int col, vector>& board) {while (row != 9 && board[row][col] != '.') {	row = row + (col + 1) / 9;
			col = (col + 1) % 9;
		}//找到空格，最后row可能出界了，所以遞歸退出條件放在下面

		if (row == 9) {	answer = true;
			return;
		}//找到了答案,退出遞歸的條件

		for (char i = '1'; i<= '9'; i++)//填入數(shù)字,合法就轉(zhuǎn)向下一格
		{	board[row][col] = i;
			if (isvalid(row, col, board)) {		backTracking(row + (col + 1) / 9, (col + 1) % 9, board);
			}
			else {continue;}
			//重點(diǎn)：回溯
			if (answer) return;//如果歸來(lái)時(shí)已經(jīng)找到了答案，就不用繼續(xù)遞歸尋找答案（不能放在for頭部，否則9歸來(lái)時(shí)如果已經(jīng)找到了答案，退出循環(huán)會(huì)被置為空格）
		}
		//重點(diǎn)：回溯
		board[row][col] = '.';//9歸來(lái)時(shí)都沒(méi)有找到答案，說(shuō)明這個(gè)節(jié)點(diǎn)的1-9都不行，恢復(fù)為空，返回上一格
		return;
	}
};

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站欄目：37.解數(shù)獨(dú)（C++）-創(chuàng)新互聯(lián)
網(wǎng)頁(yè)地址：http://www.rwnh.cn/article16/ccisdg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供電子商務(wù)、移動(dòng)網(wǎng)站建設(shè)、小程序開(kāi)發(fā)、網(wǎng)站排名、App開(kāi)發(fā)、服務(wù)器托管

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)