GameGrid: Game programming with Java
Research project PHBern  
HomePrintJava-Online

n - queens problem with backtracking


The 8-queens problem is probably the best know variation of the n-queens problem. The question of the problem is how to place eight queens on a chess board in a way that they are not able to attack each other. There cannot be any 2 queens in the same horizontal, vertical or diagonal line. The goal is not just to find one possible solution, but all of them.

An advanced way of looking at the problem is by trying to solve the problem for any number of queens. In this example we try to do exactly this. The number of queens can be defined in the source code and the amount of horizontal and vertical lines of the board are set automatically according to the quantity of queens.

The first example tries to solve the problem through backtracking. The first queen is set on the board and every other possible position of the next queen is tried out systematically. If the next queen cannot be placed on the board the porgram goes back to the previous one and tries to relocate it.

In this first example we stop after finding a possible solution. The second example (see below) detects all possible solutions, counts and shows them.

  

Example 1: The problem solving process ist started by clicking the Button Run. Clicking on Step the process can be looked at step by step. The speed of the process can be changed by sliding the speed control back and forth. To change the number of queens, redefine the varaible nrQueens.

Run this example

Edit this example in the Online-Editor

Download the program code (GGQueens.zip) 

Program code

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

 

Finding all possible solution recursively

Example 2: All possible solutions are detected with the help of a recursive algorithm. As sooon as all of them are found each solution can be looked at by clicking on the buttons Step or Run. The quantity of solutions increases exponentially with the number of queens:

number of queens
4
6
8
10
12
14
16
18

quantity of solutions
2
8
92
724
14200
365596
14772514
666090624

 

Run this example

Edit this example in the Online-Editor

Download the program code (GGQueensRec.zip) 

  

 

Program code

// 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();
  }
}