023
09.01.2009, 21:28 Uhr
0xdeadbeef
Gott
(Operator)
|
Okay, in verkürzter Form (den Listenkram habe ich in ein eigenes Modul ausgelagert, ist aber unverändert:
| C++: |
#include "clist.h"
#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;
static char delim_line[DIMENSION * 2 + 6] = "\n +";
void init_delim_line(void) {
size_t i;
for(i = 0; i < DIMENSION; ++i) {
strcpy(delim_line + i * 2 + 5, "-+");
}
}
void print_loesung(damen const *d) {
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 backtrack_damen(damen *d, clist *left_y, unsigned *count, int *diag_lu, int *diag_rd) {
cnode *p;
int depth = d->size;
if(d->size == DIMENSION) {
++*count;
print_loesung(d);
}
for(p = left_y->head->next; p != left_y->tail; p = p->next) {
int dlu = depth - p->val + DIMENSION;
int drd = depth + p->val;
if(!diag_lu[dlu] &&
!diag_rd[drd]) {
d->y[d->size] = p->val;
++d->size;
detach_node(p);
diag_lu[dlu] = 1;
diag_rd[drd] = 1;
backtrack_damen(d, left_y, count, diag_lu, diag_rd);
diag_lu[dlu] = 0;
diag_rd[drd] = 0;
attach_node(p);
--d->size;
}
}
}
int main(void) {
clist coords_y;
int i;
damen d = { { 0 }, 0 };
unsigned counter = 0;
int diag [DIMENSION * 2] = { 0 },
diag2[DIMENSION * 2] = { 0 };
init_delim_line();
create_clist(&coords_y);
for(i = 0; i < DIMENSION; ++i) {
clist_push(&coords_y, i);
}
backtrack_damen(&d, &coords_y, &counter, diag, diag2);
printf("%u\n", counter);
destroy_clist(&coords_y);
return 0;
}
|
Das schlägt deine Implementierung noch mal um ein paar Sekunden (24,358 gegenüber 33,422 bei DIMENSION=15, Varianz möglich). Falls du dich wunderst, warum mein verwursteter Listenkram Performance rausholt, er skaliert besser mit der Ebenentiefe - du hast mit dem Durchlaufen sämtlicher Koordinaten linearen Aufwand.
Nachtrag: Übrigens wird ein 16x16-Brett jetzt erschwinglich - 3:50 für dich, 2:34 für mich mit der von dir (bzw. Nemo) geklauten Idee.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra
Dieser Post wurde am 09.01.2009 um 21:40 Uhr von 0xdeadbeef editiert. |
Naja, also, wie ich es jedenfalls getan habe, eine Koordinatenliste in C geschrieben, die es mir erlaubt, Nodes aus- und wieder einzuhängen.
