fork(2) download
copy 
  1. #include <string>
  2. #include <iostream>
  3.  
  4. using namespace std;
  5.  
  6. const int SIZE = 9;
  7. const int BLOCK_SIZE = 3;
  8.  
  9. int constr_vert[SIZE][SIZE];
  10. int constr_hor[SIZE][SIZE];
  11.  
  12. int field[SIZE][SIZE];
  13. int free_hor[SIZE];
  14. int free_vert[SIZE];
  15. int free_block[SIZE / BLOCK_SIZE][SIZE / BLOCK_SIZE];
  16.  
  17. bool consistentPair(int x, int y, int sign) {
  18.   if (y < x) return sign <= 0;
  19.   if (x < y) return sign >= 0;
  20.   return true;
  21. }
  22.  
  23. bool consistent(int x, int y, int num) {
  24.   bool res = true;
  25.   if (x > 0)
  26.     res &= consistentPair(field[x][y], field[x - 1][y], constr_hor[x][y]);
  27.   if (y > 0)
  28.     res &= consistentPair(field[x][y], field[x][y - 1], constr_vert[x][y]);
  29.  
  30.   return res;
  31. }
  32.  
  33. void printField() {
  34.   for (int i = 0; i < SIZE; ++i) {
  35.     for (int j = 0; j < SIZE; ++j) {
  36.       cout << (field[i][j] + 1) << " ";
  37.     }
  38.     cout << "\n";
  39.   }
  40. }
  41.  
  42. void brute(int x, int y) {
  43.   if (x >= SIZE) {
  44.     printField();
  45.     return;
  46.   }
  47.  
  48.   int nx = x, ny = y + 1;
  49.   if (ny >= SIZE) {
  50.     nx++, ny = 0;
  51.   }
  52.  
  53.   for (int i = 0; i < 9; ++i) {
  54.     if ((free_hor[x] >> i) & 1) continue;
  55.     if ((free_vert[y] >> i) & 1) continue;
  56.     if ((free_block[x / BLOCK_SIZE][y / BLOCK_SIZE] >> i) & 1) continue;
  57.     field[x][y] = i;
  58.     if (!consistent(x, y, i)) continue;
  59.  
  60.     free_hor[x] ^= (1 << i);
  61.     free_vert[y] ^= (1 << i);
  62.     free_block[x / BLOCK_SIZE][y / BLOCK_SIZE] ^= (1 << i);
  63.     brute(nx, ny);
  64.     free_hor[x] ^= (1 << i);
  65.     free_vert[y] ^= (1 << i);
  66.     free_block[x / BLOCK_SIZE][y / BLOCK_SIZE] ^= (1 << i);
  67.   }
  68. }
  69.  
  70. int main() {
  71.   for (int i = 0; i < SIZE; ++i) {
  72.     string line;
  73.     cin >> line;
  74.     int y = 1;
  75.     for (int j = 0; j < line.size(); ++j) {
  76.       constr_vert[i][y] = (line[j] == '<' ? -1 : 1);
  77.       ++y;
  78.       if (y % BLOCK_SIZE == 0) ++y;
  79.     }
  80.   }
  81.   for (int i = 0; i < SIZE; ++i) {
  82.     string line;
  83.     cin >> line;
  84.     int x = 1;
  85.     for (int j = 0; j < line.size(); ++j) {
  86.       constr_hor[x][i] = (line[j] == '<' ? -1 : 1);
  87.       ++x;
  88.       if (x % BLOCK_SIZE == 0) ++x;
  89.     }
  90.   }
  91.   brute(0, 0);
  92.   return 0;
  93. }
Success #stdin #stdout 0.06s 3480KB
comments (?)
stdin
copy 
><><<>
><<<>>
<><>><
><><<<
<<<>><
>>><<>
>><>><
<><><>
<>><<>

<>>>><
><<><<
<<<>><
><><<>
><<><>
<>><<<
<<<>>>
<>><<>
<<><>>
stdout
copy 
8 3 4 9 6 7 2 5 1 
9 1 5 2 3 8 7 6 4 
2 7 6 4 5 1 8 3 9 
6 5 7 3 2 9 1 4 8 
4 8 9 1 7 5 6 2 3 
3 2 1 8 4 6 5 9 7 
7 4 3 5 8 2 9 1 6 
1 6 2 7 9 3 4 8 5 
5 9 8 6 1 4 3 7 2
https://ideone.com/8mKZAk
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!