Etibarlı Sudoku

Etibarlı Sudoku birdir problem içərisində 9 * 9 Sudoku lövhəsi verdik. Verilən Sudoku-nun etibarlı olub olmadığını və bunun əsasında olmadığını tapmaq lazımdır aşağıdakı qaydalar:

1. Hər sətirdə rəqəm olmalıdır 1-9 təkrar olmadan.
2. Hər sütunda rəqəmlər olmalıdır 1-9 təkrar olmadan.
3. 9-un hər biri 3x3 şəbəkənin alt qutularında rəqəmlər olmalıdır 1-9 təkrar olmadan.

Pin

Boş xanalar '' ilə doldurulur. giriş formatında.

Giriş Formatı

9 sətir s olan hər sətrin olduğu 9 sətirdən giriş alın.

Çıxış formatı

Qismən doldurulmuş sudoku etibarlıdırsa “YES” yazdırın, əks halda “YOX” yazdırın.

Məhdudiyyətlər

• s [i] = ”.” və ya 1 <= s [i] <= 9.

Example Input:
8.6..3.9.
.4..1..68
2..87...5
1.8..5.2.
.3.1...5.
7.5.3.9..
.21..7.4.
6...2.8..
.876.4..3

Example Output:
YES

Izahat 

Bir sıra, sütun və ya 3 * 3 torda təkrarlanan hər hansı bir dəyərin olub olmadığını yoxlayın. Hazırlıq tapdığımız təqdirdə YOX yazmaz YES.

Alqoritm

Algorithm: 
Step:1 For each row check that their is repeatation of any digit present in filled cells.
Step:2 For each column check that their is repeatation of any digit present in filled cells.
Step:3 Check that every 3*3 grid must contain different values means no repeatation of any digit present in filled cells.
Step:4 Print "YES" if no repeatation of digit is found else print "NO".

Valid Sudoku üçün tətbiqetmə

/*C++ Implementation of Valid Sudoku problem*/ 
#include<bits/stdc++.h>
using namespace std;
int main() 
{ 
    /*input suduko*/
    vector<string> v(10);
    for(int i=0;i<9;i++)
    {
        cin>>v[i];
    }
    /*use for store the count of digit 1-9*/
    int freq[10]={0};
    int flag=0;
    /*For each row check that their is repeatation of any digit present in filled cells.*/
    for(int i=0;i<9;i++)
    {
        for(int j=0;j<9;j++)
        {
            /*for filled cells only*/
           if(v[i][j]!='.')
           {
               freq[v[i][j]-'0']++;
               /*if count is repeated*/
               if(freq[v[i][j]-'0']>1)
               {
                   flag=1;
                   goto label;
               }
           }
        }
        /*set all values to 0 for next time use*/
        memset(freq,0,sizeof(freq));
    }
    /*For each  chcolumneck that their is repeatation of any digit present in filled cells.*/
    for(int j=0;j<9;j++)
    {
        for(int i=0;i<9;i++)
        {
            /*for filled cells only*/
            if(v[i][j]!='.')
            {
               freq[v[i][j]-'0']++;
               /*if count is repeated*/
               if(freq[v[i][j]-'0']>1)
               {
                   flag=1;
                   goto label;
               }
            }
        }
        /*set all values to 0 for next time use*/
        memset(freq,0,sizeof(freq));
    }
    /*Check that every 3*3 grid must contain different values means no repeatation of any digit present in filled cells.*/
    for(int k1=0;k1<3;k1++)
    {
        for(int k2=0;k2<3;k2++)
        {
            for(int i=k1*3;i<k1*3+3;i++)
            {
                for(int j=k2*3;j<k2*3+3;j++)
                {
                    /*for filled cells only*/
                    if(v[i][j]!='.')
                    {
                        freq[v[i][j]-'0']++;
                        /*if count is repeated*/
                        if(freq[v[i][j]-'0']>1)
                        {
                            flag=1;
                            goto label;
                        }
                    }
                }
            } 
            /*set all values to 0 for next time use*/
            memset(freq,0,sizeof(freq));    
        }
    }
    label:;
    /*print "YES" if flag is 0 then sudoku is valid else "NO" valid*/
    if(flag==1)
    {
        cout<<"NO"<<endl;
    }
    else
    {
        cout<<"YES"<<endl;
    }    
    return 0; 
}

Input-1:
....5..1.
.4.3.....
.....3..1
8......2.
..2.7....
.15......
.....2...
.2.9.....
..4......

Output-1:
NO

Input-2:
53..7....
6..195...
.98....6.
8...6...3
4..8.3..1
7...2...6
.6....28.
...419..5
....8..79

Output-2:
YES

Zamanın mürəkkəbliyi

O (9 * 9) Burada sudokunun hər hüceyrəsini 3 dəfə ziyarət edirik və hüceyrələrin ümumi sayı 9 * 9-dur, bu zaman zaman mürəkkəbliyi sabitdir.

Kosmik Mürəkkəblik

O (9 * 9) 9 uzunluqlu 9 ipdən istifadə edirik, buna görə burada 9 * 9 boşluğa ehtiyacımız var. Hesablama olaraq giriş üçün yer əlavə etmiriksə, zaman mürəkkəbliyinin sabit olduğu deyirik O (1). Sadəcə giriş dəyərlərini keçərək tətbiq olunmalıdır ki, bu da əlavə bir boşluq yaradılmır və istifadə olunmur.

References