a016 - Sudoku Validator
題目描述
題目要求判斷一個 9x9 的數獨盤面是否合法。合法數獨的定義是：每一行、每一列、以及每一個 3x3 的子方塊都包含數字 1 到 9，且不重複。
解題思路
程式碼首先讀取 9x9 的數獨盤面。然後，它分別檢查每一行、每一列、以及每一個 3x3 的子方塊是否符合數獨的規則。
檢查的方法是將每一行、每一列、以及每一個 3x3 的子方塊的數字放入一個陣列中，然後對該陣列進行排序。排序後，如果陣列中的數字不是 1 到 9 的順序，則表示該行、該列或該子方塊不合法，輸出 "no"。如果所有行、列和子方塊都合法，則輸出 "yes"。
check 函數用於判斷一個陣列是否包含 1 到 9 的所有數字且不重複。它將輸入陣列排序後，與一個包含 1 到 9 的排序陣列進行比較。如果存在差異，則返回 1，否則返回 0。
複雜度分析
- 時間複雜度: O(n^3 * log n)，其中 n 是數獨盤面的大小 (9)。主要的時間消耗在排序操作上，每一行、每一列和每一個 3x3 的子方塊都需要排序，總共有 9 + 9 + 9 = 27 個需要排序的陣列，每個陣列的大小為 9，因此排序的總時間複雜度為 27 * 9 * log 9，簡化為 O(n^3 * log n)。
- 空間複雜度: O(n)，其中 n 是數獨盤面的大小 (9)。程式碼使用了一個大小為 9 的
load陣列來儲存每一行、每一列或每一個 3x3 子方塊的數字。
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
int check(int x[]){
int g=0;
int checker[9]={1,2,3,4,5,6,7,8,9};
sort(x,x+9);
for(int i=0;i<9;i++){
if(x[i]!=checker[i]){
g++;
break;
}
}
return g;
}
int main() {
int a[9][9],load[9],t;
while(cin>>a[0][0]){
int p=0;
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
if(i==0&&j==0);
else cin >> a[i][j];
}
}
for(int i=0;i<9;i++){
for(int t=0;t<2;t++){
for(int j=0;j<9;j++){
if(t==0){
load[j]=a[i][j];
}
else if(t==1){
load[j]=a[j][i];
}
}
if(check(load)){
cout << "no" << endl;
p++;
}
if(p!=0)break;
}
if(p!=0)break;
}
for(int m=0;m<=6;m+=3){
for(int n=0;n<=6;n+=3){
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
load[(i*3)+j]=a[m+i][n+j];
}
}
if(check(load)){
cout << "no" << endl;
p++;
}
if(p!=0)break;
}
if(p!=0)break;
}
if(p==0) cout << "yes" << endl;
}
return 0;
}