pastebin

pastebin

Paste Search Dynamic
Recent pastes
sudoku
  1. #include <bits/stdc++.h>
  2. #include <sys/types.h>
  3. #include <sys/time.h>
  4. #include <sys/socket.h>
  5. #include <sys/un.h>
  6. #include <netinet/in.h>
  7. #include <arpa/inet.h>
  8. #include <unistd.h>
  9. #include <stdlib.h>
  10. #include <cstring>
  11. #include <unistd.h>
  12. #include <signal.h>
  13. #include <filesystem>
  14. #include <dirent.h>
  15. #define X first
  16. #define Y second
  17.  
  18. using namespace std;
  19. using pii = pair<int, int>;
  20.  
  21. int sudoku[15][15]; // 9 * 9
  22. char buf[1000000];
  23. queue <pii> q;
  24. vector <pii> lists;
  25.  
  26. bool inside(int i, int j){
  27.     if(i >= 0 && i < 9 && j >= 0 && j < 9) return true;
  28.     return false;
  29. }
  30.  
  31. bool checker(int x, int y,  int num){
  32.     for(int i = 0; i < 9; i++){
  33.         if(x == i || sudoku[i][y] == 0) continue;
  34.         if(sudoku[i][y] == num) return false;
  35.     }
  36.     for(int j = 0; j < 9; j++){
  37.         if(y == j || sudoku[x][j] == 0) continue;
  38.         if(sudoku[x][j] == num) return false;
  39.     }
  40.     for(int i = x - 1; i <= x + 1; i++){
  41.         for(int j = y - 1; j <= y + 1; j++){
  42.             if((i == x && j == y) || !inside(i, j) || sudoku[i][j] == 0) continue;
  43.             if(sudoku[i][j] == num) return false;
  44.         }
  45.     }
  46.     return true;
  47. }
  48.  
  49. int solve(int idx){
  50.     if(idx == lists.size()) return 1;
  51.     printf("cur idx = %d, (%d, %d)n", idx, lists[idx].X, lists[idx].Y);
  52.     for(int i = 0; i < 9; i++){
  53.         for(int j = 0; j < 9; j++) cout << sudoku[i][j] << " "; cout << endl;
  54.     }
  55.     cout << "----------------------------n";
  56.     for(int i = 1; i <= 9; i++){
  57.         if(checker(lists[idx].X, lists[idx].Y, i)){
  58.             sudoku[lists[idx].X][lists[idx].Y] = i;
  59.             if(solve(idx + 1)) return 1;
  60.             sudoku[lists[idx].X][lists[idx].Y] = 0;
  61.         }
  62.     }
  63.     return 0;
  64. }
  65.  
  66. int main(int argc, char **argv)
  67. {
  68.        
  69.  
  70.     bzero(buf, sizeof(buf));
  71.     scanf("%s", buf);
  72.     printf("buf = %sn", buf);
  73.     cout << "str len = " << strlen(buf) << endl;
  74.     // filling with value 9
  75.     int p = 0;
  76.     while(buf[p] != '.' && (buf[p] - '0' > 9 || buf[p] - '0' < 0)) p++;
  77.     for(int i = 0; i < 9; i++){
  78.         for(int j = 0; j < 9; j++) {
  79.             if(buf[p] != '.') sudoku[i][j] = buf[p] - '0';
  80.             else sudoku[i][j] = 0, lists.emplace_back(i, j);
  81.             p++;
  82.         }
  83.     }
  84.     //cout << "debugn";
  85.    
  86.     cout << "ans = " <<solve(0) << "n";
  87.         for(int i = 0; i < 9; i++){
  88.             for(int j = 0; j < 9; j++) printf("%d ", sudoku[i][j]); printf("n");
  89.         }
  90.  
  91.         return 0;
  92. }
  93.  
  94.  
Parsed in 0.043 seconds