n - Damen Problem mit Backtracking

Die bekannteste Variante ist das Acht-Damen-Problem. Hier wird danach gefragt, wie man acht Damen auf ein Schachbrett stellen kann, ohne dass sich diese gegenseitig bedrohen. Das heisst, es dürfen keine zwei Damen in der gleichen waagrechten, senkrechten oder diagonalen Linie stehen. Von Interesse ist nicht nur eine Lösung zu finden, sondern auch die Frage, wie viele verschiedene es gibt.

Das Problem kann für beliebig viele Damen verallgemeinert werden. Auch in unserem Beispiel kann die Anzahl Damen beliebig gewählt werden. Die Anzahl der vertikalen und horizontalen Zellen wird dann automatisch angepasst.

Im ersten Beispiel wird eine Lösung durch Backtracking ermittelt. Man setzt die erste Dame und probiert systematisch alle Möglichkeiten für die nächste. Wenn man die nächste Dame nicht setzen kann, geht man wieder einen Schritt zurück und versucht die vorhergehende Dame anders zu platzieren.

Im Beispiel 2 (siehe unten) werden mit einem anderen Algorithmus alle möglichen Lösungen für die gewählte Damenzahl gesucht und angezeigt.

Beispiel 1: Die Lösungssuche durch Backtracking wird mit Klick auch die Schaltfläche Run gestartet. Mit Step kann man das Vorgehen schrittweise verfolgen, mit dem Schieberegler kann die Geschwindigkeit angepasst werden. Falls Sie die Anzahl Damen ändern möchten, müssen Sie im Programmcode den Wert der Variablen nrQueens ändern.

Programmcode downloaden (GGQueens.zip)

Programmcode

// GGQuens.java

import ch.aplu.jgamegrid.*;
import java.awt.*;
import java.util.*;
import ch.aplu.util.Monitor;

public class GGQueens extends GameGrid
{

  final static int nrQueens = 8; //changes number of queens & size of board!
  Queen[] queens = new Queen[nrQueens];
  private int nrSteps;

  public GGQueens()
  {
    super(nrQueens, nrQueens, 600 / nrQueens);
    this.setBgColor(Color.white);
    setTitle("n-queens problem");
    drawPattern();
    this.addStatusBar(25);
    show();
    for (int i = 0; i < queens.length; i++)
    {
      queens[i] = new Queen();
    }
    solveQueens();
  }

  public void act()
  {
    Monitor.wakeUp();
  }

  private void drawPattern()
  {
    GGBackground bg = getBg();
    for (int x = 0; x < nbHorzCells; x++)
      for (int y = 0; y < nbVertCells; y++)
      {
        if ((x + y) % 2 == 0)
          bg.fillCell(new Location(x, y), new Color(142, 72, 47));
        else
          bg.fillCell(new Location(x, y), new Color(255, 218, 145));
      }
  }

  public void reset()
  {
    removeAllActors();
    nrSteps = 0;
    setStatusText("Situation reset..");
  }

  private void solveQueens()
  {
    boolean notSolved = true;
    int nrQueen = 0;
    boolean troubleForNextQueen = false;
    addActor(queens[0], new Location(0, nbVertCells - 1));
    while (notSolved)
    {
      nrSteps++;
      refresh();
      Monitor.putSleep();
      if (isThreatenedByOtherQueen(queens[nrQueen].getLocation()) || troubleForNextQueen)
        if (queens[nrQueen].getY() == 0)
        {
          queens[nrQueen].removeSelf();
          setStatusText("Tracing steps back..");
          nrQueen--;
          troubleForNextQueen = true;
        }
        else
        {
          queens[nrQueen].move();
          setStatusText("Moving forward..");
          troubleForNextQueen = false;
        }
      else
      {
        if (nrQueen == queens.length - 1)
        { //solved!
          notSolved = false;
          success();
        }
        else
        {
          nrQueen++;
          addActorNoRefresh(queens[nrQueen], new Location(nrQueen, nbVertCells - 1));
          setStatusText("Adding next queen..");
          troubleForNextQueen = false;
        }
      }
    }
  }

  private void success()
  {
    setStatusText("Found Solution! It took: " + nrSteps + " steps.");
  }

  private boolean isThreatenedByOtherQueen(Location queenLoc)
  {
    ArrayList<Location> possibleLocations = getDiagonalLocations(queenLoc, true);
    possibleLocations.addAll(getDiagonalLocations(queenLoc, false));

    for (int x = 0; x < nbVertCells; x++)
      possibleLocations.add(new Location(x, queenLoc.y));

    for (int y = 0; y < nbHorzCells; y++)
      possibleLocations.add(new Location(queenLoc.x, y));

    while (possibleLocations.contains(queenLoc))
      possibleLocations.remove(queenLoc);

    for (Location loc : possibleLocations)
    {
      if (getActorsAt(loc, Queen.class).size() != 0)
        return true;
    }
    return false;
  }

  public static void main(String[] args)
  {
    new GGQueens();
  }
}

// ------------- class Queen ---------------------

class Queen extends Actor
{
  public Queen()
  {
    super("sprites/queen.png");
  }

  public void reset()
  {
    this.setDirection(Location.NORTH);
  }
}

Alle mögliche Lösungen rekursiv suchen

Beispiel 2: Mit Hilfe eines rekursiven Algorithmus werden alle möglichen Lösungen gesucht. Am Schluss können mit Klick auf die Schaltflächen Step oder Run alle Lösungen nacheinander angezeigt werden. Die Anzahl der Lösungen steigt mit der Anzahl der Damen exponentiell:

Anzahl Damen
4
6
8
10
12
14
16
18

Anzahl Lösungen
2
8
92
724
14200
365596
14772514
666090624

Beispiel zeigen

Beispiel im Online-Editor bearbeiten

Programmcode downloaden (GGQueensRec.zip)

Programmcode

// GGQueensRec.java

import java.awt.Color;
import java.util.ArrayList;

import ch.aplu.jgamegrid.*;

public class GGQueensRec extends GameGrid
{
  private final static int nrQueens = 12; //changes number of queens & size of board!
  private boolean mustWait = true;

  public GGQueensRec()
  {
    super(nrQueens, nrQueens, 600 / nrQueens);
    this.setBgColor(Color.white);
    setTitle("Damenproblem");
    drawPattern();
    addStatusBar(25);
    addResetListener(
      new GGResetListener()
      {
        public boolean resetted()
        {
          return true;  // Consume reset event->reset disabled
        }
      });
    show();
    setStatusText("Press 'Run' or 'Step' to play.");
    while (true)
    {
      setSimulationPeriod(300);
      doWait();
      ArrayList<int[][]> solutions = solveQueens(nrQueens, nrQueens);
      setSimulationPeriod(2000);
      setStatusText("Done. " + solutions.size()
        + " solutions. Press 'Run' or 'Step' to show them.");
      removeAllActors();
      refresh();
      doPause();
      mustWait = true;
      doWait();

      //iterate through solutions
      int nb = 1;
      for (int[][] computedSolution : solutions)
      {
        setStatusText("Solution #" + nb++ + " of " + solutions.size());
        arrangeQueensOnBoard(computedSolution);
        doWait();
      }
      setStatusText("Done. Press 'Run' or 'Step' to play again.");
      doPause();
      doWait();
    }
  }

  private void doWait()
  {
    while (mustWait)
      delay(1);
    mustWait = true;
  }

  public void act()
  {
    mustWait = false;
  }

  private void drawPattern()
  {
    GGBackground bg = getBg();
    for (int x = 0; x < nbHorzCells; x++)
      for (int y = 0; y < nbVertCells; y++)
      {
        if ((x + y) % 2 == 0)
          bg.fillCell(new Location(x, y), new Color(142, 72, 47));
        else
          bg.fillCell(new Location(x, y), new Color(255, 230, 145));
      }
  }

  private ArrayList<int[][]> solveQueens(int row, int column)
  {
    if (row <= 0)
    {
      ArrayList<int[][]> zeroCase = new ArrayList<int[][]>();
      zeroCase.add(new int[nrQueens][nrQueens]);
      return zeroCase;
    }
    else
      return oneMoreQueen(row - 1, column, solveQueens(row - 1, column));
  }

  private ArrayList<int[][]> oneMoreQueen(int newRow, int column, ArrayList<int[][]> partSolution)
  {
    ArrayList<int[][]> newSolution = new ArrayList<int[][]>();
    for (int[][] solution : partSolution)
    {
      for (int i = 0; i < column; i++)
      {
        if (noConflicts(newRow, i, solution))
        {
          setStatusText("No conflicts -> save partial solution");
          int[][] solutionClone = cloneArray(solution);
          solutionClone[i][newRow] = 1;
          newSolution.add(solutionClone);
        }
        else
          setStatusText("Conflict -> drop partial solution");
        doWait();
      }
    }
    return newSolution;
  }

  private boolean noConflicts(int newRow, int i, int[][] solution)
  {
    arrangeQueensOnBoard(solution);
    addActor(new Actor("sprites/queen.png"), new Location(i, newRow));
    return !isThreatenedByOtherQueen(new Location(i, newRow));
  }

  private void arrangeQueensOnBoard(int[][] solution)
  {
    removeAllActors();
    for (int x = 0; x < nrQueens; x++)
    {
      for (int y = 0; y < nrQueens; y++)
      {
        if (solution[x][y] == 1)
          addActor(new Actor("sprites/queen.png"), new Location(x, y));
      }
    }
  }

  public static int[][] cloneArray(int[][] solution)
  {
    int[][] copy = new int[solution.length][];
    for (int i = 0; i < solution.length; i++)
    {
      System.arraycopy(solution[i], 0, copy[i] = new int[solution[i].length], 0, solution[i].length);
    }
    return copy;
  }

  private boolean isThreatenedByOtherQueen(Location queenLoc)
  {
    ArrayList<Location> possibleLocations = getDiagonalLocations(queenLoc, true);
    possibleLocations.addAll(getDiagonalLocations(queenLoc, false));

    for (int x = 0; x < nbVertCells; x++)
      possibleLocations.add(new Location(x, queenLoc.y));

    for (int y = 0; y < nbHorzCells; y++)
      possibleLocations.add(new Location(queenLoc.x, y));

    while (possibleLocations.contains(queenLoc))
      possibleLocations.remove(queenLoc);

    for (Location loc : possibleLocations)
    {
      if (getActorsAt(loc, Actor.class).size() != 0)
        return true;
    }
    return false;
  }

  public static void main(String[] args)
  {
    new GGQueensRec();
  }
}