2. Consider the following problem Given a standard 8x8 chessboard, put on it as
ID: 3709427 • Letter: 2
Question
2. Consider the following problem Given a standard 8x8 chessboard, put on it as many bishops as possible in such a way that they do not attack each other Represent this problem as an algorithmic problem. What is this algorithmic problem? Is it possible to solve it in a polynomial time? What algorithm would you use to find a solution? Explain you answers. 3. Consider the following problem Given a standard 8x8 chessboard, put on it as few bishops as possible in such a way that every square is under attack by one of the bishops Represent this problem as an algorithmic problem. What is this algorithmic problem? Is it possible to solve it in a polynomial time? What algorithm would you use to find a solution? Explain you answers. 4. You have n files with data on your hard drive, files have sizes m, GB,.,mn GB. You want to save them on clouds for backup. You have accounts on K file hosting services. On each of these services first p GB are free, and you have to pay if you exceed the limit. You want to save your files on that clouds in such a way that you do not have to pay for additional space. Is it possible to do so? If the answer is yes, how to do it? Represent this problem as an algorithmic problem. What is this algorithmic problem? Is it possible to solve it in a polynomial time? What algorithm would you use to find a solution? Explain you answers.Explanation / Answer
2 answer
given by
Demonstration for A standard 8*8 chessboard predicament as an algorithmic problem...
1. knowhow to a new queen be located ?
ALGORITHM Place (k,i)
// Returns TRUE if a queen be able to be located in kth row and ith coloumn.
// otherwise it returns FALSE.
// x[ ] is a universal array whose first (k-1) values include been set.
// Abs(r) returns the unqualified value of r.
{
For j:=1 to k-1 do
if ((x[j]=i) // Two in the equal column
or (Abs(x[ j ] - i)=Abs(j-k)))
// or in the equal diagonal
then retirn false;
return true;
}
2. All solutions to the 8*8 - queen’s problem...
ALGORITHM 8Queens (k,8)
// using BACKTRACKING, this method prints all possible placement of 8 queens on an 8*8 chessboard so that // they are non-attacking.
{
for i:=1 to 8 do
{
if Place (k,i) then
{
x[k]:=i;
if (k=8) then write (x[1:8]);
else 8Queens(k+1,8);
}
}
}
3. A standard 8*8 chessboard algorithmic crisis is know as 8-Queens problem which can be solved by the BACKTRACKING practice.
4. I think it is not unlikely to answer in a polynomial time.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.