Eight Queens Problem

The Eight Queens Problem refers to a puzzle where you place eight chess queens on an 8Ă—8 chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal. This solver uses a recursive function, solveQueens, to attempt to place queens in every single combination until a solution is found. The solveQueens function adds queens one row at a time, but a separate isSolution function checks every queen’s diagonals to see whether any of them threaten each other. Finally, for dramatic effect, each frame of the computation is stored in an arraylist that is displayed one frame at a time for the user to see. By the time the animation starts loading, the problem has already been solved fully, and the sketch simply plays back the solution! [raw] [/raw] Code for the animation follows。 You can edit and run this code on the KTBYTE Coder
int boardRectSize = 50;
boolean[][] board = new boolean[8][8];
PImage queen;
ArrayList tries = new ArrayList();

void setup() {
  //size(8*boardRectSize, 8*boardRectSize);

  size(400, 400);
  boardRectSize = width / board.length;
  queen = loadImage("https://i.imgur.com/SDiocmg.png");
  queen.resize(boardRectSize, boardRectSize);
  solveQueens(board, 0);

void draw() {
  int index = frameCount;
  if (index < tries.size()) {
  } else {
    noLoop(); //end program

boolean hasQueen(boolean[][] board, int x, int y) {
  if (x >= 0 && x < board.length && y >= 0 && y < board[x].length && board[x][y] == true) return true;
  return false;

boolean isSolution(boolean[][] board) {
  //save copy for drawing:
  boolean[][] cp = new boolean[board.length][board[0].length];
  for (int i=0; i= board.length) return isSolution(board);
  if (!isSolution(board)) return false; //exit if board not valid already

  for (int i=0; i	

Leave a Reply

Your email address will not be published. Required fields are marked *