N-queens in Haskell, ohne Liste traversal

StackOverflow https://stackoverflow.com/questions/1255018

Frage

Ich suchte im Internet nach verschiedenen Lösungen für das n-Damen-problem in Haskell, aber konnte nicht finden das überprüfen könnte für unsichere Positionen in O(1) Zeit, so dass Sie halten ein array der / einer diagonalen und einer für \ diagonalen.

Die meisten Lösungen, die ich gefunden, nur geprüft jeder neue Königin gegen all die vorherigen.So etwas wie dieses:http://www.reddit.com/r/programming/comments/62j4m/nqueens_in_haskell/

nqueens :: Int -> [[(Int,Int)]]
nqueens n = foldr qu [[]] [1..n]
    where qu k qss = [ ((j,k):qs) | qs <- qss, j <- [1..n], all (safe (j,k)) qs ]
      safe (j,k) (l,m) = j /= l && k /= m && abs (j-l) /= abs (k-m)

Was wäre der beste Weg, um die Umsetzung einer solchen "O(1) - Ansatz" in Haskell?Ich bin nicht auf der Suche nach etwas "super optimiert".Nur einige Wege, um das zu produzieren "ist diese Diagonale bereits genutzt?" - array in eine funktionale Art und Weise.

UPDATE:

Vielen Dank für all die Antworten, Leute!Der Grund, warum ich ursprünglich gestellte Frage ist, weil ich lösen wollte ein schwieriger, backtracking problem.Ich wusste, wie es zu lösen in einer imperativen Sprache, konnte aber nicht sofort denken Sie an eine rein funktionale Datenstruktur, die Arbeit zu tun.Ich dachte mir, dass die Damen-problem wäre ein gutes Vorbild (da die backtracking problem :) ) für die gesamte Daten-Struktur, problem -, aber es ist nicht mein real problem though.

Ich wirklich wollen, zu finden, eine Daten-Struktur, mit der O(1) random access und hält Werte, die entweder auf eine "ursprüngliche" Zustand (frei-Linie/Diagonale, in der n-Königinnen-Fall) oder in einer "endgültigen" Zustand (besetzt-Linie/Diagonale), mit übergängen (frei, besetzt) wird O(1).Dies kann realisiert werden mit veränderlichen arrays in einer imperativen Sprache, aber ich fühle, dass die Beschränkung der Aktualisierung der Werte erlaubt nur eine schöne, rein funktionale Datenstrukturen (im Gegensatz zu Quicksort, zum Beispiel, dass wirklich will veränderlichen arrays).

Ich vermute, das sth-Lösung ist so gut, wie Sie erhalten können mit immutable arrays in Haskell und der "main" - Funktion, sieht aus wie ich ihn mir gewünscht habe:

-- try all positions for a queen in row n-1
place :: BoardState -> Int -> [[(Int, Int)]]
place _ 0 = [[]]
place b n = concatMap place_ (freefields b (n-1))
   where place_ p = map (p:) (place (occupy b p) (n-1))

Das Hauptproblem scheint zu sein, dass eine bessere Datenstruktur, obwohl, wie Haskell-Arrays O(n) zu aktualisieren.Weitere schöne Anregungen Herbst kurze von der mythischen O(1) Heiligen Gral:

  • DiffArrays nahe gekommen, sondern Durcheinander in der backtracking.Sie bekommen tatsächlich super langsam :( .
  • STUArrays Konflikt mit den hübschen funktionale backtracking-Ansatz, damit Sie verworfen werden.
  • Maps und Sets haben nur O(log n) aktualisiert werden.

Ich bin nicht wirklich sicher, es gibt eine Lösung insgesamt, aber es scheint vielversprechend.

UPDATE:

Die vielversprechendsten Daten-Struktur, die ich gefunden, wo die Anhänger Arrays.Im Grunde eine Haskell DiffArray aber es mutiert zurück, wenn Sie backtrack.

War es hilfreich?

Lösung

Im Allgemeinen sind Sie wahrscheinlich stecken die Zahlung der O(log n) Komplexität Steuer für einen funktionalen, nicht-destruktiv Umsetzung oder haben Sie, nachsichtig zu sein, und verwenden Sie einen (IO|ST|STM)UArray.

Strengen pure Sprachen zu bezahlen O(log n) Steuern über eine unreine Sprache schreiben können, die sich auf Referenzen durch die Implementierung von Referenzen durch eine Karte-wie Struktur;faul Sprachen können manchmal dodge dieser Steuer, obwohl es keinen Beweis dafür, so oder so, ob oder nicht die zusätzliche Leistung angeboten durch Faulheit ist ausreichend, um stets dodge dieser Steuer ist-auch wenn es den starken Verdacht, dass Faulheit ist nicht leistungsfähig genug.

In diesem Fall ist es schwer zu sehen, ein Mechanismus, durch den die Faulheit könnte ausgenutzt werden, um zu vermeiden, die Steuer-Referenz.Und, nach allem, das ist, warum wir die ST Monade in den ersten Platz.;)

Das heißt, Sie könnten untersuchen, ob oder nicht einige Art von board-schräger Reißverschluss könnte ausgenutzt werden, die Lokalität updates -- Ausnutzung von Lokalität in einer Reißverschluss ist ein gemeinsamer Weg, um zu versuchen, um drop eine logarithmische Laufzeit.

Andere Tipps

Der einfachste Weg wäre, um einen UArray (Int, Int) Bool aufzeichnen sicher/unsicher bits.Obwohl das kopieren von diesen ist O(n2), für kleine Werte von N dies ist die Schnellste Methode zur Verfügung.

Für größere Werte von N, gibt es drei Hauptoptionen:

  • Daten.DiffArray entfernt Kopie overhead wie lange, wie Sie nie verwenden, die alten Werte wieder, nachdem Sie Sie ändern.Das heißt, wenn Sie immer wegwerfen, die alten Werte des Arrays nach mutierend es, die änderung ist O(1).Wenn Sie jedoch Zugriff auf den alten Wert des Arrays später (sogar für nur Lesen), die O(N2) ist, dann bezahlt in voll.
  • Daten.Karte und Daten.Set erlauben, O(lg n) änderungen und Suchvorgänge.Dadurch ändert sich die Algorithmische Komplexität, aber Häufig schnell genug.
  • Daten.Array.ST STUArray s (Int, Int) Bool geben Sie Imperativ-arrays, so dass Sie zum implementieren des Algorithmus in der klassischen (nicht-funktionale) Art und Weise.

Das grundlegende problem mit diesem Ansatz ist, dass die arrays für die diagonalen müssen geändert werden jedes mal, wenn eine Dame gelegt.Der kleine Verbesserung des constant-lookup-Zeit für die diagonalen vielleicht nicht unbedingt sein lohnt sich, die zusätzliche Arbeit ständig neue modifizierte arrays.

Aber der beste Weg, um zu wissen, die wirkliche Antwort ist, es zu versuchen, also habe ich ein wenig rumprobiert und kam mit der folgenden:

import Data.Array.IArray (array, (//), (!))
import Data.Array.Unboxed (UArray)
import Data.Set (Set, fromList, toList, delete)

-- contains sets of unoccupied columns and lookup arrays for both diagonals
data BoardState = BoardState (Set Int) (UArray Int Bool) (UArray Int Bool)

-- an empty board
board :: Int -> BoardState
board n
   = BoardState (fromList [0..n-1]) (truearr 0 (2*(n-1))) (truearr (1-n) (n-1))
   where truearr a b = array (a,b) [(i,True) | i <- [a..b]]

-- modify board state if queen gets placed
occupy :: BoardState -> (Int, Int) -> BoardState
occupy (BoardState c s d) (a,b)
   = BoardState (delete b c) (tofalse s (a+b)) (tofalse d (a-b))
   where tofalse arr i = arr // [(i, False)]

-- get free fields in a row
freefields :: BoardState -> Int -> [(Int, Int)]
freefields (BoardState c s d) a = filter freediag candidates
   where candidates = [(a,b) | b <- toList c]
         freediag (a,b) = (s ! (a+b)) && (d ! (a-b))

-- try all positions for a queen in row n-1
place :: BoardState -> Int -> [[(Int, Int)]]
place _ 0 = [[]]
place b n = concatMap place_ (freefields b (n-1))
   where place_ p = map (p:) (place (occupy b p) (n-1))

-- all possibilities to place n queens on a n*n board
queens :: Int -> [[(Int, Int)]]
queens n = place (board n) n

Das funktioniert und ist, für die n=14 rund 25% schneller als die version, die Sie erwähnt.Die wichtigsten speedup kommt aus der Verwendung des arrays ohne Verpackung bdonian empfohlen.Mit dem normalen Data.Array es hat etwa die gleiche Laufzeit wie die version in Frage.

Es könnte sich auch lohnen, es zu versuchen, die anderen array-Typen aus der Standardbibliothek zu sehen, ob mit Ihnen kann die Leistung weiter verbessern.

Ich bin immer skeptisch der Anspruch dass rein funktional ist in der Regel O(log n).Siehe auch Edward der Bürgermeister die Antwort, die macht in Anspruch zu nehmen.Obwohl, die angewendet werden können, um zufällige Mutationen array-Zugriff im theoretischen Sinne, sondern zufällige änderbaren array-Zugriff ist wahrscheinlich nicht das, was die meisten algorithmen benötigt, wenn es richtig ist, studierte für wiederholbare Struktur, d.h.nicht zufällig ist.Ich denke, dass Edward der Bürgermeister bezieht sich auf diese, wenn er schreibt, "exploit Ortschaft updates".

Ich bin am überlegen O(1) ist theoretisch möglich, in einer reinen funktionalen-version des n-Damen-Algorithmus, indem Sie die undo-Methode für die DiffArray, welche Anforderungen ein Blick zurück in die Unterschiede Duplikate entfernen, und vermeiden Sie die Wiedergabe.

Wenn ich richtig bin in meinem Verständnis der Art und Weise der backtracking n-queens-Algorithmus arbeitet, dann ist die Verlangsamung verursacht durch die DiffArray ist, weil die unnötigen Unterschiede beibehalten werden.

In der Zusammenfassung, eine "DiffArray" (nicht unbedingt Haskell ' s) hat (oder haben könnte) ein set-element-Methode gibt eine neue Kopie des Arrays und speichert einen Unterschied Datensatz mit die original, einschließlich der Zeiger auf die neue geändert kopieren.Wenn die original Kopie muss Zugriff auf ein element, dann ist diese Liste der Unterschiede muss wiederholt werden in umgekehrter rückgängig machen die änderungen auf eine Kopie der aktuellen Kopie.Hinweis: es ist auch der Aufwand, die einzelnen verknüpften Liste zu ging zu Ende, bevor es wiedergegeben werden können.

Stellen Sie sich stattdessen wurden diese gespeichert, wie eine doppelt verknüpfte Liste, und es wurde die undo-Funktion wie folgt.

Aus einer abstrakten konzeptionellen Ebene, was die Rückverfolgung n-queens-Algorithmus ist rekursiv operieren auf einigen arrays von booleans, bewegen Sie den queen ' s position schrittweise vorwärts in diese arrays auf jeder rekursiven Ebene.Finden diese animation.

Arbeiten diese aus in meinem Kopf, ich Stelle mir, dass der Grund DiffArray so langsam ist, ist, weil, wenn die Königin zog von einer position zur anderen, dann Boolesches flag für die original-position wird wieder auf false gesetzt und die neue position auf true festgelegt ist, und diese Unterschiede werden aufgezeichnet, aber Sie sind unnötig weil, wenn wiedergegeben in reverse, das array endet mit dem gleichen Wert, den es hat, bevor Sie die Wiedergabe begann.Also, anstatt Betrieb wieder auf false gesetzt, was benötigt wird, ist die undo-Methode aufrufen, Optional mit einer input-parameter erzählen DiffArray was "rückgängig " zu" Wert für die Suche nach den in den vorstehenden double-linked-Liste der Unterschiede.Wenn die "rückgängig" - Wert ist im Unterschied Datensatz in der doppelt verknüpften Liste, gibt es keine widersprüchlichen intermediate änderungen auf das gleiche array-element, wenn man zu Fuß zurück in die Liste zu durchsuchen, und der aktuelle Wert gleich dem "undo " aus" - Wert in diesem Unterschied Datensatz der Datensatz kann dann entfernt werden und dass die alten kopieren können werden re-Spitzen, um den nächsten Datensatz in der doppelt verknüpften Liste.

Was diese leistet, ist zu entfernen unnötige kopieren des gesamten Arrays auf backtracking.Es gibt noch einige zusätzliche overhead im Vergleich zu der Imperativ version des Algorithmus zum hinzufügen und lösen der Beurteilung der Unterschied records, aber dies näher zu konstanter Zeit, alsoO(1).

Wenn ich das richtig verstehe die n-queen-Algorithmus, der lookback für die undo-operation ist nur eine, es gibt also kein Spaziergang.So ist es nicht einmal erforderlich, zum speichern der Unterschied der set-element beim bewegen der Königin zu stellen, da es rückgängig gemacht werden, bevor die alte Kopie zugegriffen werden.Wir brauchen nur ein Weg, um auszudrücken, diese Art sicher, das ist einfach genug zu tun, aber ich lasse es als übung für den Leser, als diese post ist jetzt schon viel zu lang.

UPDATE:Ich habe nicht geschrieben, der code für den gesamten Algorithmus, aber in meinem Kopf der n-Königinnen können umgesetzt werden auf jede Zeile iteriert, eine Falte auf der folgenden Reihe von diagonalen, wo jedes element ist die Triole tuple von:(index der Zeile, die es besetzt ist oder Keiner, array of row indices kreuzenden Links-rechts-diagonal-array der Reihe Indizes schneidenden rechts, Links, diagonal).Die Zeilen Durchlaufen werden können, die mit Rekursion oder eine Falte, die von einem array von Zeilen-Indizes (die Falte hat der Rekursion).

Hier folgt die Schnittstellen für die Daten-Struktur, die ich vorstellen.Die syntax ist unten Copute, aber ich denke, es ist nahe genug, um Scala, dass Sie verstehen können, was beabsichtigt ist.

Beachten Sie, dass eine Umsetzung von DiffArray werden übermäßig langsam, wenn es ist multithreaded, aber das n-queens backtracking-Algorithmus erfordert nicht DiffArray, um Multithread.Dank Edward Bürgermeister für den Hinweis in die Kommentare für diese Antwort.

interface Array[T]
{
   setElement  : Int -> T -> Array[T]     // Return copy with changed element.
   setElement  : Int -> Maybe[T] -> Array[T]
   array       : () -> Maybe[DiffArray[T]]// Return copy with the DiffArray interface, or None if first called setElement() before array().
}
// An immutable array, typically constructed with Array().
//
// If first called setElement() before array(), setElement doesn't store differences,
// array will return None, and thus setElement is as fast as a mutable imperative array.
//
// Else setElement stores differences, thus setElement is O(1) but with a constant extra overhead.
// And if setElement has been called, getElement incurs an up to O(n) sequential time complexity,
// because a copy must be made and the differences must be applied to the copy.
// The algorithm is described here:
//    http://stackoverflow.com/questions/1255018/n-queens-in-haskell-without-list-traversal/7194832#7194832
// Similar to Haskell's implementation:
//    http://www.haskell.org/haskellwiki/Arrays#DiffArray_.28module_Data.Array.Diff.29
//    http://www.haskell.org/pipermail/glasgow-haskell-users/2003-November/005939.html
//
// If a multithreaded implementation is used, it can be extremely slow,
// because there is a race condition on every method, which requires internal critical sections.

interface DiffArray[T] inherits Array[T]
{
   unset       : () -> Array[T]        // Return copy with the previous setElement() undone, and its difference removed.
   getElement  : Int -> Maybe[T]       // Return the the element, or None if element is not set.
}
// An immutable array, typically constructed with Array( ... ) or Array().array.

UPDATE:Ich arbeite auf der Scala-Implementierung, die eine verbesserte Schnittstelle im Vergleich zu dem, was ich hatte oben vorgeschlagen.Ich habe auch erklärt, wie eine Optimierung für Falten Ansätze der gleichen Konstanten overhead als ein veränderliches array.

Ich habe eine Lösung.Jedoch kann die Konstante große, so dass ich nicht wirklich Hoffnung schlagen alles.

Hier ist meine Datenstruktur:

-- | Zipper over a list of integers
type Zipper = (Bool,  -- does the zipper point to an item?
               [Int], -- previous items
                      -- (positive numbers representing
                      --   negative offsets relative to the previous list item)
               [Int]  -- next items (positive relative offsets)
               )

type State =
  (Zipper, -- Free columns zipper
   Zipper, -- Free diagonal1 zipper
   Zipper  -- Free diagonal2 zipper
   )

Es ermöglicht alle erforderlichen Operationen durchgeführt werden, die in O(1).

Der code kann hier gefunden werden: http://hpaste.org/50707

Die Geschwindigkeit ist schlecht-es ist langsamer als die Referenz-Lösung gepostet, die in der Frage über die die meisten Eingänge.Ich habe gemessen, Sie gegen einander auf-Eingänge [1,3 .. 15] und bekam die folgende Zeit-Verhältnissen ((reference solution Zeit / meine Lösung mal) in %):

[24.66%, 19.89%, 23.74%, 41.22%, 42.54%, 66.19%, 84.13%, 106.30%]

Beachten Sie nahezu lineare Verlangsamung der Referenz-Lösung, die relativ zu mir, zeigt Unterschied in der asymptotischen Komplexität.

Meine Lösung ist wahrscheinlich schrecklich in Bezug auf strenge und Dinge wie, dass, und müssen gefüttert werden, einige sehr gut optimierende compiler (wie Don Stewart zum Beispiel), um bessere Ergebnisse zu erhalten.

Wie auch immer, ich denke, in diesem problem O(1) und O(log(n)) nicht mehr zu unterscheiden sind sowieso da log(8) nur 3 und Konstanten wie diese sind Gegenstand von Mikro-Optimierungen statt des Algorithmus.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top