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

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

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

class Solution {private:
    bool answer{false };//用來遞歸時，判斷是否找到了答案

public:
	//自己寫的檢驗數(shù)獨合法的代碼效率似乎有點低，頻繁調用影響有點大
	//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ù)獨的函數(shù)
    void solveSudoku(vector>& board) {backTracking(0, 0, board);
    }

	//遞歸的函數(shù)
    //對 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可能會 == 9，所以退出遞歸的條件放在后面）

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

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

class Solution {private:
	bool answer{false };//用來遞歸時，判斷是否找到了答案

public:
	//判斷是否滿足數(shù)獨條件
	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)過了考驗
		return true;
	}



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

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

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

class Solution {private:
	bool answer{false };//用來遞歸時，判斷是否找到了答案

public:
	//判斷填入數(shù)字后數(shù)獨是否合法（默認初始數(shù)獨合法）
	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 對于字符 board[row][i] 在數(shù)組中的下標
				if (arrRow[index] == 0) {arrRow[index] = 1;
				}
				else {return false; }
			}
			//判斷列符合
			if (board[i][col] != '.') {		int index = board[i][col] - '0';//index 對于字符 board[i][col] 在數(shù)組中的下標
				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 對于字符 board[rowStart + i][colStart + j] 在數(shù)組中的下標
					if (arrBox[index] == 0) {arrBox[index] = 1;
					}
					else {return false; }
				}
			}
		}

		//經(jīng)過了考驗
		return true;
	}



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

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

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

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

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

廣告

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