// El principio del palomar como fórmula: n + 1 palomas en n casillas, cada paloma en alguna
// casilla y ninguna casilla con dos palomas. No se puede cumplir, y a un solucionador SAT le
// cuesta mucho demostrarlo: es el contraste con las fórmulas del tableau.
//   build/pigeonhole 8 > build/php8.cnf
#include <cstdlib>
#include <iostream>

#include "cnf.h"

int main(int argc, char** argv) {
    if (argc != 2) {
        std::cerr << "uso: pigeonhole n\n";
        return 2;
    }
    int n = std::atoi(argv[1]);
    if (n < 1 || n > 20) {
        std::cerr << "n debe estar entre 1 y 20\n";
        return 2;
    }
    Cnf f;
    f.num_vars = (n + 1) * n;
    // La variable de "la paloma p está en la casilla h", con p de 0 a n y h de 0 a n - 1.
    auto in = [n](int p, int h) { return p * n + h + 1; };
    for (int p = 0; p <= n; p++) {
        Clause some;
        for (int h = 0; h < n; h++) {
            some.push_back(in(p, h));
        }
        f.add(some);
    }
    for (int h = 0; h < n; h++) {
        for (int p = 0; p <= n; p++) {
            for (int q = p + 1; q <= n; q++) {
                f.add({-in(p, h), -in(q, h)});
            }
        }
    }
    write_dimacs(std::cout, f);
    return 0;
}
