NQueens

Bachelor Parallele und funktionale Programmierung
1

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

NQueens
also so richtig effizient ist mein Algo nicht :\

Found 1 solutions for size1 in 3
Found 0 solutions for size2 in 0
Found 0 solutions for size3 in 0
Found 2 solutions for size4 in 1
Found 10 solutions for size5 in 1
Found 4 solutions for size6 in 1
Found 40 solutions for size7 in 4
Found 92 solutions for size8 in 2
Found 352 solutions for size9 in 4
Found 724 solutions for size10 in 15
Found 73712 solutions for size13 in 5274
Found 73712 solutions for size13 in 2795
Found 365596 solutions for size 14 in 34601 with 1 Thread.
Found 365596 solutions for size 14 in 26887 with 2 Threads.
Found 365596 solutions for size 14 in 29114 with 3 Threads.
Found 365596 solutions for size 14 in 34379 with 4 Threads.
Found 365596 solutions for size 14 in 34748 with 5 Threads.
Found 365596 solutions for size 14 in 33094 with 6 Threads.
Found 365596 solutions for size 14 in 29194 with 7 Threads.
Found 365596 solutions for size 14 in 29303 with 8 Threads.
Found 365596 solutions for size 14 in 28507 with 9 Threads.

Funktionsweise: eine Zeile wird von je einen Thread bearbeitet, der dann rekursiv absteigt und den Rest sequentiell bearbeitet.

3

Bei mir bekommt jeder Thread eine Teilstellung, und füllt die dann rekursiv auf und zählt wieviele er hinbekommt.

Wie stellst du dein Feld dar? Bei mir ist eine Stellung als int kodiert

4

ich hab es als Boolean[][]

bei einer 3x3 Matrix mit 3 Threads
[1][X][X]
[2][X][X]
[3][X][X]

schnappt sich der 1. Thread Feld [1] und bearbeitet danach die restlichen [X] ab, danach folgt der 2. Thread mit Feld [2] und den restlichen [X]…

5

ist das nicht total das Gefummel mit nem 2dimensionalen Array rumzuhantieren?

Im Prinzip mache ich das Gleiche wie du nur halt eben auf einem 1D int[] Array pro Thread, wüßte auch ad hoc nicht was man da großartig anders machen sollte

6

Sieht bei mir so ähnlich aus…mal aus Interesse, auf was für einem Rechner habt ihr das Programm laufen lassen?

7

Aufm Schleppi, Core i7 Q820@1.73GHz

8

bei mir ist es ein Core Duo vielleicht liegts daran xD

Edit: hab jetzt ein int[] Array daraus gemacht, läuft bedeutend schneller

Found 365596 solutions for size 14 in 11216 with 1 Thread.
Found 365596 solutions for size 14 in 5820 with 2 Threads.
Found 365596 solutions for size 14 in 5851 with 3 Threads.
Found 365596 solutions for size 14 in 7489 with 4 Threads.
Found 365596 solutions for size 14 in 6272 with 5 Threads.
Found 365596 solutions for size 14 in 6381 with 6 Threads.

ab 2 Threads steigt es dann wieder an, liegt wohl doch am Core Duo

9

Meine Ergebnisse sind ähnlich:

Found 1 solutions for size1 in 0
Found 0 solutions for size2 in 0
Found 0 solutions for size3 in 0
Found 2 solutions for size4 in 0
Found 10 solutions for size5 in 0
Found 4 solutions for size6 in 0
Found 40 solutions for size7 in 32
Found 92 solutions for size8 in 0
Found 352 solutions for size9 in 15
Found 724 solutions for size10 in 0
Found 73712 solutions for size13 in 1513
Found 73712 solutions for size13 in 844
Found 365596 solutions for size 14 in 9189 with 1 Thread.
Found 365596 solutions for size 14 in 4852 with 2 Threads.
Found 365596 solutions for size 14 in 5056 with 3 Threads.
Found 365596 solutions for size 14 in 4868 with 4 Threads.
Found 365596 solutions for size 14 in 4946 with 5 Threads.
Found 365596 solutions for size 14 in 4962 with 6 Threads.
Found 365596 solutions for size 14 in 4884 with 7 Threads.
Found 365596 solutions for size 14 in 4869 with 8 Threads.
Found 365596 solutions for size 14 in 4962 with 9 Threads.
Found 2279184 solutions for size 15 in 35431 with 2 Threads.
Found 14772512 solutions for size 16 in 221740 with 2 Threads.

System: Laptop mit Core2Duo @ 2600 MHz.
Implementierung: Jeder Thread beginnt mit einer festen Spalte und zählt die damit möglichen gültigen Damenpositionen. Keine Rekursion, dafür mit Gefummel im zweidimensionalen Array.

Edit: Probeweise auf 15x15 und 16x16 Feldern getestet (s. beide unteren Zeilen der Auflistung)… und mich schweren Herzens von den Gedanken an den neuen Weltrekord (> 26x26) verabschiedet. Grob überschlagen würde mein Rechner für 26x26 knapp 2000 Jahre benötigen… :slight_smile: