Here are the rules for Project 3.
Project 3 revolves around the problem of finding all the possible ways to place n queens on an n-by-n chessboard so that none of them are under attack by any of the others.
I have sent you three routines: BPrint.m, QSearch.m, and QSTest.m. You are to write two routines: Queens.m and attack.m. For most of you the attack.m routine that you turned in for Exercise 14 will work fine. The routine Queens.m should be a recursive function.
function count = Queens(B, r, c, count, PrintOut)B is an n-by-n matrix which represents the chessboard. Squares marked with a +1 are occupied by a queen. Squares marked with a -1 are under attack by one or more queens. Squares that are marked with 0 are empty and not under attack. The arguments r and c are the row and column indices of an empty swuare where a queen is to be placed. The argument, count, is the ongoing count of the total number of solutions found to this point, and the argument, PrintOut, is a flag which indicates whether or not a solution should be pretty printed using the BPrint routine.
Once your programs are working correctly, run QSearch for a 4-by-4 and a 5-by-5 chessboard with PrintOut set to true. Then run QSearch for an 8-by-8 chessboard with PrintOut set to false (don't print all the solutions!). Print the command window. Then run QSTest and set the maximum size to 10. Print the command window and both plots. Turn in the listing of your Queens.m program, the printouts of the command windows, the printouts of the plots, and a brief discussion of your recursive program.
BPrint.m
function BPrint( B ) % % BPrint( B ) % % This function pretty prints the board % represented by B. Every square containing % the value one represents a queen. The % remaining squares are empty. % Daniel D. Warner 3/6/2000 [m,n] = size(B); for r=1:m for c=1:n if B(r,c) == 1 fprintf(' Q '); else fprintf(' - '); end end fprintf('\n'); end fprintf('\n');QSearch.m
% Project 3 - Queen Search % % This program is the driver for the % recursive function which finds all % the possible ways to place n queens % on an n-by-n chessboard so that none % of the queens are under attack by % any of the others. There are many % ways to do this if n > 3. % Daniel D. Warner 3/6/2000 n = input('Enter the size of the board: '); if (n < 4) fprintf('It is not possible to place %g nonattacking queens on an %g-by-%g chessboard\n',n,n,n); else yn = input('Do you want to print out the solutions? (y/n): '); if (yn == 'y') | (yn == 'Y') Printout = 1; else Printout = 0; end B = zeros(n,n); % Start the clock Tstart = clock count = 0; for r = 1:floor(n/2) count = count + 2*Queens(B,r,1,0, Printout); end if rem(n,2) count = count + Queens(B,ceil(n/2),1,0, Printout); end % Stop the clock. Tstop = clock fprintf('Found %g solutions in %g seconds\n', count, etime(Tstop,Tstart)) endQSTest.m
% Queen Search Test % % This program is the driver for the % recursive function which finds all % the possible ways to place n queens % on an n-by-n chessboard so that none % of the queens are under attack by % any of the others. % % This version runs all boards from 4-by-4 % thru the maximum specified size. It then % draws a plot of the time versus the size % of the board. % Daniel D. Warner 3/6/2000 nmax = input('Enter the maximum size of the board: '); if (n < 4) fprintf('It is not possible to place %g nonattacking queens on an %g-by-%g chessboard\n',n,n,n); else times = zeros(1,(nmax-3)); counts = zeros(1,(nmax-3)); Printout = 0; for n = 4:nmax % Start the clock Tstart = clock; B = zeros(n,n); count = 0; for r = 1:floor(n/2) count = count + 2*Queens(B,r,1,0, Printout); end if rem(n,2) count = count + Queens(B,ceil(n/2),1,0, Printout); end % Stop the clock. Tstop = clock; counts(n-3) = count; times(n-3) = etime(Tstop,Tstart); end fprintf('Solutions Time\n') for k=1:nmax-3 fprintf(' %5d %g sec\n', counts(k), times(k)); end X = [4:nmax] plot(X, counts); title('Number of Solutions') pause plot(X, times); title('Times For Each Board'); end