lyuda-shahmaty

#include <stdio.h>
#include <stdlib.h>

int check_if_bad(int x1, int y1, int x2, int y2) {
    return x1 == x2 || y1 == y2 || x1 + y1 == x2 + y2 || x1 - y1 == x2 - y2;
}

int check_if_bad_f(int** field, int n, int x, int y) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (field[i][j]) {
                if (check_if_bad(i, j, x, y)) {
                    return 1;
                }
            }
        }
    }
    return 0;
}

int** copy_field(int** field, int n) {
    int** fn = (int**)malloc(sizeof(int*) * (n + 1));

    for (int i = 0; i < n; i++) {
        fn[i] = (int*)malloc(sizeof(int) * (n + 1));

        for (int j = 0; j < n; j++) {
            fn[i][j] = field[i][j];
        }
    }

    return fn;
}

int** concat_fields(int** f1, int** f2, int n) {
    int** fn = copy_field(f1, n);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (f2[i][j]) {
                fn[i][j] = 1;
            }
        }
    }

    return fn;
}

int** find_variants(int** field, int** bad_variants, int n, int l) {
    int** fn = copy_field(field, n);
    int e = 0;

    for (int m = 0; m < l; m++) {
        e = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!fn[i][j] && !bad_variants[i][j] && !check_if_bad_f(fn, n, i, j)) {
                    fn[i][j] = 1;
                    e = 1;
                    break;
                }
            }
            if (e) {
                break;
            }
        }

        if (!e) {
            //return blank if no solution
            int** a = (int**)malloc(sizeof(int*));
            a[0] = (int*)malloc(sizeof(int));
            a[0][0] = -1;
            return a;
        }
    }

    if (!e) {
        //return blank if no solution
        int** a = (int**)malloc(sizeof(int*));
        a[0] = (int*)malloc(sizeof(int));
        a[0][0] = -1;
        return a;
    }

    return fn;
}

void print_variants(int** field, int n, FILE* f) {
    int max_size = 1000;
    int line_size = max_size * n * n;
    char* line = (char*)malloc(sizeof(char) * line_size + 1);
    line[0] = '\0';

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (field[i][j]) {
                if (line[0] != '\0') {
                    snprintf(line, line_size, "%s (%d,%d)", line, i, j);
                }
                else {
                    snprintf(line, line_size, "(%d,%d)", i, j);
                }
            }
        }
    }
    fputs(line, f);
}

int main()
{
    int n, l, k, x, y;

    FILE* inp = fopen("input.txt", "r");

    if (inp == NULL) {
        exit(1);
    }

    char* line = (char*)malloc(sizeof(char) * 100);
    fgets(line, 100, inp);
    sscanf(line, "%d %d %d", &n, &l, &k);
    //printf("%d %d %d\n", n, l, k);

    int** field = (int**)malloc(sizeof(int*) * (n + 1));
    for (int i = 0; i < n; i++) {
        field[i] = (int*)malloc(sizeof(int) * n);
        for (int j = 0; j < n; j++) {
            field[i][j] = 0;
        }
    }

    for (int i = 0; i < k; i++) {
        while (fgets(line, 100, inp) != NULL) {
            sscanf(line, "%d %d", &x, &y);
            //printf("%d %d\n", x, y);
            field[x][y] = 1;
        }
    }

    fclose(inp);

    FILE* out = fopen("output.txt", "w");

    int one_e = 0;
    int** bad_variants = copy_field(field, n);
    while (1) {
        int** variants = find_variants(field, bad_variants, n, l);

        if (variants[0][0] == -1) {
            if (!one_e) {
                fputs("no solutions", out);
                exit(0);
            }
            break;
        }

        if (one_e) {
            fputs("\n", out);
        }

        one_e = 1;
        bad_variants = concat_fields(bad_variants, variants, n);
        print_variants(variants, n, out);
        if (l == 0) {
            break;
        }
    }

    fclose(out);

    return 0;
}