Queens Problem MATLAB (Different than normal queens problem) The code of main.m,

Question

Queens Problem MATLAB

(Different than normal queens problem)

The code of main.m, sol.m, and back.m DOES NOT WORK. (It has been given as a solution to all post of same question)

Need help especially with Part C.

Algorithm

A) Begin the code using a variable that defines the board size – we want our code to be flexible enough to handle boards ranging in size from 4x4 up to NxN. Based on this variable, create a “board” by initializing a matrix that is size NxN using the ‘zeros’ command.

B) Write code that will randomly place N queens on the board. Use the number ‘1’ to indicate a space on the board that contains a queen. If you have a 4x4 board, your matrix should now contain four entries that are a ‘1’ -- these represent your queens. The remaining entries in the matrix should still be zeros. Note: This ‘random’ placement is one area of the code that you are allowed to modify. If you truly allow your code to randomly place the queens, it might take a long time to find a solution (especially for large N); the benefit of simple random placement is that the code for the placement of the queens will be much easier to write. Examples of modifications that you can make to the code that will “guide” the placement of queens:

i. Only allow 1 queen to be placed in each row

ii. Only allow 1 queen to be place in each column

iii. After the placement of any single queen, you may also mark off any spaces that she attacks as being unfit for future placement.

iv. (Note: If you program too many restrictions, then your code may not be able to finish placing queens on the board. If you find yourself in this situation, your code must be able to recognize what has happened and should then re-set the board to all zeros and start the placement process once again.)

C) If you haven’t implemented an attack procedure as part of the above restrictions, your code will now have to go through an attack procedure (and even if you did, you may still have to do this step depending on the “completeness” of your attack procedure). That is, once you have a board that has N queens placed on it, you have to evaluate whether any queen threatens another occupied position on the board. Write code that iterates through your matrix and looks for a queen (i.e., a ‘1’), then have that queen ‘attack’ in all possible directions. To do this, change all positions that she is capable of threatening into an ‘8’ (in other words, all other entries in her row, column, and in both diagonals will become an ‘8’). a. Note: If another queen was in the way, this attack sequence just eliminated her from the board. You can stop that particular solution there, or….

D) After executing the attack sequence for every queen on the board, count how many are remaining. If you still have N queens, you’ve found a solution – congratulations! If you have less than N queens on the board, re-set the board (turn it to all zeros) and go back to step 2.

Explanation / Answer

Here's some MATLAB code to implement this idea.

function [board,succeeded] = placeQueens(board,col)
N = size(board,1);
if col > N
% There are no columns left. All the queens
% have been placed. Return with success.
succeeded = true;
return
end
safe = false(1,N);
for row = 1:N
safe(row) = isSafe(board,row,col);
end
if ~any(safe)
% There are no safe squares on this column.
% Return with failure.
succeeded = false;
return
end
for row = 1:N
if safe(row)
board(row,col) = 1;
[board,succeeded] = placeQueens(board,col+1);
if succeeded
return
else
% Backtrack. Undo the placement of the queen
% on this column and keep looking.
board(row,col) = 0;
end
end
end
% If we get here, we have checked every row on this column
% without succeeding. Return with failure.
succeeded = false;

or

function [board,succeeded] = placeQueens(board,col)

N = size(board,1);
if col > N
% There are no columns left. All the queens
% have been placed. Return with success.
succeeded = true;
return
end

safe = false(1,N);
for row = 1:N
safe(row) = isSafe(board,row,col);
end

if ~any(safe)
% There are no safe squares on this column.
% Return with failure.
succeeded = false;
return
end

for row = 1:N
if safe(row)
board(row,col) = 1;
[board,succeeded] = placeQueens(board,col+1);
if succeeded
return
else
% Backtrack. Undo the placement of the queen
% on this column and keep looking.
board(row,col) = 0;
end
end
end

% If we get here, we have checked every row on this column
% without succeeding. Return with failure.
succeeded = false;
end

function [ safe] = isSafe(board,row,col)
safe =true;
% row
if(sum(board(row,:)>0))
safe = false;
return ;
end

if(sum(board(:,col)>0))
safe = false;
return ;
end

% ncol=floor(size(board,2)/2)+1;
dcol = col-row;

if(sum(diag(board,dcol)>0))
safe = false;
return ;
end

NewcolN=size(board,2)-col+1;
dcol = NewcolN-row;

if(sum(diag(fliplr(board),dcol)>0))
safe = false;
return ;
end

end

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.