Fun-Soft - Programmierforum

Autor

Thread - Seiten: > 1 < [ 2 ] [ 3 ]

000
26.01.2004, 10:31 Uhr
(un)wissender
Niveauwart

Ich hoffe, dass das nicht zu banal oder zu bekannt ist.

Schreibe ein möglichst performantes Programm, welches acht Damen auf einem Schachbrett platziert, die sich nicht gegenseitig schlagen können.

Als Ausgabe kannste ja Ascii nehmen, ob in Java oder C++ ist egal.
--
Wer früher stirbt ist länger tot.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

001
26.01.2004, 12:01 Uhr
virtual
Sexiest Bit alive
(Operator)

Danke fürs Rästel. Leider ist Performant immer so ein dehnbarer begriff...
(sorry for delay, ich hatte ein Meeting)

C++:

#include <iostream>
#include <cstring>

class DamenRaetsel
{
private:
    static const int SIZE = 8; // max sizeof(unsigned)*8 - 1 erlaubt!

    static const unsigned POSITIONSFLAG = 1u<<31;

    unsigned felder[SIZE][SIZE];

    unsigned loesungen;

    void entferneDame(int nr, int x, int y)
    {
        unsigned mask = ~(1u<<nr);

        felder[x][y] &= mask&(~POSITIONSFLAG);

        for(int i=1; i<SIZE; ++i)
        {
            felder[x][i] &= mask;
            felder[i][y] &= mask;
            if (x+i<SIZE)
            {
                if (y+i<SIZE) felder[x+i][y+i] &= mask;
                if (y-i>=0) felder[x+i][y-i] &= mask;
            }
            if (x-i>=0)
            {
                if (y+i<SIZE) felder[x-i][y+i] &= mask;
                if (y-i>=0) felder[x-i][y-i] &= mask;
            }
        }
    }

    bool setzeDame(int nr, int x, int y)
    {
        unsigned mask = (1u<<nr);
        unsigned imask = ~mask;

        if (felder[x][y]&imask)
        {
            return false;
        }
        felder[x][y] |= mask|POSITIONSFLAG;
        for(int i=1; i<SIZE; ++i)
        {
            felder[x][i] |= mask;
            felder[i][y] |= mask;
            if (x+i<SIZE)
            {
                if (y+i<SIZE) felder[x+i][y+i] |= mask;
                if (y-i>=0) felder[x+i][y-i] |= mask;
            }
            if (x-i>=0)
            {
                if (y+i<SIZE) felder[x-i][y+i] |= mask;
                if (y-i>=0) felder[x-i][y-i] |= mask;
            }
        }
        return true;

    }

    void ausgabe()
    {
        std::cout<<"Loesung #"<<++loesungen<<":"<<std::endl;
        std::cout<<"   |";
        for(int i=0; i<SIZE; ++i) std::cout<<' '<<char('A'+i)<<" |";
        std::cout<<std::endl;
        for(int i=0; i<=SIZE; ++i) std::cout<<"---+";
        std::cout<<std::endl;

        for(int y=0; y<SIZE; ++y)
        {
            std::cout<<y+1<<"  |";
            for(int x=0; x<SIZE; ++x)
                std::cout<<((felder[x][y]&POSITIONSFLAG)? " * |":"   |");
            std::cout<<std::endl;
            for(int i=0; i<=SIZE; ++i) std::cout<<"---+";
            std::cout<<std::endl;
        }
        std::cout<<std::endl;
    }

    void naechsteLoesung(int nr)
    {
        for(int i=0; i<SIZE; ++i)
        {
            if (!setzeDame(nr, nr, i))
                continue;
            if (nr+1==SIZE)
            {
                ausgabe();
            }else
            {
                naechsteLoesung(nr+1);
            }
            entferneDame(nr, nr, i);
        }
    }
public:
    DamenRaetsel() :loesungen(0) { memset(felder, 0, sizeof(felder)); }

    void loese() { naechsteLoesung(0); }
};

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

--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21)

Dieser Post wurde am 26.01.2004 um 12:03 Uhr von virtual editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

002
26.01.2004, 13:13 Uhr
(un)wissender
Niveauwart

Wahnsinn!
Hast du das echt in so kurzer Zeit gelöst, oder kanntest du es?
Wenn nicht, dann bin ich nicht in der Lage dir ein Rätsel zu stellen, welches ich lösen kann und du evtl. nicht.
Und performant, jo, das ist es wohl.
Ich habe Probleme es zu verstehen...

Gibt es eigentlich nur 92 Lösungen, oder sind es mehr?
(Versteh mich nicht falsch, 92 sind eine Menge).
--
Wer früher stirbt ist länger tot.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

003
26.01.2004, 13:47 Uhr
virtual
Sexiest Bit alive
(Operator)

Eigentlich sind ja nur 92/4, weil jeweils 4 Drehungen einer Lösung sind.

Hm, zum Verständnis:
es gibt ja SIZE Damen (also beispielsweise 8). Das Spielweld hat die größe SIZE*SIZE Felder. Jedes Feld ist ein unsigned. In einem Unsigned wird das oberste bit (als 1u<<31) gesetzt, wenn dort eine Dame steht. Ansonsten hat jede Dame eine Nummer 0 .. 30 und im Feld wird das Bit 1<<[Damennummer] gessetzt, wenn es durch die Dame erreichbar ist.

Die Methode setzeDame markiert nun also felder entsprechend der oben genannten Regeln. Ausserdem prüft setzeDame gleichzeitig, ob ein Setzen überhaupt möglich ist und gibt entsprechend true oder false zurück.
Da für jede Dame unterschiedliche Bits für die erreichbaren Felder verwendet werden, kann man mittels entferneDame ein gesetzte Dame auch wieder vom Feld nehmen.

Eine Spielstellung ist genau dann gültig, wenn für alle Damen setzeDamen true zurückliefert. rekursive werden daher in naechsteLoseung alle halbwegs sinnvoll erscheinenden Möglichkeiten ausprobiert und dann eben ausgegeben, wenn sie korrekt sind.

Rätsel dieser Art sind eigentlich strukturell recht gleich, wir hatten in der Vergangenheit der Rätselkecke schon oft ähnliches.
--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21)

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

004
26.01.2004, 14:18 Uhr
(un)wissender
Niveauwart

Das mit den Bitmasken ist auch eine gute Idee, viel besser, als alle Felder durch zu gehen.
--
Wer früher stirbt ist länger tot.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

005
26.01.2004, 15:12 Uhr
0xdeadbeef
Gott
(Operator)

Wie wärs damit:

C++:

#include <iostream>

int main() {
  std::cout << "  a b c d e f g h"   << std::endl
        << " +-+-+-+-+-+-+-+-+"  << std::endl
        << "8| | | | | |D| | |8" << std::endl
        << " +-+-+-+-+-+-+-+-+"  << std::endl
        << "7| | | |D| | | | |7" << std::endl
        << " +-+-+-+-+-+-+-+-+"  << std::endl
        << "6| |D| | | | | | |6" << std::endl
        << " +-+-+-+-+-+-+-+-+"  << std::endl
        << "5| | | | | | | |D|5" << std::endl
        << " +-+-+-+-+-+-+-+-+"  << std::endl
        << "4| | | | |D| | | |4" << std::endl
        << " +-+-+-+-+-+-+-+-+"  << std::endl
        << "3| | | | | | |D| |3" << std::endl
        << " +-+-+-+-+-+-+-+-+"  << std::endl
        << "2|D| | | | | | | |2" << std::endl
        << " +-+-+-+-+-+-+-+-+"  << std::endl
        << "1| | |D| | | | | |1" << std::endl
        << " +-+-+-+-+-+-+-+-+"  << std::endl
        << "  a b c d e f g h"   << std::endl;
  return 0;
}

...das dürfte performanter sein...

--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

006
26.01.2004, 15:23 Uhr
(un)wissender
Niveauwart

Das erfüllt das Rätsel, sicher.
War aber für @virtual gedacht und der macht son Scheiß nicht

.
--
Wer früher stirbt ist länger tot.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

007
27.01.2004, 01:17 Uhr
NemoEimi

Huhu,

da das endlich mal wieder ein Performancerätsel ist, also nichts zum Golfen

(bei den Golfrätseln bekomme ich immer so Minderwertigkeitskomplexe

) , habe ich mich eben auch dazu entschlossen, eine Lösung (also ein Programm zum Generieren/Durchzählen der gewünschten Positionen) zusammenzubasteln, obwohl ich nicht das Geburtstagskind bin

.
Hier ist das Ergebnis

C++:

class DamenBrett {
  private int size;
  private int linie_aktuell;
  private boolean fertig;
  private int[] damen_pos;
  private boolean[] reihe_belegt;
  private boolean[] diag1_belegt;
  private boolean[] diag2_belegt;
  private int calc_diag1(int linie, int reihe) {
    return(linie + reihe);
    }
  private int calc_diag2(int linie, int reihe) {
    return(linie - reihe + size);
    }
  public boolean setze_dame(int reihe) {
    if (fertig) return(false);
    if (reihe_belegt[reihe]) return(false);
    int diag1 = calc_diag1(linie_aktuell, reihe);
    if (diag1_belegt[diag1]) return(false);
    int diag2 = calc_diag2(linie_aktuell, reihe);
    if (diag2_belegt[diag2]) return(false);
    damen_pos[linie_aktuell] = reihe;
    reihe_belegt[reihe] = true;
    diag1_belegt[diag1] = true;
    diag2_belegt[diag2] = true;
    linie_aktuell = linie_aktuell + 1;
    if (linie_aktuell == size) fertig = true;
    return(true);
    }
  public boolean problem_solved() {
    return(fertig);
    }
  public void rem_dame() {
    linie_aktuell = linie_aktuell - 1;
    int reihe = damen_pos[linie_aktuell];
    reihe_belegt[reihe] = false;
    int diag1 = calc_diag1(linie_aktuell, reihe);
    int diag2 = calc_diag2(linie_aktuell, reihe);
    diag1_belegt[diag1] = false; diag2_belegt[diag2] = false;
    fertig = false;
    }
  public DamenBrett(int n) {
    size = n;
    linie_aktuell = 0;
    fertig = false;
    damen_pos = new int[size];
    reihe_belegt = new boolean[size];
    diag1_belegt = new boolean[2*size];
    diag2_belegt = new boolean[2*size];
    }
  }

public class damen{
  public static int loesungen = 0;
  public static int size = 0;
  public static void solve_rec(DamenBrett brett) {
    if (brett.problem_solved()) {loesungen = loesungen + 1; return;}
    for (int i = 0; i < size; i++) {
      boolean weiter = brett.setze_dame(i);
      if (weiter) {solve_rec(brett); brett.rem_dame();}
      }
    }
  public static void main(String[] args) {
    int n = Integer.parseInt(args[0]); size = n;
    DamenBrett brett = new DamenBrett(n);
    solve_rec(brett);
    System.out.println("Anzahl gefundener Lösungen:" + loesungen);
    }
  }

Grüße,
Nemo

Dieser Post wurde am 27.01.2004 um 01:20 Uhr von NemoEimi editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

008
27.01.2004, 11:09 Uhr
(un)wissender
Niveauwart

Nicht schlecht, aber du solltest aufpassen bei den args, wenn man nichts übergibt, dann hat man gleiche eine ArrayIndexOutBoundsException, im Prinzip kannste 8 eh vorgeben.
--
Wer früher stirbt ist länger tot.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

009
08.01.2009, 21:49 Uhr
0xdeadbeef
Gott
(Operator)

Ist zwar schon lange her, aber ein anderer Thread hat das irgendwie wieder ein bisschen nach vorne gebracht. Und wo ich das wieder gesehen habe, dachte ich mir: Das toppste doch locker.

Also:

C++:

#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <list>
#include <set>
#include <string>
#include <vector>

#ifndef DIMENSION
#define DIMENSION (8)
#endif

typedef std::vector<int> damen_t;
typedef bool koords_t[DIMENSION];
typedef std::list<damen_t> loesungen_t;

void print_loesung(damen_t const &loesung) {
  std::string delim_line = "\n   ";

  std::cout << "    ";
  for(int i = 0; i < DIMENSION; ++i) {
    std::cout << (i + 1) % 10 << ' ';
    delim_line += "+-";
  }
  delim_line += "+\n";

  std::cout << delim_line;

  for(int i = 0; i < DIMENSION; ++i) {
    std::cout << std::setw(2) << i + 1 << " |";
    for(int j = 0; j < DIMENSION; ++j) {
      std::cout << (j == loesung[i] ? 'D' : ' ') << '|';
    }
    std::cout << delim_line;
  }
  std::cout << std::endl;
}

bool try_dame(damen_t const &damen, int cand_x, int cand_y) {
  for(int x = 0; x < int(damen.size()); ++x) {
    if(std::abs(x - cand_x) == std::abs(damen[x] - cand_y)) {
      return false;
    }
  }

  return true;
}

void backtrack_damen(damen_t &damen,
                     koords_t &left_y,
                     loesungen_t &loesungen) {
  if(damen.size() == DIMENSION) {
    loesungen.push_back(damen);
    return;
  }

  for(int i = 0; i < DIMENSION; ++i) {
    if(left_y[i]) {
      if(try_dame(damen, damen.size(), i)) {
        damen.push_back(i);
        left_y[i] = false;

        backtrack_damen(damen, left_y, loesungen);

        damen.pop_back();
        left_y[i] = true;
      }
    }
  }
}

int main() {
  damen_t damen;
  koords_t koord_y;
  loesungen_t loesungen;

  for(int i = 0; i < DIMENSION; ++i) {
    koord_y[i] = true;
  }

  damen.reserve(DIMENSION);

  backtrack_damen(damen, koord_y, loesungen);

  for(loesungen_t::const_iterator i = loesungen.begin();
      i != loesungen.end();
      ++i) {
    print_loesung(*i);
  }

  std::cout << loesungen.size() << std::endl;
}

Bearbeitung von 0xdeadbeef:

Aufgrund eines dämlichen Fehlers im Zusammenhang mit Iteratorgültigkeit: Neue Version.

--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Dieser Post wurde am 08.01.2009 um 23:06 Uhr von 0xdeadbeef 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: