MthSc 360: Project 3

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))
end

QSTest.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