資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++ 實現數獨驗證
假設我們得到一個 9×9 的矩陣，稱為數獨。任務是檢查給定的數獨圖案是否有效。
一般來說，數獨棋盤如下所示：
數獨規則 −
每一行包含一個 1-9 之間的數字
每一列包含 1-9 之間的數字。
每個 3×3 的塊包含唯一的數字。
特定行不能有相同的數字。
特定列不能有相同的數字。
例如
輸入-1 −
sudoku[]= [["3","5",".",".","2",".",".",".","."] ,["7",".",".","1","6","5",".",".","."] ,[".","9","8",".",".",".",".","6","."] ,["8",".",".",".","6",".",".",".","3"] ,["4",".",".","5",".","4",".",".","1"] ,["7",".",".",".","2",".",".",".","6"] ,[".","6",".",".",".",".","2","8","."] ,[".",".",".","4","1","9",".",".","5"] ,[".",".",".",".","8",".",".","7","9"]]
輸出 − True。
解釋 − 由於數獨矩陣中的所有數字都遵循有效數獨的模式，因此輸出為 True。
解決這個問題的方法
首先，我們將檢查給定的數獨棋盤是否包含具有唯一數字的列。然後，我們將檢查行。每個 3*3 的塊都包含所有唯一的數字。我們將檢查每個塊的行和列，如果它包含任何重複的數字，我們將返回 false，否則返回 true。
輸入數獨棋盤的二維陣列。
一個布林函式，用於檢查行中是否存在唯一元素。
一個布林函式，用於檢查列中是否存在唯一元素。
一個布林函式，用於檢查塊中是否存在唯一元素。
示例
#include<bits/stdc++.h>
using namespace std;
bool validSudoku(vector<vector<char>>& sudoku) {
int row = 0, col = 0, i = 0, block = 0;
int count[9];
for (row = 0; row < 9; ++row){
memset(count, 0, 9 * sizeof(int));
for (col = 0; col < 9; ++col){
if (sudoku[row][col] != '.')
++count[sudoku[row][col]-'1'];
}
for (i = 0; i < 9; ++i)
if (count[i] > 1)
return false;
}
for (col = 0; col < 9; ++col){
memset(count, 0, 9 * sizeof(int));
for (row = 0; row < 9; ++row){
if (sudoku[row][col] != '.')
++count[sudoku[row][col]-'1'];
}
for (i = 0; i < 9; ++i)
if (count[i] > 1)
return false;
}
int block_row = 0, block_col = 0;
for (block = 0; block < 9; ++block){
block_row = (block / 3) * 3, block_col = (block % 3) * 3;
memset(count, 0, 9 * sizeof(int));
for (row = block_row; row < (block_row + 3); ++row)
for (col = block_col; col < (block_col + 3); ++col)
if (sudoku[row][col] != '.')
++count[sudoku[row][col] - '1'];
for (i = 0; i < 9; ++i)
if (count[i] > 1)
return false;
}
return true;
}
int main(){
vector<vector<char> > sudoku= {
{'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'}
};
bool ans= validSudoku(sudoku);
if(ans){
cout<<"True"<<endl;
} else {
cout<<"false"<<endl;
}
return 0;
}輸出
True
更新於: 2021年2月5日
3K+ 次瀏覽
廣告