YEZAELP

SMMR-142: Sudoku [Extra Challenge]

Jun 7th, 2020
130
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.12 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define N 10
  4. using pii=pair<int,int>;
  5. int ar[N][N];
  6.  
  7. bool fill_line(int line,int num){
  8.     for(int j=1;j<=9;j++)
  9.         if(ar[line][j]==num) return false;
  10.     return true;
  11. }
  12. bool fill_col(int col,int num){
  13.     for(int i=1;i<=9;i++)
  14.         if(ar[i][col]==num) return false;
  15.     return true;
  16. }
  17. bool fill_square(int line,int col,int num){
  18.     if(1<=line&&line<=3) line=1;
  19.     else if(4<=line&&line<=6) line=4;
  20.     else line=7;
  21.     if(1<=col&&col<=3) col=1;
  22.     else if(4<=col&&col<=6) col=4;
  23.     else col=7;
  24.     for(int i=line;i<=line+2;i++){
  25.         for(int j=col;j<=col+2;j++){
  26.             if(ar[i][j]==num) return false;
  27.         }
  28.     }
  29.     return true;
  30. }
  31.  
  32. pii find_zero(int ar[N][N]){
  33.     for(int i=1;i<=9;i++){
  34.         for(int j=1;j<=9;j++){
  35.             if(ar[i][j]==0)
  36.             return {i,j};
  37.         }
  38.     }
  39.     return {-1,-1};
  40. }
  41.  
  42. bool sudoku(int ar[N][N]){
  43.  
  44.     int line,col;
  45.     line=find_zero(ar).first;
  46.     col=find_zero(ar).second;
  47.     if(line==-1&&col==-1) return true;
  48.  
  49.     for(int num=1;num<=9;num++){
  50.         if( fill_line(line,num) && fill_col(col,num) && fill_square(line,col,num) ){
  51.             ar[line][col]=num;
  52.             if( sudoku(ar) ) return true;
  53.             ar[line][col]=0;
  54.         }
  55.     }
  56.  
  57.     return false;
  58. }
  59.  
  60. int main(){
  61.  
  62.     FILE *read,*write;
  63.     read=fopen("input_sudoku.txt","r");
  64.     write=fopen("sudoku_ans.txt","w");
  65.     string  str[10];
  66.     int t=0;
  67.     while(fscanf(read,"%[^\n]s",str)!=EOF){
  68.  
  69.         for(int i=1;i<=9;i++){
  70.             for(int j=1;j<=9;j++){
  71.                 fscanf(read,"%d",&ar[i][j]);
  72.             }
  73.         }
  74.  
  75.         sudoku(ar);
  76.         fprintf(write,"%s\n",str);
  77.         for(int i=1;i<=9;i++){
  78.             for(int j=1;j<=9;j++){
  79.                 fprintf(write,"%d ",ar[i][j]);
  80.             }
  81.             fprintf(write,"\n");
  82.         }
  83.  
  84.         fscanf(read,"%[^\n]s",str);
  85.         for(int i=1;i<=9;i++){
  86.             for(int j=1;j<=9;j++){
  87.                 fscanf(read,"%d",&ar[i][j]);
  88.             }
  89.         }
  90.     }
  91.     fclose(read);
  92.     fclose(write);
  93.     return 0;
  94. }
Add Comment
Please, Sign In to add comment