Was ist eine effiziente Möglichkeit, ein Schachbrett in LISP zu speichern?

Question

Was ist eine effiziente Möglichkeit, ein Schachbrett in LISP zum Beispiel zu speichern, um das 8-Königinnen-Puzzle zu lösen?

Answer 1

Für die 8 Königinnen Problem, Ihre effizientesten Speicher wird ein Array von 8 Bytes sein. Clojure stellt die Methode byte-array zur Verfügung, um das Erstellen eines solchen Arrays zu vereinfachen. Behandle jedes Byte als ein Array von 8 Bits und verwende 0 für ein leeres Quadrat und 1 für eine Königin.

Dies funktioniert nicht, wenn Sie mehr als eine Art von Schachfiguren verwenden möchten; Darüber hinaus sollten Sie einen anderen Ansatz betrachten, wenn Sie variable Boardgrößen wünschen.

Answer 2

Um das Problem der acht Königinnen effizient zu lösen, suchen Sie nach einer effizienten Möglichkeit, eine Teillösung darzustellen.

Wenn wir Reihen und Dateien 0-7 Nummer und arbeiten zunehmend durch die Reihen, dann ein Vektor rank -> file macht den Job.

• Die Reihen kümmern sich um sich selbst.
• Die freien Dateien sind, was von (set (range 8)) übrig bleibt.
• Die frei aufsteigenden Diagonalen sind die Reste von (set (range 15)).
• Die frei fallenden Diagonalen sind die Reste von (set (range -7 8)).

... wo, für jeden Platz [i j],

• die rank ist i
• die file ist j
• die rising-diagonal ist (+ i j)
• die falling-diagonal ist (- i j)

Sie könnten, wie @WolfeFan schlägt, Bit-Sets verwenden, um die freien oder belegten Steckplätze zu speichern. Aber die Speicherung ist in beiden Darstellungen vernachlässigbar. Und welche Darstellung ist schneller, ich würde nicht raten.