?
Solved

8 Queens Problem Recursively

Posted on 1997-11-10
1
Medium Priority
?
1,306 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
1 Comment
 
LVL 5

Accepted Solution

by:
y96andha earned 200 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

[Webinar] Lessons on Recovering from Petya

Skyport is working hard to help customers recover from recent attacks, like the Petya worm. This work has brought to light some important lessons. New malware attacks like this can take down your entire environment. Learn from others mistakes on how to prevent Petya like worms.

Question has a verified solution.

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

The top devops trends for 2017 are focused on improved deployment frequency, decreased lead time for change and decreased MTTR.
If you're a modern-day technology professional, you may be wondering if certifications are really necessary. They are. Here's why.
Michael from AdRem Software explains how to view the most utilized and worst performing nodes in your network, by accessing the Top Charts view in NetCrunch network monitor (https://www.adremsoft.com/). Top Charts is a view in which you can set seve…
Sometimes it takes a new vantage point, apart from our everyday security practices, to truly see our Active Directory (AD) vulnerabilities. We get used to implementing the same techniques and checking the same areas for a breach. This pattern can re…

764 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