Program szukający magicznych kwadratów

0

Witam wszystkich, goszczę na forum pierwszy raz. Jestem trochę zielony w C a muszę napisać program który szuka magicznych kwadratów o boku podanym przez użytkownika metodą brutal force. Mam problem ze znalezieniem sposobu który gwarantuje przeszukanie wszystkich możliwości. Proszę o pomoc w znalezieniu takiego sposobu. Z góry dzięki

0

Brute force jak już...
Ma być z przycinaniem czy zwykły backtracking?

0

z przycinaniem znaczy jak??

0

Wiem jedynie że metoda brute force polega na badaniu każdej możliwości do skutku

0

nawet bardzo mało
wielkie dzięki za te linki. Pozdrawiam [browar]

0

Z ciekawości napisałem chamskiego brute force'a bez żadnego przycinania, żeby zobaczyć przy jakiej dlugosci kwadratu wymięknie. Wymiękł dla 4 (dla 3 jeszcze działa). Tak więc jeżeli chcesz brute force dla większych n to tylko z przycinaniem.

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

#define MAX_CANDIDATES 10

#define TRUE  1
#define FALSE 0



int map2(int x, int y, int n) {
        int index = x * n + y;
        assert(index < n*n);
        return index;
}

int is_solution(int* partial, int n, int k) {
        int i = 0, j = 0;
        int s = 0, sum = 0;
        if(n*n == k) {
                for(j = 0;  j < n; j++) {
                        s += partial[map2(i, j, n)];
                }
                sum = s;
                for(i = 0; i < n; i++) {
                        s = 0;
                        for(j = 0;  j < n; j++) {
                                s += partial[map2(i, j, n)];
                        }
                        if(s != sum) {
                                return FALSE;
                        }
                }
                for(i = 0; i < n; i++) {
                        s = 0;
                        for(j = 0;  j < n; j++) {
                                s += partial[map2(j, i, n)];
                        }
                        if(s != sum) {
                                return FALSE;
                        }
                }
                s = 0;
                for(i = 0; i < n; i++) {
                        s += partial[map2(i, i, n)];
                }
                if(s != sum) {
                        return FALSE;
                }
                s = 0;
                for(i = 0; i < n; i++) {
                        s += partial[map2(n-i-1, i, n)];
                }
                if(s != sum) {
                        return FALSE;
                }
        } else {
                return FALSE;
        }
        return TRUE;
}

void process_solution(int* partial, int n, int k) {
        int i = 0, j = 0;
        for(i = 0; i < n; i++) {
                for(j = 0; j < n; j++) {
                        printf("%2d", partial[map2(i, j, n)]);
                }
                printf("\n");
        }
        printf("\n");
        fflush(stdout);
}

int gen_candidates(int *candidates, int* partial, int n, int k) {
        int i = 0;
        int res = 0;
        static int used[MAX_CANDIDATES+1];
        memset(used, FALSE, (MAX_CANDIDATES+1) * sizeof(int));

        if(k < n*n) {
                for(i = 0; i < n; i++) {
                        used[partial[i]] = TRUE;
                }
                for(i = 0; i < MAX_CANDIDATES; i++) {
                        if(used[i] == FALSE) {
                                candidates[res] = i;
                                res++;
                        }
                }
        }

        return res;
}

void construct_solution(int *partial, int n, int k, int c) {
        partial[k] = c;
}

int backtrack(int *partial, int n, int k, int* count) {
        int i = 0, nc = 0;
        int candidates[MAX_CANDIDATES];

        //process_solution(partial, n, k);
        //getch();

        if(is_solution(partial, n, k) == TRUE) {
                process_solution(partial, n, k);
                (*count)++;
        } else {
                memset(candidates, 0, MAX_CANDIDATES * sizeof(int));

                nc = gen_candidates(candidates, partial, n, k);
                /*printf("Cand: ");
                for( i = 0; i < nc; i++) {
                        printf("%d", candidates[i]);
                }
                printf("\n"); */
                for(i = 0; i < nc; i++) {
                        construct_solution(partial, n, k, candidates[i]);
                        backtrack(partial, n, k+1, count);
                }
        }

        return 0;
}

int main(int argc, char* argv[])
{
        int count = 0, i = 0, j = 0;
        int n = 0;
        int* partial = NULL;
        scanf("%d", &n);

        partial = (int*)malloc(n * n * sizeof(int));
        memset(partial, 0, n * n * sizeof(int));

        backtrack(partial, n, 0, &count);

        printf("\ncount: %d", count);

        free(partial);

        return 0;
}

1 użytkowników online, w tym zalogowanych: 0, gości: 1