Herzlich Willkommen, lieber Gast!
  Sie befinden sich hier:

  Forum » Rätselecke » @virtual: Geburtstagsrätsel

Forum | Hilfe | Team | Links | Impressum | > Suche < | Mitglieder | Registrieren | Einloggen
  Quicklinks: MSDN-Online || STL || clib Reference Grundlagen || Literatur || E-Books || Zubehör || > F.A.Q. < || Downloads   

Autor Thread - Seiten: [ 1 ] > 2 < [ 3 ]
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.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
011
09.01.2009, 13:57 Uhr
FloSoft
Medialer Over-Flow
(Administrator)


jetzt wärs interessant wies mit den zeiten von den verschiedenen lösungen aussieht, also wie lange se brauchen um die lösungen auszuspucken
--
class God : public ChuckNorris { };
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
012
09.01.2009, 18:32 Uhr
kronos
Quotenfisch
(Operator)


Beefz und meine Lösung (z-taste kaputt, sorrz) bleiben bis n=12 und 1s.
Für n=13 braucht beefz 1.7s und ich 4.3.
Auf n=14 will ich jetzt nich warten.
Wenn man nur eine Lösung sucht braucht mab bis 19 nur ein paar Sekunden (das osziliert natürlich ein bischen über die verschiedenen n).

Hier ist mein Code, macht eigentlich das selbe, wüsste gerne warum der so viel langsamer ist!!
Die Print-Methoden hab' ich zum Zeit nehemen 'rausgestrichen.


C++:
#include<iostream>
#include<vector>
#include<list>
#include<cstdlib>

class DameStack
{
    private:
        static const int n=8;
        std::vector<int> damen;
        std::list<int> zeilen;

        void output()
        {
            for(int i=0;i<n;++i)
            {
                for(int j=0;j<n;++j)
                    std::cout << '|'
                        << ((damen[i]==j)?'D':(i+j)&1?' ':'#');
                std::cout<<'|'<<std::endl;
            }
            std::cout<<std::endl;
        }

        bool bedroht(int c, int z)
        {
            for(int d=0;d<c;++d)
                if(abs(damen[d]-z)==c-d)
                    return true;
            return false;
        }


    public:
        DameStack():damen(n)
        {
            for(int i=0;i<n;++i) zeilen.push_back(i);
        }

        void loese(int c=0)
        {
            if(c==n)
                 output();
            else
                for(std::list<int>::iterator zit=zeilen.begin();zit!=zeilen.end();++zit)
                {
                    int z=*zit;
                    if(bedroht(c,z))
                            continue;
                    damen[c]=z;
                    zit=zeilen.erase(zit);
                    loese(c+1);
                    zit=zeilen.insert(zit,z);
                }
        }
};

int main()
{
    DameStack().loese();
}



Ist aufgrund konvergenter Evolution inhaltlich das selbe wie der von 0xdeadbeef und formell an virtual angelehnt, da ich's eigentlich mit dessen Implementierung vergleichen wollte...
--
main($)??<-$<='?'>>2?main($-!!putchar(
(("$;99M?GD??(??/x0d??/a:???;a"+'?'/4)
??($??)+'?'/3-2-1+$%2)??''?')):'?';??>

Dieser Post wurde am 09.01.2009 um 20:17 Uhr von kronos editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
013
09.01.2009, 18:35 Uhr
0xdeadbeef
Gott
(Operator)


Bei einer Brettgröße von 8 ist das nicht sinnvoll benchmarkbar - auf meiner schon etwas älteren Maschine läuft das C-Ding in 0,005 Sekunden durch, während ein Browser und ein DVB-T-Empfangsprogramm laufen, virtual's Code gerade eben in 0,012 - aber bei derart kurzen Laufzeiten fällt eine so kleine Marge in den Bereich statistischen Weißrauschens. Ich müsste virtuals Code auf eine Brettgröße von 15 umklamüsern, um in eine einigermaßen verlässlich messbare Größenordnung zu kommen.

Nachtrag: Möglicherweise sogar 16; für Brettgröße 15 brauchte ich hier eben knapp zweieinhalb Minuten.

Nachtrag 2: @kronos: Vorsicht, du läufst da in die selbe Iteratorgültigkeitsfalle, in die ich zuerst gefallen bin. Das Element, auf das zit bei rekursiven Aufruf von loese zeigt, wird womöglich in der nächsten Rekursionsebene gelöscht, wodurch zit ungültig wird.

Nachtrag 3: Brettgröße 16 krieg ich hier in endlicher Zeit nicht raus - das Speichern der Lösungen allein frisst etwa 600 Megabyte RAM, da fängt er mir an, zu swappen.

Nachtrag 4: Virtuals Code war ja dankenswerterweise sehr einfach umzuklamüsern. Also, bei Brettgröße 15 rechnet der obrige C-Code 2 Minuten und 23 Sekunden, virtuals C++-Programm 5 Minuten und 42 Sekunden. Ich habe das jetzt (aus offensichtlichen Gründen) nicht häufig wiederholt, kann also keinen Anspruch auf Genauigkeit erheben, aber die Größenordnung dürfte so stimmen.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Dieser Post wurde am 09.01.2009 um 19:04 Uhr von 0xdeadbeef editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
014
09.01.2009, 19:15 Uhr
kronos
Quotenfisch
(Operator)



Zitat von 0xdeadbeef:
Nachtrag 2: @kronos: Vorsicht, du läufst da in die selbe Iteratorgültigkeitsfalle, in die ich zuerst gefallen bin. Das Element, auf das zit bei rekursiven Aufruf von loese zeigt, wird womöglich in der nächsten Rekursionsebene gelöscht, wodurch zit ungültig wird.

Klingt vernünftig... wieso funktioniert's dann trotzdem? Er findet alle Lösungen, ist bloß ein bischen lahm...
--
main($)??<-$<='?'>>2?main($-!!putchar(
(("$;99M?GD??(??/x0d??/a:???;a"+'?'/4)
??($??)+'?'/3-2-1+$%2)??''?')):'?';??>
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
015
09.01.2009, 19:30 Uhr
0xdeadbeef
Gott
(Operator)


Warum das manchmal funktioniert, ist eine gute Frage. Vermutlich hängt es mit der Heap-Speicherverwaltung des Compilers sowie der Tatsache zusammen, dass das Löschen des Elementes den Speicher nicht überschreibt, und, sofern dadurch kein Segfault ausgelöst wird oder der Speicher zwischenzeitlich anders verwendet wurde, der Iterator durch den Zugriff auf den ungültigen, aber nicht überschriebenen Speicher die selben prev- und next-Zeiger erhält, die er auch erhielte, wenn er noch gültig wäre. Das ist allerdings geraten - sicher sagen kann ich dir das nicht. Es ist ein merkwürdiger Zufall.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
016
09.01.2009, 20:02 Uhr
kronos
Quotenfisch
(Operator)


Ok, ich leg mal nach:

C++:
#include<string.h>
#include<stdio.h>
#define n 16

int damen[n],
    zeilen[n],
    diag1[2*n],
    diag2[2*n];

void output()
{return;
    int i,j;
    for(i=0;i<n;++i)
    {
        for(j=0;j<n;++j)
            printf("|%c",(damen[i]==j)?'D':(i+j)&1?' ':'#');
        puts("|");            
    }
    puts("");
}

void loese(int c)
{
    int z;
     if(c==n)
         output();
     else
         for(z=0;z<n;++z)
         {
             if(zeilen[z]||diag1[c-z+n]||diag2[c+z-n])
                 continue;
             damen[c]=z;
             zeilen[z]=1;
             diag1[c-z+n]=1;
             diag2[c+z-n]=1;

             loese(c+1);
            
             zeilen[z]=0;
             diag1[c-z+n]=0;
             diag2[c+z-n]=0;
        }
}

int main()
{
    memset(zeilen,0,n);
    loese(0);
}


n=15 in 13s, n=16 in 1min 10s @1.7GHz
--
main($)??<-$<='?'>>2?main($-!!putchar(
(("$;99M?GD??(??/x0d??/a:???;a"+'?'/4)
??($??)+'?'/3-2-1+$%2)??''?')):'?';??>

Dieser Post wurde am 09.01.2009 um 20:33 Uhr von kronos editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
017
09.01.2009, 20:16 Uhr
0xdeadbeef
Gott
(Operator)


Das findet aber für n = 15 nur 16.792 Lösungen, obwohl 2.279.184 existieren...

(Übrigens wäre ich zunächst weit weniger verwirrt gewesen, hättest du das return; am Anfang von output vor dem Posten entfernt... )

Was mich angeht, ich habe in der Zwischenzeit eine etwas intelligentere Speicherverwaltung für die Lösungen implementiert, komme damit runter auf 2 Minuten und 1 Sekunde. für ein 15x15-Brett. Vielleicht sollte ich auf die Speicherung stumpf verzichten und einfach nacheinander ausgeben.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Dieser Post wurde am 09.01.2009 um 20:19 Uhr von 0xdeadbeef editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
018
09.01.2009, 20:35 Uhr
0xdeadbeef
Gott
(Operator)


Okay, also wie folgt:

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 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);
}

void init_delim_line(char *delim_line) {
  size_t i;

  for(i = 0; i < DIMENSION; ++i) {
    strcpy(delim_line + i * 2 + 5, "-+");
  }
}

char const *delim_line(void) {
  static char delim_line[DIMENSION * 2 + 6] = "\n   +";
  static int inited = 0;

  if(!inited) {
    inited = 1;
    init_delim_line(delim_line);
  }

  return delim_line;
}

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("");
}

int try_dame(damen *d, int x, int y) {
  int i;

  for(i = 0; i < (int) d->size; ++i) {
    if(x - i == abs(d->y[i] - y)) {
      return 0;
    }
  }

  return 1;
}

void backtrack_damen(damen *d, clist *left_y, unsigned *count) {
  cnode *p;

  if(d->size == DIMENSION) {
    ++*count;
    print_loesung(d);
  }

  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, count);

      attach_node(p);
      --d->size;
    }
  }
}

int main(void) {
  clist coords_y;
  int i;
  damen d = { { 0 }, 0 };
  unsigned counter = 0;

  create_clist(&coords_y);

  for(i = 0; i < DIMENSION; ++i) {
    clist_push(&coords_y, i);
  }

  backtrack_damen(&d, &coords_y, &counter);

  printf("%lu\n", counter);

  destroy_clist(&coords_y);

  return 0;
}


Mit auskommentierter Ausgabe kommt das für DIMENSION=15 auf 53 Sekunden auf einem Athlon 64 3200+ (2GHz). Der scheint vergleichbar schnell mit kronos Rechner zu sein, allerdings können (und auch dann nur bedingt) faire Vergleiche natürlich nur auf der gleichen Maschine gemessen werden. Oder ich müsste meinen Profiler entstauben...

Mit globalen Variablen ließe sich da u.U. noch ein bisschen was reißen, aber das widerstrebt mir nun wirklich zu sehr.

Nachtrag: Die Liste werde ich mir übrigens wohl aufheben - das könnte irgendwann noch mal nützlich sein.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Dieser Post wurde am 09.01.2009 um 20:45 Uhr von 0xdeadbeef editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
019
09.01.2009, 20:56 Uhr
kronos
Quotenfisch
(Operator)


Ups, ja da waren noch ein paar Macken drin. Nun aber:

C++:
#include<string.h>
#include<stdio.h>
#define n 15

int damen[n],
    zeilen[n],
    diag1[2*n],
    diag2[2*n],
    loesungen;

void output()
{
    ++loesungen; return;
    int i,j;
    for(i=0;i<n;++i)
    {
        for(j=0;j<n;++j)
            printf("|%c",(damen[i]==j)?'D':(i+j)&1?' ':'#');
        puts("|");            
    }
    puts("");
}

void loese(int c)
{
    int z;
     if(c==n)
         output();
     else
         for(z=0;z<n;++z)
         {
             if(zeilen[z]||diag1[c-z+n]||diag2[c+z])
                 continue;
             damen[c]=z;
             zeilen[z]=1;
             diag1[c-z+n]=1;
             diag2[c+z]=1;

             loese(c+1);
            
             zeilen[z]=0;
             diag1[c-z+n]=0;
             diag2[c+z]=0;
        }
}

int main()
{
    memset(zeilen,0,n);
    memset(diag1,0,2*n);
    memset(diag2,0,2*n);
    loese(0);
    printf("%d\n",loesungen);
}


Ist bei n=15 immer noch fast doppelt so schnell.
--
main($)??<-$<='?'>>2?main($-!!putchar(
(("$;99M?GD??(??/x0d??/a:???;a"+'?'/4)
??($??)+'?'/3-2-1+$%2)??''?')):'?';??>

Dieser Post wurde am 09.01.2009 um 20:57 Uhr von kronos editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
Seiten: [ 1 ] > 2 < [ 3 ]     [ Rätselecke ]  


ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: