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
Brute force jak już...
Ma być z przycinaniem czy zwykły backtracking?
z przycinaniem znaczy jak??
Wiem jedynie że metoda brute force polega na badaniu każdej możliwości do skutku
http://www.codeproject.com/KB/recipes/Magic_Square.aspx
http://user.chollian.net/~brainstm/source.htm
bo mało jest o tym informacji w internecie o_O''
nawet bardzo mało
wielkie dzięki za te linki. Pozdrawiam [browar]
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;
}
Zarejestruj się i dołącz do największej społeczności programistów w Polsce.
Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.