Solved

8 Queens Problem Recursively

Posted on 1997-11-10
1
1,303 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 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

On Demand Webinar: Networking for the Cloud Era

Did you know SD-WANs can improve network connectivity? Check out this webinar to learn how an SD-WAN simplified, one-click tool can help you migrate and manage data in the cloud.

Question has a verified solution.

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

Multi-threading long-running processes can have a significant increase in overall performance and drastically decrease over time it takes for a process to complete. Unfortunately, not all applications support native multi-threading, some by design a…
Let’s face it: one of the reasons your organization chose a SaaS solution (whether Microsoft Dynamics 365, Netsuite or SAP) is that it is subscription-based. The upkeep is done. Or so you think.
If you’ve ever visited a web page and noticed a cool font that you really liked the look of, but couldn’t figure out which font it was so that you could use it for your own work, then this video is for you! In this Micro Tutorial, you'll learn yo…
Add bar graphs to Access queries using Unicode block characters. Graphs appear on every record in the color you want. Give life to numbers. Hopes this gives you ideas on visualizing your data in new ways ~ Create a calculated field in a query: …

705 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