/// TRABALHO REALIZADO POR:
///  36431 - João Vargas
///  36763 - Pedro Pinheiro


/// O QUE FALTA FAZER !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
/// FALTA IMPLEMENTAR A FILA
/// FALTA R14 E R15 (BIN E TXT, NÓS JÁ TEMOS MAS É EM METRIZ, TEMOS DE FAZER COM LINKED LIST AGORA )
/// QUANDO UM TABULEIRO FOR IMPOSSIVEL TEMOS DE TER UMA CONDICAO NO ALGORITMO MELHORADO QUE PARE A EXECUCAO DO ALGORITMO E IMPRIMA A MENSAGEM DE SUDOKU IMPOSSIVEL
/// FAZER MAIS 2 PESQUISAS PARA MELHORAR O ALGORITMO
/// !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

#include "projeto.h"
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

/// VARIÁVEIS GLOBAIS ///
int count_global =0; /// contador de numero de ciclos feitos por cada algoritmo
int mudar_algoritmo = 0;
int num_tab_memoria = 0;
int num_zeros=0;
///



struct fila addFila(struct fila *f, struct node *head){
    if(f->size == 0){
        /// se o size = 0 , então a fila está vazia
        f->tabuleiro = malloc(sizeof(struct tabuleiros));
        f->inicio = malloc(sizeof(struct tabuleiros));
        f->fim = malloc(sizeof(struct tabuleiros));
        f->tabuleiro->no = head;
        f->inicio = f->tabuleiro;
        f->tabuleiro->next = NULL;
        f->tabuleiro->prev = NULL;
        f->fim = f->tabuleiro;
        f->size++;
        f->tabuleiro->index = f->size ;
        return *f;
    }else{
        struct tabuleiros *aux =NULL;
        struct fila *faux = f;
        aux = malloc(sizeof(struct tabuleiros) );
        aux->no = head; // aux é o novo nó para inserir
        aux->next = f->tabuleiro;
        aux->prev = NULL;
        f->tabuleiro->prev = aux;
        f->inicio = aux; //o inicio vai ficar a apontar para o novo nó
        f->size++;
        f->tabuleiro->index = f->size;
        return *f;
    }
}
void printfila(struct fila *f){
    f->tabuleiro = f->inicio;
    while(f->tabuleiro != NULL){
        printf("%d \n",f->tabuleiro->index);
        f->tabuleiro = f->tabuleiro->next;
    }
}
struct fila * createFila(){
    struct fila * f=NULL;
    f = malloc(sizeof(struct fila));
    f->size=0;
    return f;
}



/**
 *
 * @param matriz
 * @param lin
 * @param col
 * @return
 */
struct node *encontra_zeros(struct node *tab)
{
    struct node * current = tab;
    struct node * pcs = tab;
    int lin=0, col=0;
    while(pcs != NULL) {
        while(current != NULL) {
            current->col = col;
            current->lin = lin;
            if (current->data == 0) {
                return current;
            }
            current = current->pnext;
            count_global ++;
            col++;
        }
        lin ++;
        col = 0;
        current = pcs->S;
        pcs = pcs->S;
    }
    free(current);
    free(pcs);
    return 0;
}
/**
 *
 * @param matriz
 * @param lin
 * @param col
 * @param num
 * @return
 */
int verifica_quadrado(struct node *tab,int num){
    int raiz = sqrt(NUM);
    struct node *quad = tab;
    struct node *aux_quad = tab;
    int lin_quad = tab->lin - tab->lin % raiz;
    int col_quad = tab->col - tab->col % raiz;
    int cel_num = (tab->lin * NUM) + tab->col; /// para verificar em todas as posicoes do quadrado menos nesta, porque nao vai verificar o proprio numero

    /// percorre o quardrado para veirificar os numeros possiveis

    while (quad->lin != lin_quad){ /// para quad chegar à celula do inicio do quadrado (lin)
        quad = quad->N;
        aux_quad = aux_quad->N;
    }
    while (quad->col != col_quad){ /// para quad chegar à celula do inicio do quadrado (col)
        quad = quad->prev_node;
        aux_quad = aux_quad->prev_node;
    }

    for (int i = 0; i < raiz; i++) {
        for (int j = 0; j < raiz; j++) {
            int aux_cel_num = (quad->lin * NUM) + quad->col; /// para verificar em todas as posicoes do quadrado menos nesta, porque nao vai verificar o proprio numero
            if (quad->data == num && aux_cel_num != cel_num) {
                return 0;
            }
            quad = quad->pnext;
        }
        quad = aux_quad->S;
        aux_quad = aux_quad->S;
    }
    free(quad);
    free(aux_quad);
    return 1;
}

int verifica_lin(struct node *tab,int num) {
    struct node * norte = tab;
    struct node * sul = tab;

    while (norte != NULL){
        if(norte->data == num){
            count_global ++;
            return 0;
        }
        norte = norte->N;
    }

    while (sul != NULL){
        if(sul->data == num){
            count_global ++;
            return 0;
        }
        sul = sul->S;
    }
    free(norte);
    free(sul);
    return 1;
}

int verifica_col(struct node *tab,int num) {
    struct node * este = tab;
    struct node * oeste = tab;

    while (este != NULL){
        if(este->data == num){
            count_global ++;
            return 0;
        }
        este = este->pnext;
    }

    while (oeste != NULL){
        if(oeste->data == num){
            count_global ++;
            return 0;
        }
        oeste = oeste->prev_node;
    }
    free(este);
    free(oeste);
    return 1;
}

int verifica_x_principal(struct node *tab,int num){
    struct node * diag_prin_no = tab;
    struct node * diag_prin_se = tab;

    while (diag_prin_no != NULL){
        if(diag_prin_no->data == num){
            count_global ++;
            return 0;
        }
        diag_prin_no = diag_prin_no->NO;
    }
    while (diag_prin_se != NULL){
        if(diag_prin_se->data == num){
            count_global ++;
            return 0;
        }
        diag_prin_se = diag_prin_se->SE;
    }
    free(diag_prin_se);
    free(diag_prin_no);
    return 1;
}

int verifica_x_secundario(struct node * tab,int num){
    struct node * diag_prin_so = tab;
    struct node * diag_prin_ne = tab;

    while (diag_prin_so != NULL){
        if(diag_prin_so->data == num){
            count_global ++;
            return 0;
        }
        diag_prin_so = diag_prin_so->SO;
    }
    while (diag_prin_ne != NULL){
        if(diag_prin_ne->data == num){
            count_global ++;
            return 0;
        }
        diag_prin_ne = diag_prin_ne->NE;
    }
    free(diag_prin_so);
    free(diag_prin_ne);
    return 1;
}
int verificar_condicoes(struct node * tab,int num){
    if(tab->lin == tab->col && (tab->lin + tab->col) == NUM-1) { /// diagonal principal e secundaria
        if (verifica_col(tab, num) == 1 &&
            verifica_lin(tab, num) == 1 &&
            verifica_quadrado(tab, num) == 1 &&
            verifica_x_principal(tab, num) == 1 &&
            verifica_x_secundario(tab, num) == 1 && tab->data == 0){
            return 1;
        }
    }

    else if(tab->lin == tab->col) { /// para verificar se os numeros estao posicionados em alguma posicao do "x", (lin = col, para \ )(lin+col ==N-1, para / )
        if (verifica_lin(tab, num) == 1 &&
            verifica_col(tab, num) == 1 &&
            verifica_quadrado(tab, num) == 1 &&
            verifica_x_principal(tab, num) == 1 && tab->data == 0) {
            return 1;
        }
    }
        /// caso nao esteja posicionado no "x" faz as condicoes normais
    else if ((tab->lin + tab->col) == NUM-1){
        if (verifica_col(tab, num) == 1 &&
            verifica_lin(tab, num) == 1 &&
            verifica_quadrado(tab, num) == 1 &&
            verifica_x_secundario(tab, num) == 1 && tab->data == 0) {
            return 1;
        }
    }

    else{
        if (verifica_col(tab,num) == 1 &&
            verifica_lin(tab, num) == 1 &&
            verifica_quadrado(tab, num) == 1 &&
                tab->data == 0) {
            return 1;
        }
    }

    return 0;
}
/**
 *
 * @param matriz
 * @return
 */
int sudoku(struct node *head) {
    struct node* current = NULL;
    current = encontra_zeros(head);

    if (current == 0) /// encontra todos os zeros da matriz, manda o endereco para a variavel row e col ser incrementada
        return 1; /// caso retorne 1, quer dizer que já nao existem zeros na matriz e retorna para de seguida ir para o if(sudoku) e sair da funcao

    for (int num = 1; num <= NUM; num++){ /// numeros que vao ser inseridos nos zeros encontrados
        if(verificar_condicoes(current,num) == 1){
            current->data = num;

            if (sudoku(head)) /// quando terminar o sudoku, este if trata de sair da funcao
                return 1;

            current->data = 0; /// nesta posicao o numero ja esgotou todas as possibilidade (num 1-9) e vai ter de fazer o Back Tracking Search, ou seja vai ter de recuar as posicoes de forma a tentar alterar os numeros anteriores
        }
    }
    return 0;
}

void guardar_matriztxt(struct node * tab) {
    FILE *fp;
    fp=fopen("matrizsolucao.txt","w");
    int count_col=1,count_lin = 1;
    int raiz = sqrt(NUM);
    struct node * current = tab;
    for (int lin = 0; lin < NUM; lin++){
        for (int col = 0; col < NUM; col++) {
            fprintf(fp,"%d",tab->data);
            fprintf(fp," ");
            if(col+1 == (raiz)*count_col){
                count_col ++;
                fprintf(fp,"  ");
            }
            tab = tab->pnext;
        }
        count_col =1;
        if(lin+1 == (raiz)*count_lin){
            count_lin++;
            fprintf(fp,"\n");
        }
        fprintf(fp,"\n");
        tab = current->S;
        current = current-> S;
    }
    fclose(fp);
}
void guardar_matrizbin(struct node * tab) {
    FILE *fp;
    fp=fopen("matrizsolucao.bin","wb");
    struct node * current = tab;
    int count_col=1,count_lin = 1;
    int raiz = sqrt(NUM);
    for (int lin = 0; lin < NUM; lin++){
        for (int col = 0; col < NUM; col++) {
            fwrite(&tab->data, sizeof(int),1,fp);
            fwrite(" ",1,1,fp);
            if(col+1 == (raiz)*count_col){
                count_col ++;
                fwrite("  ",1,1,fp);
            }
            tab = tab->pnext;
        }
        count_col =1;
        if(lin+1 == (raiz)*count_lin){
            count_lin++;
            fwrite("\n",1,1,fp);
        }
        fwrite("\n",1,1,fp);
        tab = current->S;
        current = current-> S;
    }
    fclose(fp);
}

void carregar_matriz(struct node **head){
    FILE *fp;
    fp=fopen("sudoku_X9x9.txt","r");
    //fp=fopen("sudoku_X16x16.txt","r");

    if (fp==NULL)
        printf("Erro ao abrir arquivo!");

    for (int i = 0; i < NUM; i++){          ///guarda a letra numa variavel e aplica na matriz
        for (int j = 0; j < NUM; j++) {
            struct node * new_node = (struct node * ) malloc(sizeof(struct node)); /// aloco espaco para no novo node
            struct node *current = *head; /// current tem de comecar a percorrer pelo primeiro nó, isto pelo pelo head
            struct node * first_lin = NULL; /// node auxiliar, apenas para ajudar a fazer ligacoes com as linhas inferiores (vai estar sempre uma linha a cima)
            fscanf(fp, "%d", & new_node->data);
            new_node->pnext = NULL; /// o node seguinte vai ser null

            if(*head == NULL) { /// para o 1 caso, quando é o primeiro node a ser inserido, head ainda é null
                new_node->prev_node = NULL; /// node anterior é null
                new_node->N = NULL;
                new_node->S = NULL;
                new_node->NO = NULL;
                new_node->NE = NULL;
                new_node->SO = NULL;
                new_node->SE = NULL;
                *head = new_node; /// por isso head tem de passar a ser o primeiro node
            }else{
                if (i < 1) { /// primeira linha da matriz
                    while (current->pnext != NULL) {
                        current = current->pnext;
                    }
                    new_node->prev_node = current; /// prev_node vai sempre apontar para o node anterior
                    new_node->N = NULL; /// norte vai ser sempre NULL na 1 linha
                    new_node->S = NULL; /// S vai comecar a NULL

                    new_node->NO = NULL;
                    new_node->NE = NULL;
                    new_node->SO = NULL;
                    new_node->SE = NULL;

                    current->pnext = new_node; /// adiciono o novo node

                }else if(j == 0){ /// para a primeira celula de cada linha
                    while (current->S != NULL){ /// percorro current até o maximo possivel em S
                        current= current->S;
                    }

                    new_node->N = current; /// node N vai ser o node da linha superior
                    new_node->S = NULL; /// S vai comecar a NULL
                    new_node->prev_node = NULL; /// prev_node vai ser sempre NULL

                    new_node->NO = NULL;
                    new_node->NE = current->pnext;
                    new_node->SO = NULL;
                    new_node->SE = NULL;

                    current->pnext->SO = new_node;
                    current->S = new_node; /// adiciono um novo node a S de current

                }else { /// para os restantes elementos das restantes linhas
                    while (current->S != NULL){ /// percorre o maximo possivel para s (percorrendo as linhas)
                        current = current->S;
                    }

                    first_lin = current->N; /// fist_lin está uma linha a cima do current, isto porque eu quero fazer a ligacao da linha de cima com a de baixo e por isso uso o first_lin

                    while (current->pnext != NULL){ /// percorre o maximo possivel para a frente ( percorre as colunas )
                        current = current->pnext;
                        first_lin = first_lin->pnext; /// para ter acesso á celula da linha de cima para fazer o N e o S
                    }
                    new_node->prev_node = current;
                    new_node->N = first_lin->pnext;
                    new_node->S = NULL;

                    new_node->NO = first_lin;
                    if(first_lin->pnext->pnext != NULL) { /// so entra aqui nas posicoes do meio da matriz, isto porque a ultima celula de cada linha, a posicao NE tem de ser NULL (no new_node)
                        new_node->NE = first_lin->pnext->pnext;
                    }
                    new_node->SO = NULL;
                    new_node->SE = NULL;


                    current->pnext = new_node;
                    first_lin->pnext->S = new_node;
                    first_lin->SE = new_node;
                    if(first_lin->pnext->pnext != NULL) { /// so entra aqui nas posicoes do meio da matriz, isto porque a ultima celula de cada linha, a posicao NE e se nao tem NE, a posicao correspondente tambem nao pode ter o SO, tem de ser NULL (no first_lin)
                        first_lin->pnext->pnext->SO = new_node; ///
                    }
                }
            }
        }
    }
    fclose(fp);
}

void imprimirSudoku(struct node *pcs)
{
    /// IMPRIMIR A MATRIZ ( Este-Sul )
    printf("\nTabuleiro:\n");
    struct node * current = pcs;
    int lin=0,col=0,count_col=1,count_lin=1,raiz = sqrt(NUM);
    while (pcs != NULL){
        while (current != NULL){
            printf( "%d ", current->data);
            if(col +1 == (raiz) * count_col){
                count_col ++;
                printf("  ");
            }
            col ++;
            current = current->pnext;
        }
        count_col = 1;
        if(lin +1 == (raiz) * count_lin){
            count_lin++;
            printf("\n");
        }
        printf("\n");
        lin ++;col=0;
        current = pcs->S;
        pcs = pcs->S;
    }
    free(current);
}
void numeros_possiveis(struct node *current) {
    struct node *norte = current;
    struct node *sul = current;
    struct node *este = current;
    struct node *oeste = current;
    struct node*diag_prin_no = current;
    struct node*diag_prin_se = current;
    struct node*diag_secundaria_ne = current;
    struct node*diag_secundaria_so = current;
    struct node * quad = current;
    struct node * aux_quad = current;

    int tam_cel=0;

    int raiz = sqrt(NUM);
    int lin_quad = current->lin - current->lin % raiz;
    int col_quad = current->col - current->col % raiz;

    int aux[NUM*NUM], numeros[NUM], array_possiveis[NUM];
    int k = 0;

    for (int i = 0; i < NUM ; i++) { /// numeros de 1-9
        numeros[i] = i+1;
    }

    /// percorre as linhas e colunas para verificar os numeros possiveis
    while (norte != NULL){
        if(norte->data != 0){
            aux[k] = norte->data; /// coloca os valores existentes na linha no array aux
            k++;
        }
        norte = norte->N;
    }

    while (sul != NULL){
        if(sul->data != 0){
            aux[k] = sul->data; /// coloca os valores existentes na linha no array aux
            k++;
        }
        sul = sul->S;
    }

    while (este != NULL){
        if(este->data != 0){
            aux[k] = este->data; /// coloca os valores existentes na linha no array aux
            k++;
        }
        este = este->pnext;
    }

    while (oeste != NULL){
        if(oeste->data != 0){
            aux[k] = oeste->data; /// coloca os valores existentes na linha no array aux
            k++;
        }
        oeste = oeste->prev_node;
    }

    /// percorre o quardrado para veirificar os numeros possiveis

    while (quad->lin != lin_quad){ /// para quad chegar à celula do inicio do quadrado (lin)
        quad = quad->N;
        aux_quad = aux_quad->N;
    }
    while (quad->col != col_quad){ /// para quad chegar à celula do inicio do quadrado (col)
        quad = quad->prev_node;
        aux_quad = aux_quad->prev_node;
    }

    for (int i = 0; i < raiz; i++) {
        for (int j = 0; j < raiz; j++) {
            if (quad->data != 0 ) {
                aux[k] = quad->data; /// coloca os valores existentes no quadrado no array aux
                k++;
            }
            quad = quad->pnext;
        }
        quad = aux_quad->S;
        aux_quad = aux_quad->S;
    }

    /// caso esteja na diagonal verifica tambem na diagonal

    if (current->lin == current->col || (current->lin + current->col) == NUM -1) { /// para verificar se os numeros estao posicionados em alguma posicao do "x", (lin = col, para \ )(lin+col ==N-1, para / )
        if(current->lin == current->col) { /// na diagonal ( \ )
            while (diag_prin_no){
                if(diag_prin_no->data != 0){
                    aux[k] = diag_prin_no->data; /// coloca os valores existentes na linha no array aux
                    k++;
                }
                diag_prin_no = diag_prin_no->NO;
            }
            while (diag_prin_se){
                if(diag_prin_se->data != 0){
                    aux[k] = diag_prin_se->data; /// coloca os valores existentes na linha no array aux
                    k++;
                }
                diag_prin_se = diag_prin_se->SE;
            }
        }else{ /// na diagonal /
            while (diag_secundaria_ne){
                if(diag_secundaria_ne->data != 0){
                    aux[k] = diag_secundaria_ne->data; /// coloca os valores existentes na linha no array aux
                    k++;
                }
                diag_secundaria_ne = diag_secundaria_ne->NE;
            }
            while (diag_secundaria_so){
                if(diag_secundaria_so->data != 0){
                    aux[k] = diag_secundaria_so->data; /// coloca os valores existentes na linha no array aux
                    k++;
                }
                diag_secundaria_so = diag_secundaria_so->SO;
            }
        }
    }

    /// agora verifico os numeros que nao foram usados, ou seja os numeros possiveis

    int contador=0; /// variavel auxiliar usada apenas para percorrer aux

    for (int i = 0; i < NUM ; i++) { /// percorre o array de numeros de 0-9
        while( numeros[i] != aux[contador]  && contador <= k) { /// percorre o array aux enquanto este for diferente do numero e o tamanho de contador for menor que o tamanho de aux
            contador++;
            if(contador == k) /// quer dizer que contador percorreu todos os numeros de aux e que foram todos diferentes por isso esse numero é um dos "possiveis"
            {
                array_possiveis[tam_cel]=numeros[i];
                tam_cel++; /// incrementa contador de numeros possiveis
            }
        }
        contador = 0; /// cada vez que salta so ciclo while contador tem de ser zerado
    }

    current->tam = tam_cel;
    for (int l = 0; l < current->tam ; l++) {
        current->array[l] = array_possiveis[l];
    }

    free(norte);
    free(sul);
    free(este);
    free(oeste);
    free(diag_prin_no);
    free(diag_prin_se);
    free(diag_secundaria_ne);
    free(diag_secundaria_so);
    free(aux_quad);
    free(quad);

}

void remover_numero(struct node *current,int cel,struct node *head){
    int raiz = sqrt(NUM);
    struct node *linhas_N = current->N;
    struct node *linhas_S = current->S;
    struct node *colunas_E = current->pnext;
    struct node *colunas_O = current->prev_node;
    struct node *diag_pri_NO = current->NO;
    struct node *diag_pri_SE = current->SE;
    struct node *diag_secu_NE = current->NE;
    struct node *diag_secu_SO = current->SO;
    struct node *aux_quad = current;

    int remove_lin=0, count_aux=0; /// count tem de multiplicar pelas linhas, para ir à posicao correta
    int lin_aux=0,col_aux=0; /// array auxiliar usado para colocar o numero que pretendo eliminar na ultima posicao
    current->data = current->array[cel]; /// atribui o numero correto à celula da struct ( numero pertencente à celula )

    /// remover das linhas
    while (linhas_N != NULL) { /// remover das linhas
        for (int j = 0; j < linhas_N->tam; j++) {
            if (linhas_N->array[j] == current->array[cel]) { /// encontra nas linhas, as celulas que contêm os numeros que pretendo remover
                linhas_N->array[j] = 0; /// zero o numero que ia "eliminar" e passo-o para ultima posicao do array
                remove_lin = j + 1; /// porque j comeca em 0 e nao em 1
                count_aux = j; /// auxiliar para ajudar a colocar numero que pretendo eliminar na ultima posicao
                while (remove_lin < linhas_N->tam) { /// para trocar até à ultima posicao do array
                    lin_aux = linhas_N->array[count_aux +1];
                    linhas_N->array[count_aux +1] = linhas_N->array[count_aux];
                    linhas_N->array[count_aux] = lin_aux;
                    count_aux++;
                    remove_lin++;

                    count_global++;
                }
                linhas_N->tam = linhas_N->tam - 1; /// removo uma posicao ao array
            }
        }
        linhas_N = linhas_N->N;
    }

    while (linhas_S != NULL) { /// remover das linhas
        for (int j = 0; j < linhas_S->tam; j++) {
            if (linhas_S->array[j] == current->array[cel]) { /// encontra nas linhas, as celulas que contêm os numeros que pretendo remover
                linhas_S->array[j] = 0; /// zero o numero que ia "eliminar" e passo-o para ultima posicao do array
                remove_lin = j + 1; /// porque j comeca em 0 e nao em 1
                count_aux = j; /// auxiliar para ajudar a colocar numero que pretendo eliminar na ultima posicao
                while (remove_lin < linhas_S->tam) { /// para trocar até à ultima posicao do array
                    col_aux = linhas_S->array[count_aux +1];
                    linhas_S->array[count_aux +1] = linhas_S->array[count_aux];
                    linhas_S->array[count_aux] = col_aux;
                    count_aux++;
                    remove_lin++;

                    count_global++;
                }
                linhas_S->tam = linhas_S->tam - 1; /// removo uma posicao ao array
            }
        }
        linhas_S = linhas_S->S;
    }

    /// remover das colunas
    while (colunas_E != NULL) { /// remover das linhas
        for (int j = 0; j < colunas_E->tam; j++) {
            if (colunas_E->array[j] == current->array[cel]) { /// encontra nas linhas, as celulas que contêm os numeros que pretendo remover
                colunas_E->array[j] = 0; /// zero o numero que ia "eliminar" e passo-o para ultima posicao do array
                remove_lin = j + 1; /// porque j comeca em 0 e nao em 1
                count_aux = j; /// auxiliar para ajudar a colocar numero que pretendo eliminar na ultima posicao
                while (remove_lin < colunas_E->tam) { /// para trocar até à ultima posicao do array
                    col_aux =  colunas_E->array[count_aux +1];
                    colunas_E->array[count_aux +1 ] = colunas_E->array[col_aux];
                    colunas_E->array[count_aux] = col_aux;
                    count_aux++;
                    remove_lin++;

                    count_global++;
                }
                colunas_E->tam = colunas_E->tam - 1; /// removo uma posicao ao array
            }
        }
        colunas_E = colunas_E->pnext;
    }

    while (colunas_O != NULL) {
        for (int j = 0; j < colunas_O->tam; j++) {
            if (colunas_O->array[j] == current->array[cel]) { /// encontra nas linhas, as celulas que contêm os numeros que pretendo remover
                colunas_O->array[j] = 0; /// zero o numero que ia "eliminar" e passo-o para ultima posicao do array
                remove_lin = j + 1; /// porque j comeca em 0 e nao em 1
                count_aux = j; /// auxiliar para ajudar a colocar numero que pretendo eliminar na ultima posicao
                while (remove_lin < colunas_O->tam) { /// para trocar até à ultima posicao do array
                    col_aux = colunas_O->array[count_aux +1];
                    colunas_O->array[count_aux +1] = colunas_O->array[col_aux];
                    colunas_O->array[count_aux] = col_aux;
                    count_aux++;
                    remove_lin++;

                    count_global++;
                }
                colunas_O->tam = colunas_O->tam - 1; /// removo uma posicao ao array
            }
        }
        colunas_O = colunas_O->prev_node;
    }

    /// Elimina na diagonal principal pos SE///
    if(current->lin == current->col) {
        while (diag_pri_SE != NULL) {
            for (int j = 0; j < diag_pri_SE->tam; j++) {
                if (diag_pri_SE->array[j] == current->array[cel]) { /// encontra nas linhas, as celulas que contêm os numeros que pretendo remover
                    diag_pri_SE->array[j] = 0; /// zero o numero que ia "eliminar" e passo-o para ultima posicao do array
                    remove_lin = j + 1; /// porque j comeca em 0 e nao em 1
                    count_aux = j; /// auxiliar para ajudar a colocar numero que pretendo eliminar na ultima posicao
                    while (remove_lin < diag_pri_SE->tam) { /// para trocar até à ultima posicao do array
                        col_aux = diag_pri_SE->array[count_aux + 1];
                        diag_pri_SE->array[count_aux +1] = diag_pri_SE->array[count_aux];
                        diag_pri_SE->array[count_aux] = col_aux;
                        count_aux++;
                        remove_lin++;

                        count_global++;
                    }
                    diag_pri_SE->tam = diag_pri_SE->tam - 1; /// removo uma posicao ao array
                }
            }
            diag_pri_SE = diag_pri_SE->SE;
        }
    }

    /// Elimina na diagonal principal pos NO ///
    if(current->lin == current->col) {
        while (diag_pri_NO != NULL) {
            for (int j = 0; j < diag_pri_NO->tam; j++) {
                if (diag_pri_NO->array[j] == current->array[cel]) { /// encontra nas linhas, as celulas que contêm os numeros que pretendo remover
                    *(diag_pri_NO->array +j) = 0; /// zero o numero que ia "eliminar" e passo-o para ultima posicao do array
                    remove_lin = j + 1; /// porque j comeca em 0 e nao em 1
                    count_aux = j; /// auxiliar para ajudar a colocar numero que pretendo eliminar na ultima posicao
                    while (remove_lin < diag_pri_NO->tam) { /// para trocar até à ultima posicao do array
                        col_aux = diag_pri_NO->array[count_aux +1];
                        diag_pri_NO->array[count_aux +1] = diag_pri_NO->array[count_aux];
                        diag_pri_NO->array[count_aux] = col_aux;
                        count_aux++;
                        remove_lin++;

                        count_global++;
                    }
                    diag_pri_NO->tam = diag_pri_NO->tam - 1; /// removo uma posicao ao array
                }
            }
            diag_pri_NO = diag_pri_NO->NO;
        }
    }

    /// Elimina na diagonal secundaria na pos SO ///
    if((current->lin + current->col) == NUM-1) {
        while (diag_secu_SO != NULL) {
            for (int j = 0; j < diag_secu_SO->tam; j++) {
                if (diag_secu_SO->array[j] == current->array[cel]) { /// encontra nas linhas, as celulas que contêm os numeros que pretendo remover
                    diag_secu_SO->array[j] = 0; /// zero o numero que ia "eliminar" e passo-o para ultima posicao do array
                    remove_lin = j + 1; /// porque j comeca em 0 e nao em 1
                    count_aux = j; /// auxiliar para ajudar a colocar numero que pretendo eliminar na ultima posicao
                    while (remove_lin < diag_secu_SO->tam) { /// para trocar até à ultima posicao do array
                        col_aux = diag_secu_SO->array[count_aux +1];
                        diag_secu_SO->array[count_aux +1 ] = diag_secu_SO->array[count_aux];
                        diag_secu_SO->array[count_aux] = col_aux;
                        count_aux++;
                        remove_lin++;

                        count_global++;
                    }
                    diag_secu_SO->tam = diag_secu_SO->tam - 1; /// removo uma posicao ao array
                }
            }
            diag_secu_SO = diag_secu_SO->SO;
        }
    }

    /// Elimina na diagonal secundaria na pos NE ///
    if((current->lin + current->col) == NUM-1) {
        while (diag_secu_NE != NULL) {
            for (int j = 0; j < diag_secu_NE->tam; j++) {
                if (diag_secu_NE->array[j] == current->array[cel]) { /// encontra nas linhas, as celulas que contêm os numeros que pretendo remover
                    diag_secu_NE->array[j] = 0; /// zero o numero que ia "eliminar" e passo-o para ultima posicao do array
                    remove_lin = j + 1; /// porque j comeca em 0 e nao em 1
                    count_aux = j; /// auxiliar para ajudar a colocar numero que pretendo eliminar na ultima posicao
                    while (remove_lin < diag_secu_NE->tam) { /// para trocar até à ultima posicao do array
                        col_aux = diag_secu_NE->array[count_aux +1];
                        diag_secu_NE->array[count_aux +1] = diag_secu_NE->array[count_aux];
                        diag_secu_NE->array[count_aux] = col_aux;
                        count_aux++;
                        remove_lin++;

                        count_global++;
                    }
                    diag_secu_NE->tam = diag_secu_NE->tam - 1; /// removo uma posicao ao array
                }
            }
            diag_secu_NE = diag_secu_NE->NE;
        }
    }

    /// Eliminar num em todas as celulas do quadrado
    int lin_quad = current->lin - current->lin % raiz;
    int col_quad = current->col - current->col % raiz;
    int cel_num = (current->lin * NUM) + current->col; /// para verificar em todas as posicoes do quadrado menos nesta, porque nao vai verificar o proprio numero

    while (aux_quad->lin != lin_quad){ /// para quad chegar à celula do inicio do quadrado (lin)
        aux_quad = aux_quad->N;
    }
    while (aux_quad->col != col_quad){ /// para quad chegar à celula do inicio do quadrado (col)
        aux_quad = aux_quad->prev_node;
    }

    struct node * quad = aux_quad; /// node auxiliar que anda para sul a partir da 1 celula do quadrado

    for (int i = 0; i < raiz; i++) {
        for (int k = 0; k < raiz; k++) {
            for (int j = 0; j < quad->tam; j++) {
                int aux_cel_num = (quad->lin * NUM) + quad->col;
                if (cel_num != aux_cel_num) {
                    if (quad->array[j] == current->array[cel]) { /// encontra nas linhas, as celulas que contêm os numeros que pretendo remover
                        quad->array[j] = 0; /// zero o numero que ia "eliminar" e passo-o para ultima posicao do array
                        remove_lin = j + 1; /// porque j comeca em 0 e nao em 1
                        count_aux = j; /// auxiliar para ajudar a colocar numero que pretendo eliminar na ultima posicao
                        while (remove_lin < quad->tam) { /// para trocar até à ultima posicao do array
                            col_aux = quad->array[count_aux +1];
                            quad->array[count_aux +1] = quad->array[count_aux];
                            quad->array[count_aux] = col_aux;
                            count_aux++;
                            remove_lin++;

                            count_global++;
                        }
                        quad->tam = quad->tam - 1; /// removo uma posicao ao array
                    }
                }
            }
            quad = quad->pnext;
        }
        quad = aux_quad->S;
        aux_quad = aux_quad->S;
    }

    /// para numero sozinho, tenho de remover o tamanho do array até este possuir tamanho 1 e passar à matriz o array que pretendo, neste caso vai ser um array de um numero, o numero a que a celula pertence
    if(current->array[1] != 0){
        for (int i = 0; i < current->tam ; i++) { /// zera as posicoes todas do array
            current->array[i] = 0;
        }
        while (current->tam > 1 ){ /// coloca tam com tamanho 1
            current->tam = current->tam-1;
        }
    }else if(current->tam == 1){
        *(current->array+0) = 0; /// atribui o numero correto à celula da matriz tridimensional
    }

    free(linhas_N);
    free(linhas_S);
    free(colunas_E);
    free(colunas_O);
    free(diag_pri_NO);
    free(diag_pri_SE);
    free(diag_secu_NE);
    free(diag_secu_SO);
    free(aux_quad);
    free(quad);
}

/// faz as verificacoes, para verificar se o numero é unico na linha, coluna , quadrado ou diagonal

int verifica_oculto(struct node *current ,int cel ){ /// retorna 1 caso nao exista nenhum numero igual e 0 caso exista
    int aux1=0,aux2=0,aux3=0,aux4=0,aux5=0,raiz = sqrt(NUM);
    struct node *coluna_N = current->N;
    struct node *coluna_S = current->S;
    struct node *linha_E = current->pnext;
    struct node *linha_O = current->prev_node;
    struct node *diag_prin_SE = current->SE;
    struct node *diag_prin_NO = current->NO;
    struct node *diag_secu_SO = current->SO;
    struct node *diag_secu_NE = current->NE;
    struct node * aux_quad = current;

    /// Verifica nas colunas
    while (coluna_N != NULL){
        for (int i = 0; i < coluna_N->tam ; ++i) {
            if(coluna_N->array[i] == current->array[cel]){
                aux1++;
                count_global++;
            }
        }
        coluna_N = coluna_N->N;
    }

    while (coluna_S != NULL){
        for (int i = 0; i < coluna_S->tam ; ++i) {
            if(coluna_S->array[i] == current->array[cel]){
                aux1++;
                count_global++;
            }
        }
        coluna_S = coluna_S->S;
    }

    /// Verifica nas colunas
    while ( linha_E != NULL){
        for (int i = 0; i < linha_E->tam ; ++i) {
            if(linha_E->array[i] == current->array[cel]){
                aux2++;
                count_global++;
            }
        }
        linha_E = linha_E->pnext;
    }

    while ( linha_O != NULL){
        for (int i = 0; i < linha_O->tam ; ++i) {
            if(linha_O->array[i] == current->array[cel]){
                aux2++;
                count_global++;
            }
        }
        linha_O = linha_O->prev_node;
    }

    /// Verificar nas diagonais
    /// Diagonal Principal
    if(current->lin == current->col) {
        while (diag_prin_SE != NULL) {
            for (int i = 0; i < diag_prin_SE->tam; ++i) {
                if (diag_prin_SE->array[i] == current->array[cel]) {
                    aux3++;
                    count_global++;
                }
            }
            diag_prin_SE = diag_prin_SE->SE;
        }

        while (diag_prin_NO != NULL) {
            for (int i = 0; i < diag_prin_NO->tam; ++i) {
                if (diag_prin_NO->array[i] == current->array[cel]) {
                    aux3++;
                    count_global++;
                }
            }
            diag_prin_NO = diag_prin_NO->NO;
        }
    }

    /// Diagonal Secundária
    if((current->lin + current->col) == NUM -1 ) {
        while (diag_secu_SO != NULL) {
            for (int i = 0; i < diag_secu_SO->tam; ++i) {
                if (diag_secu_SO->array[i] == current->array[cel]) {
                    aux4++;
                    count_global++;
                }
            }
            diag_secu_SO = diag_secu_SO->SO;
        }

        while (diag_secu_NE != NULL) {
            for (int i = 0; i < diag_secu_NE->tam; ++i) {
                if (diag_secu_NE->array[i] == current->array[cel]) {
                    aux4++;
                    count_global++;
                }
            }
            diag_secu_NE = diag_secu_NE->NE;
        }
    }


    /// quadrado

    int lin_quad = current->lin - current->lin % raiz;
    int col_quad = current->col - current->col % raiz;
    int cel_num = (current->lin * NUM) + current->col; /// para verificar em todas as posicoes do quadrado menos nesta, porque nao vai verificar o proprio numero

    while (aux_quad->lin != lin_quad){ /// para quad chegar à celula do inicio do quadrado (lin)
        aux_quad = aux_quad->N;
    }
    while (aux_quad->col != col_quad){ /// para quad chegar à celula do inicio do quadrado (col)
        aux_quad = aux_quad->prev_node;
    }

    struct node * quad = aux_quad; /// node auxiliar que anda para sul a partir da 1 celula do quadrado

    for (int i = 0; i < raiz; i++) {
        for (int j = 0; j < raiz; j++) {
            int aux_cel_num = (quad->lin * NUM) + quad->col;
            if (cel_num != aux_cel_num) {
                for (int k = 0; k < quad->tam ; ++k) {
                    if ( quad->array[k] == current->array[cel] ) {
                        aux5++;
                        count_global++;
                    }
                }
            }
            quad = quad->pnext;
        }
        quad = aux_quad->S;
        aux_quad = aux_quad->S;
    }

    free(coluna_N);
    free(coluna_S);
    free(linha_E);
    free(linha_O);
    free(diag_prin_SE);
    free(diag_prin_NO);
    free(diag_secu_SO);
    free(diag_secu_NE);
    free(aux_quad);
    free(quad);


    if(aux1 == 0 || aux2 == 0 || (aux3 == 0 && current->lin == current->col ) || aux5 == 0 || (aux4 == 0 && ((current->lin + current->col) == NUM-1) )){ /// se contador permanecer a 1 é porque nao existe mais nenhum numero igual na linha,coluna,diagonal e quadrado
        return 1;
    }
    return 0;
}

void elimina_par_coluna(struct node *current){
    int count_aux=0,col_aux=0,remove_lin=0;
    struct node *par_coluna = current;
    int cel_num = (current->lin * NUM) + current->col; /// para verificar em todas as posicoes do quadrado menos nesta, porque nao vai verificar o proprio numero

    while (par_coluna->N != NULL){ /// faco o par coluna ir o maximo possivel para norte, para de seguida percorrer a coluna toda para sul e fazer as verificacoes
        par_coluna= par_coluna->N;
    }
    struct node *par_coluna_aux = par_coluna;

    while (par_coluna != NULL){ /// percorro a coluna
        int cel_par_coluna = (par_coluna->lin * NUM) + par_coluna->col;
        if(cel_par_coluna != cel_num){ /// verifico todas as celulas menos a celula do current
            if(par_coluna->tam == 2) { /// verifico se alguma das celulas da coluna do current tem tamanho 2
                if (*(current->array + 0) == *(par_coluna->array + 0) && *(current->array + 1) == *(par_coluna->array + 1)) { /// se tiver tamanho 2 verifico se é igual ao current
                    /// se for igual tenho de eliminar todos os numeros iguais na coluna
                    while (par_coluna_aux != NULL) {
                        int cel_par_coluna_aux = (par_coluna_aux->lin * NUM) + par_coluna_aux->col;
                        if(cel_par_coluna_aux != cel_par_coluna && cel_par_coluna_aux != cel_num) {
                            for (int j = 0; j < par_coluna_aux->tam; j++) {
                                if (*(par_coluna_aux->array + j) == *(current->array + 0) ||*(par_coluna_aux->array + j) == *(current->array +1)) { /// caso as as celulas da coluna possuem numeros iguais às celulas do current, elimina esses numeros
                                    *(par_coluna_aux->array +j) = 0; /// zero o numero que ia "eliminar" e passo-o para ultima posicao do array
                                    remove_lin = j + 1; /// porque j comeca em 0 e nao em 1
                                    count_aux = j; /// auxiliar para ajudar a colocar numero que pretendo eliminar na ultima posicao
                                    while (remove_lin <par_coluna_aux->tam) { /// para trocar até à ultima posicao do array
                                        col_aux = *(par_coluna_aux->array + count_aux + 1);
                                        *(par_coluna_aux->array + count_aux + 1) = *(par_coluna_aux->array + count_aux);
                                        *(par_coluna_aux->array + count_aux) = col_aux;
                                        count_aux++;
                                        remove_lin++;

                                        count_global++;
                                    }
                                    par_coluna_aux->tam = par_coluna_aux->tam - 1; /// removo uma posicao ao array
                                }
                            }
                        }
                        par_coluna_aux = par_coluna_aux->S;
                    }
                    break ; /// ja encontrou um par igual na coluna, nao precisa continuar a percorrer , visto que ja encontrou e nao pode encontrar mais nenhum para igual
                }
            }
        }
        par_coluna = par_coluna->S;
    }
    free(par_coluna);
    free(par_coluna_aux);
}

void elimina_par_linha(struct node *current){
    int count_aux=0,col_aux=0,remove_lin=0;
    struct node *par_linha = current;
    int cel_num = (current->lin * NUM) + current->col; /// para verificar em todas as posicoes do quadrado menos nesta, porque nao vai verificar o proprio numero

    while (par_linha->prev_node != NULL){ /// faco o par coluna ir o maximo possivel para norte, para de seguida percorrer a coluna toda para sul e fazer as verificacoes
        par_linha= par_linha->prev_node;
    }
    struct node *par_linha_aux = par_linha;

    while (par_linha != NULL){ /// percorro a coluna
        int cel_par_coluna = (par_linha->lin * NUM) + par_linha->col;
        if(cel_par_coluna != cel_num){ /// verifico todas as celulas menos a celula do current
            if(par_linha->tam == 2) { /// verifico se alguma das celulas da coluna do current tem tamanho 2
                if (*(current->array + 0) == *(par_linha->array + 0) && *(current->array + 1) == *(par_linha->array + 1)) { /// se tiver tamanho 2 verifico se é igual ao current
                    /// se for igual tenho de eliminar todos os numeros iguais na coluna
                    while (par_linha_aux != NULL) {
                        int cel_par_coluna_aux = (par_linha_aux->lin * NUM) + par_linha_aux->col;
                        if(cel_par_coluna_aux != cel_par_coluna && cel_par_coluna_aux != cel_num) {
                            for (int j = 0; j < par_linha_aux->tam; j++) {
                                if (*(par_linha_aux->array + j) == *(current->array + 0) ||*(par_linha_aux->array + j) == *(current->array +1)) { /// caso as as celulas da coluna possuem numeros iguais às celulas do current, elimina esses numeros
                                    *(par_linha_aux->array +j) = 0; /// zero o numero que ia "eliminar" e passo-o para ultima posicao do array
                                    remove_lin = j + 1; /// porque j comeca em 0 e nao em 1
                                    count_aux = j; /// auxiliar para ajudar a colocar numero que pretendo eliminar na ultima posicao
                                    while (remove_lin <par_linha_aux->tam) { /// para trocar até à ultima posicao do array
                                        col_aux = *(par_linha_aux->array + count_aux + 1);
                                        *(par_linha_aux->array + count_aux + 1) = *(par_linha_aux->array + count_aux);
                                        *(par_linha_aux->array + count_aux) = col_aux;
                                        count_aux++;
                                        remove_lin++;

                                        count_global++;
                                    }
                                    par_linha_aux->tam = par_linha_aux->tam - 1; /// removo uma posicao ao array
                                }
                            }
                        }
                        par_linha_aux = par_linha_aux->pnext;
                    }
                    break ; /// ja encontrou um par igual na coluna, nao precisa continuar a percorrer , visto que ja encontrou e nao pode encontrar mais nenhum para igual
                }
            }
        }
        par_linha = par_linha->pnext;
    }
    free(par_linha);
    free(par_linha_aux);
}

/// ELIMINA OS PARES NA DIAGONAL PRINCIPAL
void elimina_par_diag(struct node *current){
    int count_aux=0,col_aux=0,remove_lin=0;
    struct node *par_diag = current;
    int cel_num = (current->lin * NUM) + current->col; /// para verificar em todas as posicoes do quadrado menos nesta, porque nao vai verificar o proprio numero

    while (par_diag->NO != NULL){ /// faco o par coluna ir o maximo possivel para norte, para de seguida percorrer a coluna toda para sul e fazer as verificacoes
        par_diag = par_diag->NO;
    }
    struct node *par_diag_aux = par_diag;

    while (par_diag != NULL){ /// percorro a coluna
        int cel_par_coluna = (par_diag->lin * NUM) + par_diag->col;
        if(cel_par_coluna != cel_num){ /// verifico todas as celulas menos a celula do current
            if(par_diag->tam == 2) { /// verifico se alguma das celulas da coluna do current tem tamanho 2
                if (*(current->array + 0) == *(par_diag->array + 0) && *(current->array + 1) == *(par_diag->array + 1)) { /// se tiver tamanho 2 verifico se é igual ao current
                    /// se for igual tenho de eliminar todos os numeros iguais na coluna
                    while (par_diag_aux != NULL) {
                        int cel_par_coluna_aux = (par_diag_aux->lin * NUM) + par_diag_aux->col;
                        if(cel_par_coluna_aux != cel_par_coluna && cel_par_coluna_aux != cel_num) {
                            for (int j = 0; j < par_diag_aux->tam; j++) {
                                if (*(par_diag_aux->array + j) == *(current->array + 0) ||*(par_diag_aux->array + j) == *(current->array +1)) { /// caso as as celulas da coluna possuem numeros iguais às celulas do current, elimina esses numeros
                                    *(par_diag_aux->array +j) = 0; /// zero o numero que ia "eliminar" e passo-o para ultima posicao do array
                                    remove_lin = j + 1; /// porque j comeca em 0 e nao em 1
                                    count_aux = j; /// auxiliar para ajudar a colocar numero que pretendo eliminar na ultima posicao
                                    while (remove_lin <par_diag_aux->tam) { /// para trocar até à ultima posicao do array
                                        col_aux = *(par_diag_aux->array + count_aux + 1);
                                        *(par_diag_aux->array + count_aux + 1) = *(par_diag_aux->array + count_aux);
                                        *(par_diag_aux->array + count_aux) = col_aux;
                                        count_aux++;
                                        remove_lin++;

                                        count_global++;
                                    }
                                    par_diag_aux->tam = par_diag_aux->tam - 1; /// removo uma posicao ao array
                                }
                            }
                        }
                        par_diag_aux = par_diag_aux->SE;
                    }
                    break ; /// ja encontrou um par igual na coluna, nao precisa continuar a percorrer , visto que ja encontrou e nao pode encontrar mais nenhum para igual
                }
            }
        }
        par_diag = par_diag->SE;
    }
    free(par_diag);
    free(par_diag_aux);
}

/// ELIMINA PARES NA DIAGONAL SECUNDÁRIA
void elimina_par_diag_secun(struct node *current) {
    int count_aux=0,col_aux=0,remove_lin=0;
    struct node *par_diag = current;
    int cel_num = (current->lin * NUM) + current->col; /// para verificar em todas as posicoes do quadrado menos nesta, porque nao vai verificar o proprio numero

    while (par_diag->NE != NULL){ /// faco o par coluna ir o maximo possivel para norte, para de seguida percorrer a coluna toda para sul e fazer as verificacoes
        par_diag = par_diag->NE;
    }
    struct node *par_diag_aux = par_diag;

    while (par_diag != NULL){ /// percorro a coluna
        int cel_par_coluna = (par_diag->lin * NUM) + par_diag->col;
        if(cel_par_coluna != cel_num){ /// verifico todas as celulas menos a celula do current
            if(par_diag->tam == 2) { /// verifico se alguma das celulas da coluna do current tem tamanho 2
                if (*(current->array + 0) == *(par_diag->array + 0) && *(current->array + 1) == *(par_diag->array + 1)) { /// se tiver tamanho 2 verifico se é igual ao current
                    /// se for igual tenho de eliminar todos os numeros iguais na coluna
                    while (par_diag_aux != NULL) {
                        int cel_par_coluna_aux = (par_diag_aux->lin * NUM) + par_diag_aux->col;
                        if(cel_par_coluna_aux != cel_par_coluna && cel_par_coluna_aux != cel_num) {
                            for (int j = 0; j < par_diag_aux->tam; j++) {
                                if (*(par_diag_aux->array + j) == *(current->array + 0) ||*(par_diag_aux->array + j) == *(current->array +1)) { /// caso as as celulas da coluna possuem numeros iguais às celulas do current, elimina esses numeros
                                    *(par_diag_aux->array +j) = 0; /// zero o numero que ia "eliminar" e passo-o para ultima posicao do array
                                    remove_lin = j + 1; /// porque j comeca em 0 e nao em 1
                                    count_aux = j; /// auxiliar para ajudar a colocar numero que pretendo eliminar na ultima posicao
                                    while (remove_lin <par_diag_aux->tam) { /// para trocar até à ultima posicao do array
                                        col_aux = *(par_diag_aux->array + count_aux + 1);
                                        *(par_diag_aux->array + count_aux + 1) = *(par_diag_aux->array + count_aux);
                                        *(par_diag_aux->array + count_aux) = col_aux;
                                        count_aux++;
                                        remove_lin++;

                                        count_global++;
                                    }
                                    par_diag_aux->tam = par_diag_aux->tam - 1; /// removo uma posicao ao array
                                }
                            }
                        }
                        par_diag_aux = par_diag_aux->SO;
                    }
                    break ; /// ja encontrou um par igual na coluna, nao precisa continuar a percorrer , visto que ja encontrou e nao pode encontrar mais nenhum para igual
                }
            }
        }
        par_diag = par_diag->SO;
    }
    free(par_diag);
    free(par_diag_aux);
}

void elimina_par_quadrado(struct node *current){
    int raiz = sqrt(NUM),count_aux=0,col_aux=0,remove_lin=0;;
    int lin_quad = current->lin - current->lin % raiz;
    int col_quad = current->col - current->col % raiz;
    int cel_num = (current->lin * NUM) + current->col; /// para verificar em todas as posicoes do quadrado menos nesta, porque nao vai verificar o proprio numero
    struct node *aux_quad = current;

    while (aux_quad->lin != lin_quad){ /// para quad chegar à celula do inicio do quadrado (lin)
        aux_quad = aux_quad->N;
    }
    while (aux_quad->col != col_quad){ /// para quad chegar à celula do inicio do quadrado (col)
        aux_quad = aux_quad->prev_node;
    }

    struct node * quad = aux_quad; /// node auxiliar que anda para sul a partir da 1 celula do quadrado
    struct node * aux_quad_sul = aux_quad;
    struct node *quad_current = aux_quad;

    for (int i = 0; i < raiz; i++) {
        for (int j = 0; j < raiz; j++) {
            int cel_par_coluna = (quad->lin * NUM) + quad->col;
            if(cel_par_coluna != cel_num){ /// verifico todas as celulas menos a celula do current
                if(quad->tam == 2) { /// verifico se alguma das celulas da coluna do current tem tamanho 2
                    if (*(current->array + 0) == *(quad->array + 0) && *(current->array + 1) == *(quad->array + 1)) { /// se tiver tamanho 2 verifico se é igual ao current
                        /// se for igual tenho de eliminar todos os numeros iguais no quadrado ( para isso tenho de voltar a percorrer o quadrado )
                        for (int k = 0; k < raiz ; k++) {
                            for (int l = 0; l < raiz ; l++) {
                                int cel_par_coluna_aux = (quad_current->lin * NUM) + quad_current->col;
                                if (cel_par_coluna_aux != cel_par_coluna && cel_par_coluna_aux != cel_num) {
                                    for (int r = 0; r < quad_current->tam; r++) {
                                        if (*(quad_current->array + r) == *(current->array + 0) || *(quad_current->array + r) == *(current->array +1)) { /// caso as as celulas da coluna possuem numeros iguais às celulas do current, elimina esses numeros*(quad_current->array +j) = 0; /// zero o numero que ia "eliminar" e passo-o para ultima posicao do array
                                            remove_lin = r + 1; /// porque j comeca em 0 e nao em 1
                                            count_aux = r; /// auxiliar para ajudar a colocar numero que pretendo eliminar na ultima posicao
                                            while (remove_lin < quad_current->tam) { /// para trocar até à ultima posicao do array
                                                col_aux = *(quad_current->array + count_aux + 1);
                                                *(quad_current->array + count_aux + 1) = *(quad_current->array + count_aux);
                                                *(quad_current->array + count_aux) = col_aux;
                                                count_aux++;
                                                remove_lin++;

                                                count_global++;
                                            }
                                            quad_current->tam = quad_current->tam - 1; /// removo uma posicao ao array
                                        }
                                    }
                                }
                                quad_current = quad_current->pnext;
                            }
                            quad_current = aux_quad_sul->S;
                            aux_quad_sul = aux_quad_sul->S;
                        }
                        return ; /// ja encontrou um par igual na coluna, nao precisa continuar a percorrer , visto que ja encontrou e nao pode encontrar mais nenhum para igual
                    }
                }
            }
            quad = quad->pnext;
        }
        quad = aux_quad->S;
        aux_quad = aux_quad->S;
    }

    free(quad);
    free(quad_current);
    free(aux_quad);
    free(aux_quad_sul);
}

void pares_sozinhos (struct node * head){
    struct node *current = head;
    struct node * sul = head;
    /// verifico se o current tem tamanho 2
    while (sul != NULL) {
        while (current != NULL) {
            if (current->tam == 2) {
                elimina_par_coluna(current);
                elimina_par_linha(current);
                if(current->lin == current->col) {
                    elimina_par_diag(current);
                }
                if ((current->lin + current->col) == NUM - 1) { /// so pode ver as diagonais secundarias se (lin +col ) == N-1
                    elimina_par_diag_secun(current);
                }
                elimina_par_quadrado(current);
            }
            current = current->pnext;
        }
        current = sul->S;
        sul = sul->S;
    }
    free(current);
    free(sul);
}

/**
 * @param aux_matriz
 * @param aux
 * @param tam
 * @param matriz
 */
int resolver_matriz(struct node *head){
    struct node * current = head;
    struct node *current_sul = head;
    struct node *current_aux = head;
    struct node *current_sul_aux = head;

    struct node *saltar_este = head;
    struct node *saltar_sul = head;

    int k = 0; /// ser ve para percorrer o array da matriz 3 dimensional
    int count=0;
    while(count != num_zeros) { /// para estar sempre a repetir as funcoes até a matriz estar toda resolvida
        mudar_algoritmo = 0;
        count =0;

        while (current_sul != NULL ){
            while (current != NULL){
                if(current->tam == 1 && current->array[0] != 0) {
                    remover_numero(current,0,head); /// zero porque porque so existe o numero no array, entao esse numero está na posicao 0
                    mudar_algoritmo ++;
                }
                if (*(current->array +0) != 0 && current->tam > 1) { /// se nao estiver sozinho na celula, para eliminar numeros temos de verificar o numero oculto sozinho
                    for (k = 0; k < current->tam ; k++) {
                        if (verifica_oculto(current, k) == 1) {
                            remover_numero(current,k,head);
                            mudar_algoritmo ++;
                        }
                    }
                    while (current_sul_aux != NULL){
                        while (current_aux != NULL){
                            if(current_aux->tam == 1 && current_aux->array[0] != 0) {
                                remover_numero(current_aux,0,head); /// zero porque porque so existe o numero no array, entao esse numero está na posicao 0
                                mudar_algoritmo ++;
                            }
                            current_aux = current_aux->pnext;
                        }
                        current_aux = current_sul_aux->S;
                        current_sul_aux = current_sul_aux->S;
                    }
                }
                pares_sozinhos(head);
                current = current->pnext;

                current_aux = head;
                current_sul_aux = head;

            }
            current = current_sul->S;
            current_sul = current_sul->S;
        }

        /// ciclo que percorre array aux, que possui o tamanho de cada celula da matriz, quando todas as celulas tiverem tamanho 1 pode sair desta funcao
        while(saltar_sul != NULL) {
            while(saltar_este != NULL) {
                count = count + saltar_este->tam;
//                if(saltar_este->tam == 0){ /// quando entra aqui, quer dizer que o sudoku é impossivel de resolver, a matriz de tamanhos nunca pode ter tamanho 0
//                    return 0;
//                }
                saltar_este = saltar_este->pnext;
            }
            saltar_este = saltar_sul->S;
            saltar_sul = saltar_sul->S;
        }
        if( mudar_algoritmo == 0){
            break;
        }

        /// tenho de voltar a iniciar, porque tem de voltar a percorrer do 0
        current = head;
        current_sul = head;
    }

    free(current);
    free(current_sul);
    free(current_aux);
    free(current_sul_aux);
    free(saltar_este);
    free(saltar_sul);

    return 1;
}

/**
 *
 * @param matriz
 * @return
 */
int alg_sudoku(struct node **head, int ***memoria){ /// só falta realocar espaco, para nao estar sempre a alocar espaco desnecessario (espaco a mais )
    struct node *pcs = *head;
    struct node *current = *head;

    struct node *sudoku = *head;

    count_global = 0; /// sempre que algoritmo é chamado o contador global tem de ser zerado
    int lin=0,col=0;
    /// percorre os zeros todos da matriz e em cada zero vai verificar os numeros possiveis
    while(pcs != NULL) {
        while(current != NULL) {
            current->lin = lin;
            current->col = col;
            if(current->data != 0){ /// quando nao for 0 vai receber os valores da matriz
                current->array[0] = current->data;
            }
            else if (current->data == 0) { /// aux_matriz aonde for 0 vai tomar os valores possveis
                numeros_possiveis(current);
                num_zeros++; /// para saber quantos 0 sao para de seguida saber quando devo para de fazer o ciclo que faz o sudoku_
            }
            current = current->pnext;
            col++;
        }
        current = pcs->S;
        pcs = pcs->S;
        lin++;
        col=0;
    }

    if(resolver_matriz(sudoku) == 0){
        return 0;
    }

    free(pcs);
    free(current);
    free(sudoku);
    return 1;
}


int main_projeto(int argc, char **argv){
    struct node *head = NULL;
    int *** memoria = NULL;
    clock_t inicio, fim;
    double tempoexec;

    ///R9 - Leitura dos tabuleiros de números a partir de um ficheiro de texto; PARA JÁ SÓ CARREGA 1, PARA CARREGAR MAIS TEMOS DE FAZER A FILA
//       carregar_matriz(&head);
//       imprimirSudoku(head);
//       free(head);

    ///R12 - Permitir resolver o problema com abordagens brute-force, encontrando as soluções possíveis para os tabuleiros;
//    printf("\n\nBrute Force :\n\n");
//    carregar_matriz(&head);
//    if (sudoku(head) == 1) {
//        imprimirSudoku(head);
//        printf("\n\ncontador: %d\n",count_global);
//        count_global = 0;
//    }
//    else {
//        printf("Sudoku Impossivel de Resolver !!! ");
//    }
//    free(head);

    /// R13 - implementando estratégias que melhorem a eficiência na pesquisa de uma solução, algoritmo melhorado
//    head = NULL;
//    printf("Algoritmo melhorado :\n\n");
//    carregar_matriz(&head);
//    if (alg_sudoku(&head,memoria) == 1 ) {
//        imprimirSudoku(head);
//        printf("\n\ncontador: %d\n",count_global);
//        count_global = 0;
//    } else{
//        printf("Sudoku Impossivel de Resolver !!! ");
//    }
//    free(head);

    /// Analisar e comparar as duas abordagens
    ///BruteForce:
    printf("\n\nBrute Force :\n\n");
    head = NULL;
    carregar_matriz(&head);
    inicio = clock();
    if (sudoku(head) == 1) {
        imprimirSudoku(head);
        printf("\n\ncontador: %d\n",count_global);
        count_global = 0;
        fim = clock();
        tempoexec = ((double) (fim - inicio)) / CLOCKS_PER_SEC;
        printf("Com o algoritmo brute-force a resolucao do tabuleiro foi de: %g segundos.\n\n\n", tempoexec);
    }
    else {
        printf("Sudoku Impossivel de Resolver !!! ");
    }

    free(head);

    /// Algoritmo melhorado:
    printf("Algoritmo melhorado :\n\n");
    head = NULL;
    carregar_matriz(&head);
    inicio = clock();
    if (alg_sudoku(&head,memoria) == 1 ) {
        imprimirSudoku(head);
        printf("\n\ncontador: %d\n",count_global);
        count_global = 0;
        fim = clock();
        tempoexec = ((double) (fim - inicio)) / CLOCKS_PER_SEC;
        printf("Com o algoritmo melhorado a resolucao do tabuleiro foi de: %g segundos.\n\n\n", tempoexec);
    } else{
        printf("Sudoku Impossivel de Resolver !!! ");
    }
    guardar_matriztxt(head);
    guardar_matrizbin(head);
    free(head);
    /// R14 e R15. Permitir gravar para ficheiros de texto e binário as soluções encontradas. AINDA NAO ESTÁ FEITO COM LINKED LIST !!!!!!!!!!!!!!!

//  matriz = matriz_aleatoria();
//  alg_sudoku(matriz);
//  imprimirSudoku(matriz);
//  guardar_matriztxt(matriz);
//  guardar_matrizbin(matriz);
//  free(matriz);
}