010
09.01.2009, 12:50 Uhr
0xdeadbeef
Gott
(Operator)
|
So, dass das Durchlaufen der noch vorhandenen Kandidaten da oben linear skaliert, bloß, weil ich meine Iteratoren verliere, kann ich nicht auf mir sitzen lassen. Dementsprechend habe ich, wie es wohl jeder in meiner Situation täte...  Naja, also, wie ich es jedenfalls getan habe, eine Koordinatenliste in C geschrieben, die es mir erlaubt, Nodes aus- und wieder einzuhängen. Hier das Ergebnis meines Wahnsinns:
| C++: |
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#ifndef DIMENSION
#define DIMENSION (8)
#endif
typedef struct {
int y[DIMENSION];
size_t size;
} damen;
typedef struct {
damen *states;
size_t size;
} loesungen;
typedef struct coord_node {
int val;
struct coord_node *prev, *next;
} cnode;
typedef struct coord_list {
cnode *head, *tail;
} clist;
void create_clist(clist *ls) {
ls->head = malloc(sizeof(cnode));
ls->tail = malloc(sizeof(cnode));
ls->head->prev = ls->tail->prev = ls->head;
ls->head->next = ls->tail->next = ls->tail;
}
void destroy_clist(clist *ls) {
while(ls->head->next != ls->tail) {
cnode *p = ls->head->next;
ls->head->next = ls->head->next->next;
ls->head->next->prev = ls->head;
free(p);
}
free(ls->head);
free(ls->tail);
}
void detach_node(cnode *node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
void attach_node(cnode *node) {
node->prev->next = node;
node->next->prev = node;
}
void clist_push(clist *ls, int val) {
cnode *node = malloc(sizeof(cnode));
node->val = val;
node->prev = ls->tail->prev;
node->next = ls->tail;
attach_node(node);
}
int try_dame(damen *d, int x, int y) {
int i;
for(i = 0; i < (int) d->size; ++i) {
if(abs(i - x) == abs(d->y[i] - y)) {
return 0;
}
}
return 1;
}
void backtrack_damen(damen *d, clist *left_y, loesungen *l) {
cnode *p;
if(d->size == DIMENSION) {
l->states = realloc(l->states, (l->size + 1) * sizeof(damen));
l->states[l->size] = *d;
++l->size;
}
for(p = left_y->head->next; p != left_y->tail; p = p->next) {
if(try_dame(d, d->size, p->val)) {
d->y[d->size] = p->val;
++d->size;
detach_node(p);
backtrack_damen(d, left_y, l);
attach_node(p);
--d->size;
}
}
}
void print_loesung(damen const *d, char const *delim_line) {
int i, j;
printf(" ");
for(i = 0; i < DIMENSION; ++i) {
printf("%2d", i + 1);
}
puts(delim_line);
for(i = 0; i < DIMENSION; ++i) {
printf("%2d |", i + 1);
for(j = 0; j < DIMENSION; ++j) {
printf("%c|", d->y[i] == j ? 'D' : ' ');
}
puts(delim_line);
}
puts("");
}
void print_loesungen(loesungen *l) {
char delim_line[DIMENSION * 2 + 6] = "\n +";
size_t i;
for(i = 0; i < DIMENSION; ++i) {
strcpy(delim_line + i * 2 + 5, "-+");
}
for(i = 0; i < l->size; ++i) {
print_loesung(&l->states[i], delim_line);
}
}
int main(void) {
clist coords_y;
int i;
damen d = { { 0 }, 0 };
loesungen l = { NULL, 0 };
create_clist(&coords_y);
for(i = 0; i < DIMENSION; ++i) {
clist_push(&coords_y, i);
}
backtrack_damen(&d, &coords_y, &l);
print_loesungen(&l);
printf("%lu\n", l.size);
destroy_clist(&coords_y);
free(l.states);
return 0;
}
|
Ich bin mir bewusst, dass die Speicherverwaltung des Lösungsvektors suboptimal ist, aber ich war stumpf zu faul, dafür nun noch großen Aufwand zu betreiben. Vielleicht später.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra
Dieser Post wurde am 09.01.2009 um 12:58 Uhr von 0xdeadbeef editiert. |
)