Exercise 19 in page 393. You can devise Knights\' tour very similar to N-Queens
ID: 3539413 • Letter: E
Question
Exercise 19 in page 393. You can devise Knights' tour very similar to N-Queens problem. Feel free to discuss the type of changes you need to implement Knights' tour in the forum.
(Knights Tour) This chapter described the backtracking algorithm and how to use recursion to implement it. Another well known chessboard problem that can be resolved using the backtracking algorithm is a knights tour. Given an initial board position, determine a sequence of moves by a knight that visits every square of the chessboard exactly once. For example for a 5 x 5 and 6 x 6 square board, the sequence of moves are shown below:
1 6 15 10 21 1 16 7 26 11 14
14 9 20 5 16 34 25 12 15 6 27
19 2 7 22 11 17 2 33 8 13 10
8 13 24 17 4 32 35 24 21 8 5
25 18 3 12 23 23 18 3 30 9 20
36 31 22 19 4 29
A knight moves by jumping two positions either vertically or horizontally and one position in the perpendicular direction. Write a recursive backtracking program that takes as input an initial board position and determines a sequence of moves by a knight that visits each square of the board exactly once.
Knights Tour
class knightsTour
{
public:
knightsTour(int size = 8);
void print();
...
private:
...
int boardSize;
int board[50][50];
};
Knights TourImp
#include <iostream>
#include <iomanip>
#include "knightsTour.h"
using namespace std;
knightsTour::knightsTour(int size)
{
boardSize = size;
numberOfSolutions = 0;
for(int i = 0; i < boardSize; i++)
for(int j = 0; j < boardSize; j++)
board[i][j] = 0;
}
void knightsTour::print()
{
for(int i = 0; i < boardSize; i++)
{
for(int j = 0; j < boardSize; j++)
cout<<setw(4)<<board[i][j]<<" ";
cout<<endl;
}
cout<<endl<<endl;
}
...TestKnightsTour
//Chapter 6: Programing Exercise 18
#include <iostream>
#include "knightsTour.h"
using namespace std;
int main()
{
knightsTour knight(5);
...
}
NQueens Puzzle
class nQueensPuzzle
{
public:
nQueensPuzzle(int queens = 8);
//constructor
//Postcondition: noOfSolutions = 0; noOfQueens = queens;
// queensInRow is a pointer to the array
// that store the n-tuple.
// If no value is specified for the parameter queens,
// the default value, which is 8, is assigned to it.
bool canPlaceQueen(int k, int i);
//Function to determine whether a queen can be placed
//in row k and column i.
//Postcondition: returns true if a queen can be placed in
// row k and column i; otherwise it returns false
void queensConfiguration(int k);
//Function to determine all solutions to the n-queens
//puzzle using backtracking.
//The function is called with the value 0.
//Postcondition: All n-tuples representing solutions of
// n-queens puzzle are generated and printed.
void printConfiguration();
//Function to output an n-tuple containing a solution
//to the n-queens puzzle.
int solutionsCount();
//Function to return the total number of solutions.
//Postcondition: The value of noOfSolution is returned.
private:
int noOfSolutions;
int noOfQueens;
int *queensInRow;
};
NQueens Puzzle.Imp
#include <iostream>
#include <cmath>
#include "nQueenPuzzle.h"
using namespace std;
nQueensPuzzle::nQueensPuzzle(int queens)
{
noOfQueens = queens;
queensInRow = new int[noOfQueens];
noOfSolutions = 0;
}
bool nQueensPuzzle::canPlaceQueen(int k, int i)
{
for(int j = 0; j < k; j++)
if((queensInRow[j] == i)
|| (abs(queensInRow[j] - i) == abs(j-k)))
return false;
return true;
}
void nQueensPuzzle::queensConfiguration(int k)//, int queens)
{
for(int i = 0; i < noOfQueens; i++)
{
if(canPlaceQueen(k, i))
{
queensInRow[k] = i;
if(k == noOfQueens - 1)
printConfiguration();
else
queensConfiguration(k + 1);
}
}
}
void nQueensPuzzle::printConfiguration()
{
noOfSolutions++;
cout<<"(";
for(int i = 0; i < noOfQueens - 1; i++)
cout<<queensInRow[i]<<", ";
cout<<queensInRow[noOfQueens - 1]<<")"<<endl;
}
int nQueensPuzzle::solutionsCount()
{
return noOfSolutions;
}
Test NQueensPuzzle
#include <iostream>
#include <cmath>
#include "nQueenPuzzle.h"
using namespace std;
int main()
{
int nqueens;
cout<<"Enter the board size: ";
cin>>nqueens;
nQueensPuzzle queens(nqueens);
queens.queensConfiguration(0);
cout<<"Number of Solutions: "<<queens.solutionsCount()<<endl;
return 0;
}
Explanation / Answer
code is not working unfortunately.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.