knuth_x

namespace knuth_x {
  struct Node {
    int id;
    int siz;
    Node* leader;
    Node* up;
    Node* down;
    Node* left;
    Node* right;

    Node(int id = -1) : id(id), siz(0), leader(nullptr), up(nullptr), down(nullptr), left(nullptr), right(nullptr) {
      void(0);
    }
  };

  void cover(Node* leader) {
    leader->right->left = leader->left;
    leader->left->right = leader->right;
    for (Node* i = leader->down; i != leader; i = i->down) {
      for (Node* j = i->right; j != i; j = j->right) {
        j->up->down = j->down;
        j->down->up = j->up;
        j->leader->siz -= 1;
      }
    }
  }

  void uncover(Node* leader) {
    leader->right->left = leader;
    leader->left->right = leader;
    for (Node* i = leader->up; i != leader; i = i->up) {
      for (Node* j = i->left; j != i; j = j->left) {
        j->up->down = j;
        j->down->up = j;
        j->leader->siz += 1;
      }
    }
  }

  bool search(Node* head, std::vector<int>& res) {
    if (head->right == head) {
      return true;
    }
    Node* ptr = nullptr;
    for (Node* i = head->right; i != head; i = i->right) {
      if (i->siz == 0) {
        return false;
      }
      if (!ptr || ptr->siz > i->siz) {
        ptr = i;
      }
    }
    cover(ptr);
    for (Node* i = ptr->down; i != ptr; i = i->down) {
      res.push_back(i->id);
      for (Node* j = i->right; j != i; j = j->right) {
        cover(j->leader);
      }
      if (search(head, res)) {
        return true;
      }
      res.pop_back();
      for (Node* j = i->left; j != i; j = j->left) {
        uncover(j->leader);
      }
    }
    uncover(ptr);
    return false;
  }

  std::vector<int> solve(const std::vector<std::vector<bool>>& mat) { // empty vector if no solution...
    assert(!mat.empty());
    int n = int(mat[0].size());
    assert(n > 0);
    for (const auto& vec : mat) {
      assert(int(vec.size()) == n);
    }
    std::vector<Node> leaders(n);
    Node head;
    head.left = &leaders.back();
    head.right = &leaders.front();
    for (int i = 0; i < n; ++i) {
      leaders[i].up = &leaders[i];
      leaders[i].down = &leaders[i];
      leaders[i].left = (i == 0 ? &head : &leaders[i - 1]);
      leaders[i].right = (i == n - 1 ? &head : &leaders[i + 1]);
    }
    std::vector<Node*> nodes;
    for (int i = 0; i < int(mat.size()); ++i) {
      Node* last = nullptr;
      for (int j = 0; j < n; ++j) {
        if (!mat[i][j]) {
          continue;
        }
        Node* new_node = new Node(i);
        leaders[j].siz += 1;
        new_node->up = leaders[j].up;
        new_node->down = &leaders[j];
        new_node->leader = &leaders[j];
        leaders[j].up->down = new_node;
        leaders[j].up = new_node;
        if (last) {
          new_node->left = last;
          new_node->right = last->right;
          new_node->right->left = new_node;
          new_node->left->right = new_node;
        } else {
          new_node->left = new_node;
          new_node->right = new_node;
        }
        nodes.push_back(last = new_node);
      }
    }
    std::vector<int> res;
    search(&head, res);
    for (const auto& ptr : nodes) {
      delete ptr;
    }
    return res;
  }
} // namespace knuth_x