Solved

8 Queens Problem Recursively

Posted on 1997-11-10
1
1,280 Views
Last Modified: 2012-06-27
Does anyone have an example to solve the 8 Queens problem recursively?

Place 8 queens on a chess board so that no two queens are attacking each other
0
Comment
Question by:sdevine
1 Comment
 
LVL 5

Accepted Solution

by:
y96andha earned 50 total points
ID: 1216722
Here is an example which I just wrote for you. It will lose its indentation when posted, but I hope you can read it anyway. It sets up a chessboard, tries adding a queen at a time in a free position, and for each time marks the squares which cannot be used, and tries to add a new queen recursively.

type
      pos = (Free, Queen, Busy);
      chessboard = array[1..8,1..8] of pos;

Var
  r,k: integer;
  emptyboard : chessboard;

function min(a,b:integer):integer;
begin
      if a<b then min := a else min := b;
end;

function findsolution(board : chessboard; level : Integer): Boolean;
Var
      r,k:integer;
      i:integer;
      ch:char;
      boardcopy:chessboard;
begin
      findsolution:=false;
      boardcopy := board;
      for r:=1 to 8 do
            for k:=1 to 8 do
                  if boardcopy[r, k] = Free Then
                  begin
                        if level+1 = 8 then begin
                              writeln;
                              writeln('Solution:');
                              for r:=1 to 8 do
                              begin
                                    for k:=1 to 8 do
                                          If boardcopy[r, k] = Queen then
                                                write('Q')
                                          else
                                                write(' ');
                                    writeln;
                              end;
                              findsolution:=true;
                              exit;
                        end;


                        board:=boardcopy;
                        for i:=1 to 8 do
                              board[i, k]:=Busy;
                        for i:=1 to 8 do
                              board[r, i]:=Busy;
                        for i:=1-min(r,k) to min(9-r,9-k)-1 do
                              board[r+i, k+i]:=Busy;
                        for i:=1-min(9-r,k) to min(r, 9-k)-1 do
                              board[r-i, k+i]:=Busy;

                        board[r, k]:=Queen;

                        if findsolution(board, level+1) Then
                        begin
                              findsolution:=True;
                              exit;
                        end;

                  end;

end;



begin

      for r:=1 to 8 do
            for k:=1 to 8 do
                  emptyboard[r,k]:=Free;

      if findsolution(emptyboard, 0) then
            writeln('A solution was found');
end.
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Some code to ensure data integrity when using macros within Excel. Also included code that helps secure your data within an Excel workbook.
Knowledge base software has turned out to be a quite reliable method for storing information, promoting collaborative work and for sharing valuable input and solutions.However, some organizations are trying to develop a knowledge base that works wit…
This Micro Tutorial will give you a basic overview how to record your screen with Microsoft Expression Encoder. This program is still free and open for the public to download. This will be demonstrated using Microsoft Expression Encoder 4.
Video by: Mark
This lesson goes over how to construct ordered and unordered lists and how to create hyperlinks.

920 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

12 Experts available now in Live!

Get 1:1 Help Now