Ein Schachbrett - acht Damen

CDW · Dez 17, 2007

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 · Dez 17, 2007

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:

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.

Harry Boeck · Dez 18, 2007

http://harryboeck.dyndns.org/Experimente/Habo/Damen-Plazierung.php
http://harryboeck.dyndns.org/Experimente/Habo/Damen-Plazierung-2.php

CDW · Dez 18, 2007

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

Code:

public class Main
{

	public static void main(String[] args)
	{
		try
		{
			long time = System.currentTimeMillis();
			World earth = new World(Integer.parseInt(args[0]), Integer
					.parseInt(args[1]));
			int[] result = earth.compute();
			for (int i = 0; i < result.length; i++)
			{
				for (int k = 0; k < result.length; k++)
					if (k != result[i])
						System.out.print("| ");
					else
						System.out.print("|x");
				System.out.println("|");
			}
			System.out.println(System.currentTimeMillis() - time);

		} catch (Exception ex)
		{
			System.out.println(ex.toString());
			System.out.println("Main <populationsize> <n>");
		}
	}

}

Code:

import java.util.Random;

public class Creature implements Comparable <Creature>
{
	private int[] genom;
	private int fitness;
	private static Random rand=new Random();

	//dient nur der initialisierung	der Welt
	public Creature(int genomsize) 
	{
		genom = new int[genomsize];
		int temp=rand.nextInt(genomsize);
		for (int i=0;i<genom.length;i++)
			genom[i]=(temp+i)%genomsize;
		setFitness();
	}
	
	//nur die Klasse selbst darf sich vermehren 
	//führe dabei ein Crossing-Over durch
	//auch wenn es biologisch haarsträubend anmutet ;)
	private Creature(Creature mother,Creature father)
	{
		genom=new int[father.getGenom().length];
		int k=rand.nextInt(genom.length);
		int cross_len=rand.nextInt(genom.length-k);
		//Mutterchromosom
		for (int i=0;i<genom.length;i++)
			genom[i]=mother.getGenom()[i];
		for (;k<=cross_len;k++)
			genom[k]=father.getGenom()[k];	
		setFitness();		
	}

	public int compareTo(Creature cr) {return fitness-cr.getFitness();}
	
	int[] getGenom() {return genom;}
	
	public Creature makeLove(Creature father)
	{
		return new Creature(this,father);
	}
	
	public void mutate()
	{
		genom[rand.nextInt(genom.length)]=rand.nextInt(genom.length);
		setFitness();
	}
	
	public int getFitness() {return fitness;}	
	//fitnes wird schlechter, wenn die Damen in gleicher
	//spalte sind oder sich diagonal bedrohen	
	private void setFitness() 
	{
		int fit=0;
		for (int i=0;i<(genom.length-1);i++)
			for (int k=i+1;k<genom.length;k++)
			{
				if (genom[i]==genom[k]) fit++;				
				if ((k-i)==Math.abs(genom[k]-genom[i])) fit++;
			}	
		this.fitness=fit;
	}
}

Code:

import java.util.Random;
import java.util.Vector;

public class World
{
	// Abgesehen von CHILDREN immer als 1/n Anteil an der Bevölkerung
	// zu verstehen
	private final static int BEST_REPRODUCTION = 8;
	private final static int CHILDREN = 4;
	private final static int RANDOM_REPRODUCTION = 20;
	private final static int MUTATION = 10;

	private Vector<Creature> population = new Vector<Creature>();	
	private static Random rand = new Random(0);	
	private int populationsize=0;

	public World(int populationsize, int genomsize)
	{
		this.populationsize=populationsize;
		// erschaffe eine neue Welt :)
		for (int i = 0; i < populationsize; i++)
			population.add(new Creature(genomsize));
		java.util.Collections.sort(population);
	}

	public int[] compute()
	{
		while (population.get(0).getFitness() > 0)
		{
			int actual_size = population.size();
			// fortpflanzung der "besten"
			for (int i = 0; i < actual_size / BEST_REPRODUCTION; i++)
				for (int k = 0; k < CHILDREN; k++)
				{
					population.add(population.get(i).makeLove(
							population.get(rand.nextInt(actual_size
									/ BEST_REPRODUCTION))));
				}

			// zufällige fortpflanzung
			actual_size = population.size();
			for (int i = 0; i < actual_size / RANDOM_REPRODUCTION; i++)
			{
				population.add(population.get(rand.nextInt(actual_size))
						.makeLove(population.get(rand.nextInt(actual_size))));
			}

			// mutiere (aber verschone den "besten"):
			actual_size = population.size();
			for (int i = 0; i < actual_size / MUTATION; i++)
			{
				population.get(rand.nextInt(actual_size - 1) + 1).mutate();
			}
			// jetzt lasse die Schwachen sterben:
			java.util.Collections.sort(population);
			population.setSize(populationsize);
		}
		return population.get(0).getGenom();
	}
}

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"

JTron · Jan 4, 2008

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 · Mrz 23, 2008

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

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 · Mrz 23, 2008

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:

Code:

#ifndef NQUEENS_H_
#define NQUEENS_H_
#define DEBUGV
//for debugging output, remove later
#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
#include <cstdlib>
#include <exception>

using namespace std;

class InvalidParam: public exception
{
	virtual const char* what() const throw()
  	{
    	return "Invalid parameter passed";
  	}
};

class NQueensSolver
{
	public:
		NQueensSolver(int n=8);
		vector<int> generateSolution();
	private:
		void generatePermutation(); //generates a new permutation
		bool resolveCollisions(); //tries to eliminate all collisions for the current perm.
		void countCollisions(); //counts collisions per diagonal
		int getNCollisions(int n); //gets collisions for a specified negative diagonal
		int getPCollisions(int n); //gets collisions for a specified positive diagonal
		int collisions(int n); //checks for collisions if n queens are on a diagonal
		void printVector(vector<int> v);
		vector<int> perm;
		map<int, int> queens1,queens2;
		int n;
};

#endif /*NQUEENS_H_*/

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;	
}

Code:

#include <iostream>
#include <cstdlib>
#include <vector>
#include "nqueens.h"

using namespace std;

int main(int argc,char **argv)
{
	srand(time(0));
	int n;
	if(argc != 2) {
		cout << "USAGE: " << argv[0] << " n" << endl;
		cout << "Assuming default: n=8" <<endl;
		n = 8;
	}
	else {
		n = atoi(argv[1]);
	}
	if(n<=3) {
		cout << "Invalid Parameter" << endl;
		return 1;
	}
	
	NQueensSolver nq(n);
	vector<int> solution = nq.generateSolution();
	cout << endl;
	for(vector<int>::iterator it=solution.begin();it!=solution.end();it++) {
		cout << *it << endl;	
	}
	return 0;
}

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

shUnderdog · Mrz 24, 2008

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

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

Lesco · Mrz 24, 2008

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! · Jun 20, 2008

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 · Aug 17, 2008

BF (sucht alle Lösungen):

stumpfes Ausprobieren

Code:

:-use_module(library(lists)).
not_diag(_,[],_).
not_diag(X,[E|Board],Count):-X=\=E+Count,X=\=E-Count,New is Count+1,not_diag(X,Board,New).

no_err([]).
no_err([X|Board]):- not_diag(X,Board,1),no_err(Board),!.

solution(Board,Result):-permutation(Board,Result),no_err(Result).
solution(N,Res):-numlist(1,N,Board),solution(Board,[],Res).

hier werden nur die Lösungswege weiterverfolgt/Berücksichtigt, die bis dahin richtig waren (dann wird das Board weiter zusammengesetzt). Ist sogar kürzer als die primitive Lösung (da man davon ausgehen kann, dass die bisher zusammengesetzten Elemente korrekt zusammengesetzt wurden, braucht man nur das aktuell hinzugefügte Element zu prüfen - dank Rekursion lässt sich die Richtigkeit sogar sehr einfach beweisen

)

Code:

:-use_module(library(lists)).

solution([],Result,Result).
solution(Board,Acc,Result):-select(X,Board,New_Board),
                            not_diag(X,Acc,1),
                            solution(New_Board,[X|Acc],Result).
solution(N,Res):-numlist(1,N,Board),solution(Board,[],Res).

not_diag(_,[],_).
not_diag(X,[E|Board],Count):-X=\=E+Count,X=\=E-Count,New is Count+1,not_diag(X,Board,New).

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:

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,Anzahl).
Anzahl = 92.

Ein Schachbrett - acht Damen

0

0

0

0

JTron

Guest

0

0

0

0

0

0