Solved

8 Queens Problem Recursively

Posted on 1997-11-10
1
1,275 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
Comment Utility
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

Enabling OSINT in Activity Based Intelligence

Activity based intelligence (ABI) requires access to all available sources of data. Recorded Future allows analysts to observe structured data on the open, deep, and dark web.

Join & Write a Comment

Never store passwords in plain text or just their hash: it seems a no-brainier, but there are still plenty of people doing that. I present the why and how on this subject, offering my own real life solution that you can implement right away, bringin…
Scam emails are a huge burden for many businesses. Spotting one is not always easy. Follow our tips to identify if an email you receive is a scam.
Excel styles will make formatting consistent and let you apply and change formatting faster. In this tutorial, you'll learn how to use Excel's built-in styles, how to modify styles, and how to create your own. You'll also learn how to use your custo…
This video demonstrates how to create an example email signature rule for a department in a company using CodeTwo Exchange Rules. The signature will be inserted beneath users' latest emails in conversations and will be displayed in users' Sent Items…

772 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

10 Experts available now in Live!

Get 1:1 Help Now