daily pastebin goal
92%
SHARE
TWEET

Untitled

hwanil Jan 12th, 2018 57 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<stdio.h>
  2. #include<vector>
  3. using namespace std;
  4. int map[9][9];
  5. vector<pair<int, int> > empt;
  6.  
  7. bool isOkay(int y, int x,int num) {
  8.     for (int i = 0; i < 9; i++) {
  9.         if (map[y][i] == num)return false;
  10.         if (map[i][x] == num)return false;
  11.     }
  12.  
  13.     int yy = (y / 3) * 3;
  14.     int xx = (x / 3) * 3;
  15.  
  16.     for (int i = yy; i <= yy + 2; i++) {
  17.         for (int j = xx; j <= xx + 2; j++) {
  18.             if (map[i][j] == num)return false;
  19.         }
  20.     }
  21.  
  22.     return true;
  23. }
  24.  
  25. bool dfs(int idx) {
  26.     if (idx == empt.size()) {
  27.         for (int i = 0; i < 9; i++) {
  28.             for (int j = 0; j < 9; j++) {
  29.                 printf("%d ",map[i][j]);
  30.             }
  31.             printf("\n");
  32.         }
  33.  
  34.         return true;
  35.     }
  36.  
  37.     int nowY = empt[idx].first;
  38.     int nowX = empt[idx].second;
  39.  
  40.     for (int i = 1; i <= 9; i++) {
  41.         if (isOkay(nowY, nowX, i)) {
  42.             map[nowY][nowX] = i;
  43.             if(dfs(idx + 1))
  44.                 return true;
  45.             map[nowY][nowX] = 0;
  46.  
  47.         }
  48.     }
  49. }
  50. int main() {
  51.  
  52.     for (int i = 0; i < 9; i++) {
  53.         for (int j = 0; j < 9; j++) {
  54.             scanf("%d",&map[i][j]);
  55.             if (map[i][j] == 0) {
  56.                 empt.push_back({ i,j });
  57.             }
  58.         }
  59.     }
  60.  
  61.     dfs(0);
  62.     return 0;
  63. }
RAW Paste Data
Top