CS300 - Homework #1 – Knight to the Rescue - Solved

In this homework, first, you will implement a program that will generate a chessboard of size NxN, where N represents the columns and rows. Then, you will need to implement a function that will place a certain number of pawns on the board based on given conditions. Finally, you will implement another function to place a knight and a king on the chessboard and check if the knight can rescue the king without touching any of the previously placed pawns. 

To do this homework, you are required to implement a Stack​ using a LinkedList​ data structure,​ i.e., you can not use vectors in the stack implementation. The stack class MUST​ be template-based. You may want to store basic data types, structs or classes in this stack.  

Program Flow 

        ●    Chessboard Generation
The chessboard will be represented as an NxN 2-dimensional vector (i.e. matrix) where N is going to be an input to your program given by the user. The left bottom of the chessboard will be considered as the (1,1) coordinate. The size of the chessboard must be limited to be in this range 4 < N < 11 where your program must do an input check. 

We expect each cell of the chessboard to be a stackNode​ that​ may contain the following information but you are not limited to storing only these fields, you may keep any other extra fields as needed: 

1.    x_coordinate 

2.    y_coordinate 

3.    visited 

4.    has_pawn 

        ●    Pawn Placement
Once the chessboard is generated, you’ll start to place the pawns with the following constraints: 

●     The number of pawns will also be an input to your program and must be limited to be 3N the most where your program must do an input check. For example, if N=8, the number of pawns can be 24 at most. 

●     The first pawn will be placed at coordinate (1,1). 

●     Each pawn following the previous pawn will be placed on a neighbouring cell depending on availability. 

●     On the chessboard, each row, column and diagonal can hold a maximum​ number of 3 pawns.​ 

Once all the pawns are all placed, your program will print out the coordinates of the pawns reading from your stack and also show the chessboard as a matrix. 

For example, the following placements of 5 pawns on an 8x8 chessboard are invalid​ because there are 4 pawns on a row in the first picture, on a diagonal on the second and a column on the third picture (your program must avoid such invalid placements): 

  

 

An example of a valid​ placement​ on an 8x8 chess boards with 20 pawns is below, note that there is no row or column or diagonal with more than 3 pawns in this chess board shown below: 

  

 

 

 

 

The following table shows the first 10 steps of possible pawn placements for a chessboard of size N=8 and p=20 many pawns. The possible cells that one can place each pawn in are shown as red bordered cells below; your program at each step will pick one of these red cells randomly​ .​ 

Placement 

Trial 
Chessboard 
Available Spaces 
1 

Push (1,1) 
  
  
2  Push (1,2) 
  
  
3 

Push (1,3) 
  
  
 

4 

Push (2,3) 
  
  
5 

Push (3,3) 
  
  
6 

Push (2,4) 
  
  
7 

Push (4,1) 
  
  
 

8 

Push (3,2) 
  
  
9 

Push (3,1) 
  
No More Available Spaces 

But we still need to place more pawns 
10 Pop (3,1) and mark unavailable 
  
  
11 

Push (2,1) 
  
No More Available Spaces 

But we still need to place more pawns 
10 Pop (2,1) and mark unavailable 
  
No More Available Spaces that we visited from last-placed 

pawn (3,2) 
10 Pop (3,2) and mark unavailable 
  
  
 

 

        ●    Rescuing the King with the Knight
After the pawns are placed you’ll place your knight and king on two given available cells on the chessboard where the user will input these cell coordinates as input to your program. Then, you’ll check if your knight can rescue the king without touching any of the placed pawns on the chessboard. Then your program will print out the moves done by the knight. If there is no path to your king, then your program should indicate this by printing out “No Way!”​ .​ 

 

The knight moves​ in an “L-shape” — that is, they can move​ two squares in any direction vertically followed by one square horizontally, or two squares in any direction horizontally followed by one square vertically. Your​ knight can not move to a cell that’s occupied by the enemy pawn. The following diagrams show the possible moves of a knight on the chessboard: 

  

If your knight faces a deadlock where it can not move further and moves back (similar to the scenario that’s explained for pawns above), this cell should be marked as unavailable. Also in your output, we shouldn’t see moves like knight moves from (1,8) to (2,6) and back to (1,8). You should display​ the path that the knight takes to reach your king where the steps must not be repeated. That is, there shouldn't be any same coordinates in this path. 

Output Format 

The following example is the expected output format. You should write your output to a txt file named output.txt​ .​ Please note that the empty lines should be present in your output for it to work with the semi-automated grading tool. We expect N,​ P, Pawn Locations, Knight and King locations, Knight Moves and the Chessboard matrix (be careful to invert x and y values when you’re printing the matrix out) in your output exactly as they appear below: 

 

N = 8 

P = 24 

 

Pawn Locations 8                                               1 

7                                                              1 

6                                                              2 

5                                                              2 

4                                                              3 

5                                                              4 

6                                                              5 

 

7 4 
8 5 

8 6 
7 7 

6 7 

5 8 
4 8 
3 8 

3  7 

4  6 

3 6 

2 5 
2 4 

2 3 

1 3 

1 2 

1 1 

 

Knight = 1 8 

King = 8 8 

 

1 8 

2 6 
4 7 

3 5 

5 6 

4 4 

6 3 

4 2 

6 1 

5 3 

3 2 

5 1 

7 2 

6  4 

7  6 

8  8 

 

Matrix 

0 0 1 1 1 0 0 0  

0 0 1 0 0 1 1 0  

0 0 1 1 0 0 0 1  

0 1 0 0 0 1 0 1  

0  1 0 0 1 0 1 0  

1  1 0 1 0 0 0 0  

1 0 0 0 1 1 0 0  

1 0 0 0 0 0 1 1 

 

 

Sample Runs 

Sample Run 1  
Please enter the size of the board (n): ​8 Please enter the number of the pawns (p): ​16 The matrix: 

0 0 0 1 0 0 0 0  

0 0 1 1 1 0 0 0  

0 1 0 0 1 0 0 0  

0 0 1 0 0 1 0 0  

0  0 0 1 1 1 0 0  

1  1 1 0 0 0 0 0  

1  0 0 0 0 0 0 0  1 0 0 0 0 0 0 0  

Enter the position of knight(x,y): ​1 8 Enter the position of king(x,y): ​8 8 No way! 

 

Output File 

N = 8 

P = 16 

 

Pawn Locations 

6 4 

5  4 

6  5 

5 6 

5 7 

4 8 

4 7 

3 7 

2  6 

3  5 

4  4 

3 3 

2 3 

1 3 

1 2 

1 1 

 

Knight = 1 8 

King = 8 8 

 No Way! 

 

Matrix 

0 0 0 1 0 0 0 0  

0 0 1 1 1 0 0 0  

0 1 0 0 1 0 0 0  

0 0 1 0 0 1 0 0  

0  0 0 1 1 1 0 0  

1  1 1 0 0 0 0 0  

1 0 0 0 0 0 0 0  

1 0 0 0 0 0 0 0  

 

Sample Run 2 
Please enter the size of the board (n): 8​ 

Please enter the number of the pawns (p): 14​ 

0 1 0 0 1 1 0 0 

0 1 1 1 0 0 0 0 

0 0 1 0 0 0 0 0 

0 0 0 1 0 0 0 0 

0  0 0 1 0 0 0 0 

1  1 1 0 0 0 0 0 

1 0 0 0 0 0 0 0 

1  0 0 0 0 0 0 0 

Enter the position of knight(x,y): 1​ 8 Enter the position of king (x,y): 8​ 1 Path found, see the output file! 

 

Output File 

N = 8 

P = 14 

 

Pawn Locations 

6 8 

5 8 

4  7 

3 7 

2  8 

2  7 

3  6 

4  5 

4  4 

3  3 

2 3 

1 3 

1 2 

1 1 

 

Knight = 1 8 

King = 8 1 

 

1  8 

2  6 

3  8 

1  7 

2  5 

4  6 

6 5 

5 7 

7 8 

6  6 

7  4 

5 3 

3 2 

2 4 

1 6 

3 5 

5 6 

7 5 

5 4 

4 2 

6  3 

7  1 

5  2 

6  4 

8 3 

6 2 

8 1 

 

Matrix 

0 1 0 0 1 1 0 0  

0 1 1 1 0 0 0 0  

0 0 1 0 0 0 0 0  

0 0 0 1 0 0 0 0  

0  0 0 1 0 0 0 0  

1  1 1 0 0 0 0 0  

1 0 0 0 0 0 0 0  

1 0 0 0 0 0 0 0