[HaBo]

**CDW** · 17.12.07, 22:29

Eingereicht von JTron,
mich wundert es, dass es diesen Klassiker noch nicht gab ;)

Das Programm soll dem Benutzer alle Möglichkeiten zeigen, wie man 8 Damen auf einem Schachbrett platzieren kann, ohne dass sie sich gegenseitig bedrohen. Am besten so:

0 = leer
1 = dame

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

Zur Erinnerung: eine Dame kann eine andere Figur sowohl horizontal, vertikal wie auch diagonal "bedrohen". D.h sie sollten sich nicht in die Quere kommen.
Schöner wäre es natürlich, wenn das Programm das allgemeine Problem löst: n-Damen auf einem nXn Brett

lookshe · 17.12.07, 22:53

Ich durfte das im ersten Semester im Informatikunterricht schon lösen in Setl2.

Einfach am Anfang die Anzahl der Damen aendern und man kann beliebiege Feldgrößen berechnen. Ausgabe ist allerdings etwas anders als vorgegeben, hab keine Lust das jetzt noch anzupassen.

Hier mal die Lösung ohne Kommentare:

Code

Code:

program main;
    numberQueens := 8;
    board := createBoard(numberQueens);
    print(board);
    print("\n");

    Clauses := allClauses(board);
    print("Test: Aufgabe 7");
    print("This should print a formula that is equivalent to the " 
          + numberQueens + "-queens-problem.");
    print(Clauses);
    print("\n");

    if Clauses /= om then
        I := DavisPutnam(Clauses,{});
    end if;

    if I /= FALSE then
        printBoard(I, board);
    else
        print("The problem is not solvable for " + numberQueens + " queens!");
        print("Try to increase the number of queens.");
    end if;

    procedure atMostOne(S);
		return {{["-",p1],["-",p2]} : p1 in S, p2 in S | p1/=p2};
    end atMostOne;

    procedure atMostOneInRow(board, row);
		return atMostOne(board(row));
    end atMostOneInRow;    

    procedure atMostOneInColumn(board, column);
		i:=#board;
		M:={ board(row)(column) : row in [1..i]};
		return atMostOne(M);
    end atMostOneInColumn;

    procedure atMostOneInUpperDiagonal(board, k);
		i:=#board;
		M:={ board(row)(column) : row in [1..i], column in [1..i] | row+column=k};
		return atMostOne(M);
    end atMostOneInUpperDiagonal;

    procedure atMostOneInLowerDiagonal(board, k);
		i:=#board;
		M:={ board(row)(column) : row in [1..i], column in [1..i] | row-column=k};
		return atMostOne(M);
    end atMostOneInLowerDiagonal;

    procedure oneInRow(board, row);
		return {{x : x in board(row)}};
    end oneInRow;

    procedure allClauses(board);
		i:=#board;
		M1:={atMostOneInRow(board,row) : row in [1..i]};
		M2:={atMostOneInColumn(board,column) : column in [1..i]};
		M3:={atMostOneInUpperDiagonal(board,k) : k in [2..16]};
		M4:={atMostOneInLowerDiagonal(board,k) : k in [-7..7]};
		M5:={oneInRow(board,row) : row in [1..i]};
		Klausel:=+/M1 + +/M2 + +/M3 + +/M4 + +/M5;
		return Klausel;
    end allClauses;

    procedure createBoard(n);
        return [ createRow(n, i) : i in [1..n] ];
    end createBoard;

    procedure createRow(n, i);
        return [ "p" + i + j : j in [1..n] ];
    end createRow;

    procedure printBoard(I, board);
        if I = om then
            return;
        end if;
        n := #board;
        print( "        " + ((8*n+1) * "-") );
        for row in [1..n] loop
            line := "        |";
            for col in [1..n] loop
                line +:= "       |";
            end loop;
            print(line);
            line := "        |";
            for col in [1..n] loop
                if { board(row)(col) } in I then
                    line +:= "   Q   |";
                else
                    line +:= "       |";
                end if;
            end loop;
            print(line);
            line := "        |";
            for col in [1..n] loop
                line +:= "       |";
            end loop;
            print(line);
            print( "        " + ((8*n+1) * "-") );
        end loop;
    end printBoard;

    procedure printBoardSmall(I, board);
        n := #board;
        print( "        " + ((2*n+1) * "-") );
        for row in [1..n] loop
            line := "        |";
            for col in [1..n] loop
                if { board(row)(col) } in I then
                    line +:= "Q|";
                else
                    line +:= " |";
                end if;
            end loop;
            print(line);
            print( "        " + ((2*n+1) * "-") );
        end loop;
    end printBoardSmall;

    procedure DavisPutnam( Clauses, Literals );
        Clauses := saturate(Clauses);
        if {} in Clauses then
            return false;
        end if;
        if { k in Clauses | #k = 1 } = Clauses then
            return Clauses;
        end if;
        literal := selectLiteral(Clauses, Literals);
        Result := DavisPutnam(Clauses + {{literal}}, Literals + { literal });
        if Result /= false then
            return Result;
        end if;        
        notLiteral := negateLiteral(literal);
        return DavisPutnam(Clauses + {{notLiteral}}, Literals + { notliteral } );
    end DavisPutnam;

    procedure saturate(S);
        Units := { k in S | #k = 1 };
        Used := {};
        while Units /= {} loop
            unit := arb Units;
            Used := Used + { unit };
            literal := arb unit;
            S := reduce(S, literal);
            Units := { k in S | #k = 1 } - Used;        
        end loop;
        return S;
    end saturate;

    procedure reduce( S, l );
        notL := negateLiteral(l);
        return { k - { notL } : k in S | notL in k } + 
               { k : k in S | not notL in k and (not l in k or k = {l}) };
    end reduce;

    procedure selectLiteral( S, Forbidden );
        return arb { l : k in S, l in k | not l in Forbidden };
    end selectLiteral;

    procedure negateLiteral(l);
        if l(1) = "-" then
            return l(2);
        else
            return [ "-", l ];
        end if;
    end negateLiteral;

end main;

Angehängt noch die Datei mit Kommentaren.

Anzeige

- Anzeige -

Harry Boeck · 18.12.07, 00:23

http://harryboeck.dyndns.org/Experim...Plazierung.php
http://harryboeck.dyndns.org/Experim...azierung-2.php

**CDW** · 18.12.07, 22:43

Ich habe hier eine etwas andere Lösungsmethode ("Heuristik"). Sie liefert zwar nur eine mögliche Lösung zurück, dafür aber auch für deutlich größere n

der Trick besteht darin, eine für das jeweilige n passende Startgröße zu wählen - ist sie zu groß, wird bei kleineren n unnötig Zeit "verplempert", ist sie zu klein, wird bei größeren n zu wenig "Suchraum" abgedeckt und es dauert wiederum womöglichst viel zu lange.
Start: java Main <populationsize> <n>
Bsp: java Main 1000 8
um eine Lösung für ein 8x8 Brett zu erhalten
Erfahrungswerte:Startgröße 1000 - 10000
sehr grobe Orientierungswerte
für n=8 werden ~40ms - 260ms benötigt
n=10 ~40 bis 200ms
n=12 ~150 bis 1000ms
n=20 ~500ms bis 10s (populationsize sollte ab n>=20 auf 10000 hochgeschraubt werden)
n=50 ~ab 8sek

Main.java

Creature.java

World.java

Edit: eine Lösung für n=100 (ca 5 min)
Vieles hängt von den gewählten Parametern ab. Zugegebenermaßen eignet sich das Verfahren eher dazu, möglichst schnell eine suboptiomale Lösung zu erhalten - insbesondere bei dem Schritt "99% optimal -> 100%" wird es sehr deutlich.
Im Anhang die aktualierte Version+"binary"

04.01.08, 17:18

hier, musste selbst erstmal nachdenken und im internet schauen:

Code:

class NDamen
	def initialize(size)
		@size = size
		@brett = []
	end
	def to_s
		versuch(0)
	end
private
	def feld_frei(ix, iy)
		for i in 0..iy-1
			if (@brett[i] == ix) || (((@brett[i].to_i)-ix).abs) == ((i - iy).abs)
				return false
			end
		end
		return true
	end
	def versuch(n)
		if n == @size
			print_one
		else
			for i in 0..@size-1
				if feld_frei(i,n)
					@brett[n] = i
					versuch(n+1)
				end
			end
		end
	end
	def print_one
		for i in 0..@size-1
			for j in 0..@size-1
				if j == @brett[ i ]
					print "*"
				else
					print "."
				end
			end
			print "\n"
		end
		print "\n\n"
		gets
	end
end

x = NDamen.new(8)
x.to_s

unten die n - Zahl einfügen (bei x = NDamen.new(n) )

MontyPerl · 23.03.08, 22:44

Nimmt als erstes Argument n an. Falls kein Argument übergeben wird, wird n von STDIN gelesen.

n-Damenproblem auf n*n-Brett in perl

Code:

#!/usr/bin/env perl
use warnings;
use strict;

our $n;

if (@ARGV) {$n = $ARGV[0]}
else {print "\$n ="; chomp($n = <STDIN>)}

sub solveRecur {
    my ($y, $cur, $sol, @field) = @_;
    if ($y < $n) {
        for my $x (0 .. $n-1) {
            if (not isThreatened($x, $y, @field)) {
                ${field[$y][$x]} = 1;
                solveRecur($y+1, [@$cur, "$x,$y"], $sol, @field);
                ${field[$y][$x]} = 0
            }
        }
    }
    else {
        push(@{$sol}, join(';', @$cur))
    }
}

sub validConstellation {
    my ($x1, $y1, $x2, $y2) = @_;
    if (($x1 == $x2) or ($y1 == $y2)) {return 0}
    for my $dX (1, -1) {
        for my $dY (1, -1) {
            my ($tmpX, $tmpY) = ($x1, $y1);
            while(($tmpX >= 0) and ($tmpX < $n) and ($tmpY >= 0) and ($tmpY < $n)) {
                $tmpX += $dX;
                $tmpY += $dY;
                if (($tmpX == $x2) and ($tmpY == $y2)) {return 0}
            }
        }
    }
    return 1
}

sub isThreatened {
    my ($x, $y, @field) = @_;
    for my $i (0 .. $n) {
        for my $j (0 .. $n) {
            if ((${field[$i][$j]) and (not validConstellation($x, $y, $j, $i))) {return 1}
            }
        }
    }
    return 0
}

sub createField {
    my @field;
    for my $y (0 .. $n-1) {
        $field[$y] = [];
        for (0 .. $n-1) {
            push(@{$field[$y]}, 0)
        }
    }
    return @field
}


sub prepareSolvedField {
    my @field = createField();
    for my $xypair (split(/;/, $_[0])) {
        my ($x, $y) = split(/,/, $xypair);
        ${field[$y][$x]} = 1
    }
    return @field
}

sub outputField {
    my @field = @_;
    for (1 .. $n) {print "--"}
    print "\n";
    foreach my $rowRef (@field) {
        foreach my $pos (@$rowRef) {
            if ($pos) {print "\@ "}
            else {print ". "}
        }
        print "\n"
    }
}


my @solutions;
solveRecur(0, [], \@solutions, createField());

foreach my $solution (@solutions) {
    outputField(prepareSolvedField($solution))
}

?: Wer auf Farbe steht, kann die outputField Funktion mit dieser hier ersetzen:

Code:

sub outputField {
    use Term::ANSIColor qw(:constants);
    my @field = @_;
    my $switch = 1;
    for (1 .. $n) {print "--"}
    print "\n";
    foreach my $rowRef (@field) {
        foreach my $pos (@$rowRef) {
            if ($switch) {print ON_RED}
            else {print RESET}
            $switch = not $switch;
            if ($pos) {print "\@ "}
            else {print "  "}
        }
        print RESET, "\n";
        unless ($n % 2) {$switch = not $switch}
    }
}

Lesco · 23.03.08, 23:59

Hier noch 'ne Alternative zum Standard-Backtracking(jedoch auch nur eine Lösung pro Durchlauf): Man wählt eine zufällige Permutation und versucht diese durch Tauschen von Damen zu einer Lösung zu bringen. Damit kommt man dann sogar auf O(n^3) pro Permutation und für größere Bretter geht die Anzahl an benötigten Permutationen gegen 1.

Vorsicht: unoptimiert und unsauber:

nqueens.h

nqueens.cpp

Code:

#include "nqueens.h"

NQueensSolver::NQueensSolver(int n)
{
	if(n<4) {
		throw InvalidParam();	
	}
	this->n = n;	
}

void NQueensSolver::printVector(vector<int> v)
{
	for(vector<int>::iterator it=v.begin();it!=v.end();it++) {
		cout << *it << endl;	
	}	
}

vector<int> NQueensSolver::generateSolution() 
{
	//cout << "Trying to generate solution for n=" << n << endl;
	bool solutionFound=false;
	int i=0;
	do {
		i++;
		generatePermutation();
		cout << "Trying permutation(Try: " << i << "): " << endl;
		printVector(perm);
		countCollisions();
		solutionFound=resolveCollisions();
	} while(!solutionFound);
	return perm;
}

void NQueensSolver::generatePermutation() 
{
	vector<int> values;
	for(int i=0;i<n;i++)
		values.push_back(i);
	perm.erase(perm.begin(),perm.end());
	for(int i=0;i<n;i++) {
		int temp = rand() % (n-i);
		perm.push_back(values[temp]);
		values.erase(values.begin()+temp);
	}
}

void NQueensSolver::countCollisions()
{
	/*
	 * check all "negative" diagonals
	 * x+y=const. for all fields on it
	 */
	for(int i=0;i<(2*n-1);i++) {
		int colls=0;
		for(int j=0;j<n;++j) {
			if((perm[j] + j) == i)
				colls++;	
		}	
		queens1[i] = colls;
	}
	/*
	 * check all "positive" diagonals
	 * x-y=const. for all fields
	 */
	 for(int i=0;i<(2*n-1);i++) {
	 		int val = i-n+1,colls=0;
	 		for(int j=0;j<n;j++) {
	 			if((j-perm[j]) == val)
	 				colls++;	
	 		}
	 		queens2[val]=colls;
	 }
}

int NQueensSolver::getNCollisions(int n)
{
	if(queens1[n] < 2)
		return 0;
	return queens1[n]-1;	
}

int NQueensSolver::getPCollisions(int n)
{
	if(queens2[n] < 2)
		return 0;
	return queens2[n]-1;	
}

int NQueensSolver::collisions(int n)
{
	if(n<2)
		return 0;
	return n-1;	
}

bool NQueensSolver::resolveCollisions()
{
	int swaps;
	do {
		swaps=0;
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				int nval1 = i + perm[i];
				int nval2 = j + perm[j];
				int pval1 = i - perm[i];
				int pval2 = j - perm[j];
				
				if(i==j)
					continue;
				//check wether one queen is attacked
				if(getNCollisions(nval1)||getPCollisions(pval1)||
					getNCollisions(nval2)||getPCollisions(pval2)) {
					int before,after;
					map<int,int> temp1(queens1),temp2(queens2);
					temp1[nval1]--; temp2[pval1]--;
					temp1[i+perm[j]]++; temp2[i-perm[j]]++;
					temp1[nval2]--; temp2[pval2]--;
					temp1[j+perm[i]]++; temp2[j-perm[i]]++;
					before = collisions(queens1[nval1]) + collisions(queens2[pval1]) +
								collisions(queens1[i+perm[j]]) + collisions(queens2[i-perm[j]]) +
								collisions(queens1[nval2]) + collisions(queens2[pval2]) +
								collisions(queens1[j+perm[i]]) + collisions(queens2[j-perm[i]]);
					after = collisions(temp1[nval1]) + collisions(temp2[pval1]) +
								collisions(temp1[i+perm[j]]) + collisions(temp2[i-perm[j]]) +
								collisions(temp1[nval2]) + collisions(temp2[pval2]) +
								collisions(temp1[j+perm[i]]) + collisions(temp2[j-perm[i]]);
							
					//swapping reduces collisions -> swap them
					if(after<before) {
							queens1[nval1]--; queens2[pval1]--;
							queens1[i+perm[j]]++; queens2[i-perm[j]]++;
							queens1[nval2]--; queens2[pval2]--;
							queens1[j+perm[i]]++; queens2[j-perm[i]]++;
							swaps++;
							int temp = perm[i];
							perm[i] = perm[j];
							perm[j] = temp;
					}
				}
			}	
		}
	} while(swaps!=0);
	for(int i=0;i<(2*n-1);i++) {
		if(queens1[i]>1)
			return false;
		if(queens2[i-n+1]>1)
			return false;		
	}
	return true;	
}

main.cpp

(können "glücksbedingt" mehr oder weniger stark variieren)
n=100: 0.6s
n=1000: 21.18s
n=5000: 9:18min

shUnderdog · 24.03.08, 19:53

auf die gefahr hin als noob oder ähnliches hingestellt zu werden^^

woher kommt bitte die imense zeitsteigerung von 1000 auf 5000 durchläufe?

Lesco · 24.03.08, 21:36

Nunja, dass liegt daran, dass die Zeit nicht linear, sondern immernoch polynomiell(was schonmal ein großer Vorteil zum exponentiellen Backtracking-Algorithmus ist) ansteigt, d.h. verdoppelt man die Größe verdoppelt sich nicht die Zeit, sondern sie wächst stärker an.(Z.B. für x^3: 10^3=1000 50^3=125000)

Ook! · 20.06.08, 12:37

Meine Java Lösung

Code:

import java.util.ArrayList;
import java.util.List;

public class Queenproblem {
	
	public static void main(String[] args) {
		Solver solver = new Queenproblem().new Solver(8);
		System.out.println("Anzahl Lösungen: "+ solver.getSolutionCount());
		System.out.println("\n"+ solver.printFields());
	}
	
	class Solver {
		
		private int queensCount = 0;
		private List<int[][]> solutions = null; 
		
		public Solver(int queensCount){
			this.queensCount = queensCount;
			this.solutions = new ArrayList<int[][]>(); 
			this.doIt(0, 1, new int[8][8]);
		}
		
		private void doIt(int row, int queen, int[][] field){
			if(queen > queensCount){
				solutions.add(cloneField(field));
				return;
			}
			for(int i=0; i<8; i++){
				if(!isConflict(row, i, field)){
					field[row][i] = queen;
					doIt(row+1, queen+1, field);
					field[row][i] = 0;
				}
			}
		}
		
		private boolean isConflict(int row, int col, int[][] field){			
			for(int i=0; i<8; i++){
				for(int z=0; z<8; z++){
					if(field[i][z] > 0){
						if(i == row || z == col){ // selbe reihe oder selbe spalte
							return true;
						}
						else if((i-z) == (row-col)){ // selbe diagonale lo->ru
							return true;
						}
						else if((i+z) == (row+col)){ // selbe diagonale ro->lu
							return true;
						}
					}
				}
			}
			return false;
		}
		
		private int[][] cloneField(int[][] field){
			int[][] clone = new int[8][8];
			for(int i=0; i<8; i++){
				clone[i] = field[i].clone();
			}
			return clone;
		}
		
		public int getSolutionCount(){
			return solutions.size();
		}
		
		public String printFields(){
			String returnString = "";
			for(int[][] field : solutions){
				for(int[] row : field){
					for(int value : row) {
						returnString += value +" ";
					}
					returnString += "\n";
				}
				returnString += "\n";
			};
			return returnString.substring(0,returnString.length()-2);
		}
		
	}
	
}

**CDW** · 17.08.08, 22:16

BF (sucht alle Lösungen):

primitiv

besser

Beide sind dazu geeignet, nach allen Lösungen zu suchen (sonst kann man sich auch eine bestimmte anzeigen lassen). Nur der erste ist eben etwas langsammer

Suchen aller Lösungen (ok, ohne sie zu printen) für N=12 dauert 3 Sek, für N=13 ca. 21 Sekunden.

Aufruf mit:
solve(N,Result).
Bsp:

Zitat:

6 ?- solution(25,R).
R = [22, 17, 12, 18, 16, 14, 7, 10, 8, 6, 23, 25, 20, 24, 21, 19, 15, 13, 11, 9, 4, 2, 5, 3, 1]
oder:
findall(_,solution(8,_),Counter),length(Counter,An zahl).
Anzahl = 92.

Anzeige

- Anzeige -

17.12.07, 22:29	#1 (permalink)
CDW Moderator Registriert seit: 20.07.05 Likes: 202	Ein Schachbrett - acht Damen Anzeige Eingereicht von JTron, mich wundert es, dass es diesen Klassiker noch nicht gab ;) Das Programm soll dem Benutzer alle Möglichkeiten zeigen, wie man 8 Damen auf einem Schachbrett platzieren kann, ohne dass sie sich gegenseitig bedrohen. Am besten so: 0 = leer 1 = dame 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Zur Erinnerung: eine Dame kann eine andere Figur sowohl horizontal, vertikal wie auch diagonal "bedrohen". D.h sie sollten sich nicht in die Quere kommen. Schöner wäre es natürlich, wenn das Programm das allgemeine Problem löst: n-Damen auf einem nXn Brett __________________ Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf! Selig, wer nichts zu sagen hat und trotzdem schweigt.

Themen-Optionen
Druckbare Version zeigen Jemanden per E-Mail auf dieses Thema hinweisen
Ansicht
Linear-Darstellung Zur Hybrid-Darstellung wechseln Zur Baum-Darstellung wechseln

18.12.07, 00:23	#3 (permalink)
Harry Boeck Registriert seit: 17.02.06 Likes: 0	http://harryboeck.dyndns.org/Experim...Plazierung.php http://harryboeck.dyndns.org/Experim...azierung-2.php

24.03.08, 19:53	#8 (permalink)
shUnderdog Registriert seit: 09.08.06 Likes: 0	auf die gefahr hin als noob oder ähnliches hingestellt zu werden^^ woher kommt bitte die imense zeitsteigerung von 1000 auf 5000 durchläufe?

24.03.08, 21:36	#9 (permalink)
Lesco Senior Member Registriert seit: 03.09.05 Likes: 0	Nunja, dass liegt daran, dass die Zeit nicht linear, sondern immernoch polynomiell(was schonmal ein großer Vorteil zum exponentiellen Backtracking-Algorithmus ist) ansteigt, d.h. verdoppelt man die Größe verdoppelt sich nicht die Zeit, sondern sie wächst stärker an.(Z.B. für x^3: 10^3=1000 50^3=125000)

[HaBo]

Ein Schachbrett - acht Damen