題目說明：
請你判斷一個 9x9 的數獨是否有效，只需要 根據以下規則 ，驗證已經填入的數字是否有效即可，
規則：①數字 1-9 在每一行只能出現一次，②數字 1-9 在每一列只能出現一次，③數字 1-9 在每一個以粗實線分隔的 3x3 宮內只能出現一次，（請參考示例圖）
示例：
board = [["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
數獨部分空格內已填入了數字，空白格用 '.' 表示，
輸出：true
直接暴力破解：
數獨有九行九列，從頭依次邊歷各個元素，如果元素不是‘ . ’，則對陣列元素進行規則判斷，依次判斷其所在行是否含有重復元素、所在列是否含有重復元素、所在子數獨是否含有重復元素，如果含有重復元素則回傳false，否則回傳true，
其中還有一個難點就是找各個子數獨的下標，sx=（x/3）*3 開始的行下標；sy=（y/3）*3 開始的列下標，
代碼如下:
bool isValidSudoku(char** board, int boardSize, int* boardColSize){ int x,y,sx,sy,i,j; //x行，y列，sx子行，sy子列 for(x = 0;x < 9;x ++){ //依次遍歷陣列的每一個元素 for(y = 0;y < 9;y ++){ if(board[x][y] != '.'){ //元素不是‘.’，則對元素進行規則判斷 for(j = 0 ; j < 9 ; j ++){ if(j!=y){ if(board[x][j]==board[x][y]) //判斷x行有沒有相同元素 return false; } } for(i = 0 ; i < 9 ; i ++){ if(i != x){ if(board[i][y]==board[x][y]) //判斷y列有沒有相同元素 return false; } } sx=x/3*3; //子數獨的開始行 sy=y/3*3; //子數獨的開始列 for(i=0;i<3;i++){ for(j=0;j<3;j++){ if(sx+i!=x && sy+j!=y && board[sx+i][sy+j]==board[x][y])//不同行;不同列;同一個子數獨中不能有相同元素 return false; } } } } } return true; }
雖然暴力破解可以解決問題，也便于理解，該題也可通過哈希表列解決，在后續的更新會解決的，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/285756.html
標籤：其他
上一篇：C++標準模板庫(STL)——vector常見用法詳解
下一篇：LeetCode 1.兩數之和