Question

k bishops on an nXn chessboard We have previously solved the N Queens Problem, where, for a given n, we calculated the number of ways to place n queens on an nXn board. This problem concerns bishops on the chessboard. What is a bishop? A bishop is a chess piece that controls all the squares on the two diagonals that it can reach Note that a bishop may be either on a white square or a black square. The problenm Write a program that inputs two integers n and k, where n>-k. Your program should calculate the number of different ways that k bishops could be placed on an nXn chessboard Structure your program using the backtracking scheme that we have used for the eight queens problem. What needs to be modified is the OK function Input Your main program should loop asking the user for values of n and k. Output Each time through the loop, output n, k and the number of configurations. Program Termination The program will terminate if the user enters a value of-1 for n

The problem

Write a program that inputs two integers n and k, where n>=k. Your program should calculate the number of different ways that k bishops could be placed on an nXn chessboard. Structure your program using the backtracking scheme that we have used for the eight queens problem. What needs to be modified is the “OK” function.

Input

Your main program should loop asking the user for values of n and k.

Output

Each time through the loop, output n, k and the number of configurations. Program Termination The program will terminate if the user enters a value of -1 for n.

0 0
Add a comment Improve this question Transcribed image text
Answer #1
Since you have not provided your language preference, I am providing the code in C++

CODE
=================
/*
 Write a program that inputs two integers n and k, where n>=k. Your program should calculate
 the number of different ways that k bishops could be placed on an nXn chessboard.
 Structure your program using the backtracking scheme that we have used for the eight queens
 problem. What needs to be modified is the “OK” function.
 */

#include <cstdlib>
#include <iostream>
using namespace std;

int k, n; //number of bishops, size of the board

//q is an array of squares, where b is a bishop and q[b] is the square the bishop occupies
bool ok(int q[], int b, int n){
    //identify the row and column the bishop is in
    int row = q[b]/n, column = q[b]%n, current_row, current_column;
    
    for(int i=0; i<b; i++){ //for every bishop
        current_row = q[i]/n;
        current_column = q[i]%n;
        
        //diagonal test
        if(abs(row-current_row)==abs(column-current_column)) return false;
    }
    
    return true;
}

void backtrack(int &b, int count){
    b--;
    if(b==-1){
        cout << k << " bishops can be placed on an " << n << " by " << n << " chessboard in " << count << " different ways.";
        exit(1);
    }
}

int vectors(){
    while(true){
        
        //User input
        cout << "Enter n: ";
        cin >> n;
        cout << "Enter k: ";
        cin >> k;
        if(n<0) break;
        
        //Solution/backtracking algorithm
        int* q = new int[k]; //q[bishop] is a square on the n*n grid
        int count = 0, b = 0, t;
        q[b] = 0;
        
        while(true){
            //until we found all the possible solutions
            while(b<k){
                //for each bishop
                
                while(q[b]<n*n){
                    //for each square
                    if(ok(q,b,n)) break;
                    else q[b]++;
                }
                
                if(q[b] == n*n){
                    backtrack(b, count);
                    q[b]++;
                    continue;
                }else{
                    t = q[b];
                    b++;
                    q[b] = t;
                }
            }
            count++;
            backtrack(b, count);
            q[b]++;
        }
    }
    return 0;
}


Add a comment
Know the answer?
Add Answer to:
The problem Write a program that inputs two integers n and k, where n>=k. Your program...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions
  • WRITE A JAVA PROGRAM using STACKS and backtracing to solves the N Queens Problem . The...

    WRITE A JAVA PROGRAM using STACKS and backtracing to solves the N Queens Problem . The program takes the user's input integer for N and prints out all the solutions for N . The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two queens attack each other. For example, the following is the output for 4 entered for userinput. Output for 4 Queens : 1- * * Q * Q *...

  • Main objective: Solve the n queens problems. You have to place n queens on an n...

    Main objective: Solve the n queens problems. You have to place n queens on an n × n chessboard such that no two attack each other. Important: the chessboard should be indexed starting from 1, in standard (x, y) coordinates. Thus, (4, 3) refers to the square in the 4th column and 3rd row. We have a slight twist in this assignment. We will take as input the position of one queen, and have to generate a solution with a...

  • Write a C program named space_to_line.c that features a while loop that continuously reads input from...

    Write a C program named space_to_line.c that features a while loop that continuously reads input from the user one character at a time and then prints that character out. The exception is that if the user inputs a space character (‘ ‘), then a newline character (‘\n’) should be printed instead. This will format the output such that every word the user inputs is on its own line. Other than changing the spaces to newlines, the output should exactly match...

  • CMPS 12B Introduction to Data Structures Programming Assignment 2 In this project, you will write...

    can i get some help with this program CMPS 12B Introduction to Data Structures Programming Assignment 2 In this project, you will write a Java program that uses recursion to find all solutions to the n-Queens problem, for 1 Sns 15. (Students who took CMPS 12A from me worked on an iterative, non-recursive approach to this same problem. You can see it at https://classes.soe.ucsc.edu/cmps012a/Spring l8/pa5.pdf.) Begin by reading the Wikipcdia article on the Eight Queens puzzle at: http://en.wikipedia.org/wiki/Eight queens_puzzle In...

  • Please write in the Julia Language. Consider a steel rod. Write a program which will calculate th...

    Please write in the Julia Language. Consider a steel rod. Write a program which will calculate the temperature profile in the rod using a finite difference scheme. The user should enter the length of the rod (L), the value for k (= 65 W/mK), and a value for q in W/m^3. The user should also enter the number of intervals N ,(so you can calculate Δx=L/N). The user should also enter the end temperatures. Your program should create the matrix...

  • Write a program that reads an integer k from user and finds the number of elements...

    Write a program that reads an integer k from user and finds the number of elements that are divisible by k in the file assignment4.txt. A number n is divisible by k if n = kx for some integer x > 0. You can use the mod operator % to test for divisibility. The file assign4.txt has integer values in the range [0,100 ]. You should use end-of-file controlled loop for this problem. Sample execution is given below. Assume the...

  • 21 Write a program that asks the user to input the length and breadth of a...

    21 Write a program that asks the user to input the length and breadth of a soccer field, and then computes and returns the number of square meters of grass required to cover the field The formula for the area is the product of length and breadth (5) 22 The following program uses the break statement to terminate an infinite while loop to print 5 numbers Rewrite the program to use a while loop to display numbers from 1 to...

  • please explain/ comment 3. Eight Queens Write a program that places eight queens on a chessboard...

    please explain/ comment 3. Eight Queens Write a program that places eight queens on a chessboard (8 x 8 board) such that no queen is "attacking" another. Queens in chess can move vertically, horizontally, or diagonally. How you solve this problem is entirely up to you. You may choose to write a recursive program or an iterative (i.e., non-recursive) program. You will not be penalized/rewarded for choosing one method or another. Do what is easiest for you. 3.1. Output Below...

  • Write a java program that will print if n numbers that the user will input are...

    Write a java program that will print if n numbers that the user will input are or not within a range of numbers. For that, your program needs to ask first for an integer number called N that will represent the number of times that will ask for other integer numbers. Right after, it should ask for two numbers that will represent the Min and Max for a range. Lastly. it will iterate N number times asking for an integer...

  • Task Algorithms: Pattern Matching (in java) Write a program that gets two strings from user, size...

    Task Algorithms: Pattern Matching (in java) Write a program that gets two strings from user, size and pattern, and checks if pattern exists inside size, if it exists then program returns index of first character of pattern inside size, otherwise it returns -1. The method should not use built-in methods such as indexOf , find, etc. Only charAt and length are allowed to use. Analyze the time complexity of your algorithm. Your solution is not allowed to be> = O...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT