/* Queens.c Vincent Cheng viwcheng CMPS 12B 7/18/19 finds solution to N queens problem from 1<=n<=15*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

void placeQueen(int** B, int n, int i, int j) {
    B[i][j]++; // i is row, j is column
    B[i][0] = j;
    for (int k = 1; k <= n; k++) {
        if (j + k <= n) {
            B[i][j + k]--;
            if (i - k > 0) {
                B[i - k][j + k]--;
            }
            if (i + k <= n) {
                B[i + k][j + k]--;
            }
        }
    }
}
void removeQueen(int** B, int n, int i, int j) {
    B[i][j]--;
    B[i][0] = 0;
    for (int k = 1; k <= n; k++) {
        if (j + k <= n) {
            B[i][j + k]++;
            if (i - k > 0) {
                B[i - k][j + k]++;
            }
            if (i + k <= n) {
                B[i + k][j + k]++;
            }
        }
    }
}
void printBoard(int** B, int n) {
    /*  char* listOfColumns = malloc(n*sizeof(char));
     for (int i = 0; i < n; i++)
     {
     listOfColumns[i]=B[i][0];
     }
     char* str = malloc(n*sizeof(char));*/
    //str[0] = "{";
    printf("(");
    for (int k = 1; k <= n; k++) {
        if (k < n) {
            /*str[k]=listOfColumns[k];
             str[k+1]=", ";*/
            printf("%d, ", B[k][0]);
        } else {
            /*str[k]=listOfColumns[k];
             str[k+1]=")\n";*/
            printf("%d", B[k][0]);

        }
    }
    //printf(str);
    printf(")\n");
}
int findSolutions(int** B, int n, int i, char* mode) {
    int sum = 0;
    if (i > n) {
        if (strcmp(mode,"verbose")==0) {
            printBoard(B, n);
        }
        return 1;
    } else {
        for (int j = 1; j <= n; j++) {
            if (B[j][i] == 0) // j is row, i is column
            {
                placeQueen(B, n, j, i);
                sum += findSolutions(B, n, i + 1, mode);
                removeQueen(B, n, j, i);
            }

        }
    }
    return sum;
}
int main(int argc, char* argv[]) {
    int n;
    char ch;
    if ((argc != 2) && (argc != 3)) {
        printf(
                "Usage: Queens [-v] number\nOption: -v verbose output, print all solutions\n");
    } else {
        if (argc==2 && strcmp(argv[1], "-v") == 0) {
			printf(
                "Usage: Queens [-v] number\nOption: -v verbose output, print all solutions\n");
		}
		else if (argc==3 && strcmp(argv[1], "-v") == 0)
		{
            sscanf(argv[2], "%d%c", &n, &ch);
            if ((n <= 0) || (n > 15)) {
                printf(
                        "Usage: Queens [-v] number\nOption: -v verbose output, print all solutions\n");
                return EXIT_FAILURE;
            }
            int** arr = calloc(n + 1, sizeof(int*));
            for (int i = 0; i <= n; i++) {
                arr[i] = calloc(n + 1, sizeof(int));
            }
            if (n != 1) {

                printf("%d-Queens has %d solutions\n", n,
                        findSolutions(arr, n, 1, "verbose"));
            } else {
                printf("%d-Queens has %d solution\n", n,
                        findSolutions(arr, n, 1, "verbose"));
            }
			for(int i = 0; i <= n; i++)
			{
				free(arr[i]);
				arr[i] = NULL;
			}
			free(arr);
			arr = NULL;
        } else {
            sscanf(argv[1], "%d%c", &n, &ch);
            if ((n <= 0) || (n > 15)) {
                printf(
                        "Usage: Queens [-v] number\nOption: -v verbose output, print all solutions\n");
                return EXIT_FAILURE;
            }
            int** arr = calloc(n + 1, sizeof(int*));
            for (int i = 0; i <= n; i++) {
                arr[i] = calloc(n + 1, sizeof(int));
            }
            if (n != 1) {
                printf("%d-Queens has %d solutions\n", n,
                        findSolutions(arr, n, 1, ""));
            } else {
                printf("%d-Queens has %d solution\n", n,
                        findSolutions(arr, n, 1, ""));
            }
			for(int i = 0; i <= n; i++)
			{
				free(arr[i]);
				arr[i] = NULL;
			}
			free(arr);
			arr = NULL;
		}
    }


}