A permutation of length n is a list of the numbers 1 through n but in some rearr
ID: 3846689 • Letter: A
Question
A permutation of length n is a list of the numbers 1 through n but in some rearranged order. So '1 2 3 is a permutation of length 3, and so is '213', but 5 36412' is a permutation of length 6. Notice that every number between 1 and n appears in the permutation. Permutations are e in different fields and they have practical reaklife use. For this assignment we will play a bit with permutations, but to do that we will need the following methods (Please create the following methods in a Class called Permutations la. Random Permutation (10 points) The first method that we will need method to generate a permutation. Then, you must creat method called random Permutation that takes as in an integer n and return an array with a random permutation of the integers 1 through n. The easiest way to produce a pseudo-)random permutation is to create an array of length n and insert into it the integers 1 n. Next, we can randomly select two indexes in the array to swap them. We will completely shuffle the array by performing the random selection (and the swapping) for a total of n times. lb. Visualizing a Permutation (10 points) A checkerboard visualization is a common method to visualize permutations. The general idea is to generate a grid (i.e., 2 to place in the grid (using the rows as a reference) each element of the D-array) permutation. As an example, the permutation 5, 2, 4, 1, 3 corresponds to the following 5 x 5 2D-array: Page 3 5 2 4 1 3 You will create a method checkBoard which takes as input an array of integers representing a permuta- tion and returns a 2D-array that represents a checkerboard visualization of the input permutation- As suggested above, this method will be very similar to the warm-up questions printBoard.Explanation / Answer
Answer of 1.c(NQUEEN Problem) is as follow:
public class NQueen
{
final int n = 4; //for 4x4 ChessBoard
void printSolution(int Cboard[][])
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
System.out.print(" " + Cboard[i][j] + " ");
System.out.println();
}
}
/* A utility function to check if a queen can be placed on Cboard[row][col]. Note that this function is called when "col" queens are already placeed in columns from 0 to col -1. So we need to check only left side for attacking queens */
boolean queensChecker(int Cboard[][], int row, int col)
{
int i, j;
/* Check this row on left side */
for (i = 0; i < col; i++)
if (Cboard[row][i] == 1)
return false;
/* Check upper diagonal on left side */
for (i=row, j=col; i>=0 && j>=0; i--, j--)
if (Cboard[i][j] == 1)
return false;
/* Check lower diagonal on left side */
for (i=row, j=col; j>=0 && i<n; i++, j--)
if(Cboard[i][j] == 1)
return false;
return true;
}
/* A recursive utility function to solve*/
boolean solveNQUtil(int Cboard[][], int col)
{
/* base case: If all queens are placed then return true */
if (col >= n)
return true;
/* Consider this column and try placing this queen in all rows one by one */
for (int i = 0; i < n; i++)
{
/* Check if queen can be placed on Cboard[i][col] */
if (queensChecker(Cboard, i, col))
{
/* Place this queen in Cboard[i][col] */
Cboard[i][col] = 1;
/* recur to place rest of the queens */
if (solveNQUtil(Cboard, col + 1) == true)
return true;
/* If placing queen in Cboard[i][col] doesn't lead to a solution then remove queen from Cboard[i][col] */
Cboard[i][col] = 0; // BACKTRACK
}
}
/* If queen can not be place in any row in this colum col, then return false */
return false;
}
/*Please note that there may be more than one solutions, this function prints one of the feasible solutions.*/
boolean solveNQ()
{
int Cboard[][] = {{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0}
};
if(solveNQUtil(Cboard, 0) == false)
{
System.out.print("Solution does not exist");
return false;
}
printSolution(Cboard);
return true;
}
// driver program to test above function
public static void main(String args[])
{
NQueenProblem Queen = new NQueenProblem();
Queen.solveNQ();
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.