Exercise 8.22 on textbook pages 340 – 341 describes the Knight’s Tour problem, o
ID: 3576421 • Letter: E
Question
Exercise 8.22 on textbook pages 340 – 341 describes the Knight’s Tour problem, originally proposed by the mathematician Euler. The Knight’s Tour problem asks this question: “Can the chess piece called the knight move around an empty chessboard and visit each of the 64 squares once and only once?” Please read the textbook for a detailed description of the problem.
Exercise 8.22 (b) and (c) ask you to create two C# apps for this problem. The following is a brief description of these two parts. Please see the textbook for detailed directions and requirements of the two apps.
In part (b) you are asked to write an app to move the knight around the chessboard. The app randomly picks a square on the chessboard as the initial position of the knight. It then uses the directions described in the textbook to move the knight around until either all squares have been visited or no valid move is possible. Store the numbers 1 through 64 in the squares to indicate the sequence of moves took by the knight. For example, if the upper-left corner of the chessboard is randomly picked as the initial position of the knight, store 1 in that square (which is cell [0,0] in a two-dimensional array). If the program then moves the knight one row down and two columns to the right, store 2 in cell [1,2] in the array. If the program then moves the knight another row down and another two columns to the right, store 3 in cell [2,4] in the array. Continue this until the knight has nowhere to go.
The following is the output of a test run of the program:
The tour ended with 37 moves.
This was not a full tour.
0 1 12 37 4 9 20 7
13 36 3 10 19 6 25 22
2 11 18 5 24 21 8 27
0 14 35 30 17 26 23 0
0 31 16 0 34 0 28 0
15 0 33 0 29 0 0 0
32 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
The number in each cell of the 8 by 8 array indicates when that cell was visited by the knight. Cells with 0’s are cells that were never visited. Since the tour ended with 37 moves, we see number 1 through 37 in the cells. The following is the output of another test run of the program:
The tour ended with 45 moves.
This was not a full tour.
0 9 20 45 12 7 4 15
21 44 11 8 3 14 39 6
10 19 2 13 38 5 16 29
1 22 43 32 17 28 37 40
0 33 18 0 36 41 30 27
23 0 35 42 31 26 0 0
34 0 0 25 0 0 0 0
0 24 0 0 0 0 0 0
The tour ends with 45 moves. Most test runs will have somewhere between 30 and 50 moves.
Please submit your complete C# project for Exercise 8.22(b) to Blackboard.
Exercise 8.22(c) asks you to rewrite the program with a new algorithm. An accessibility number is assigned to each cell to indicate how accessible the cell is. In every step, compare the possible moves and move the knight to the cell with the lowest accessibility. Since this makes later moves easier, the new algorithm will end up having more moves than before.
Please read page 341 of the textbook for a detailed description of this program. The textbook tells you to pick one of the four corners as the initial position of the knight. Do not follow this direction. Instead, pick a random position anywhere in the chessboard as the initial position just like what you do in Exercise 8.22 (b).
The following is the output of a test run of the program:
The tour ended with 57 moves.
This was not a full tour.
10 7 12 27 38 5 22 25
13 28 9 6 23 26 37 4
8 11 0 39 44 51 24 21
29 14 43 50 0 36 3 52
42 49 40 45 0 0 20 35
15 30 0 0 57 0 53 2
48 41 32 17 46 55 34 19
31 16 47 56 33 18 1 54
The tour ends with 57 moves. Most test runs with this new algorithm will have 55 moves or more.
Explanation / Answer
using System;
public class Knight{
Random rand = new Random();
int rowSize, colSize;
int [,] accessibility;
int [,] board;
// possible 8 moves
int[] horizontal = { 2, 1, -1, -2, -2, -1, 1, 2 };
int[] vertical = { -1, -2, -2, -1, 1, 2, 2, 1 };
public Knight(){
rowSize = 8;
colSize = 8;
accessibility = new int[rowSize, colSize];
GenerateAccessibility();
board = new int[rowSize, colSize];
}
// check if particular box is inside board or not
private bool IsInsideBoard(int r, int c){
if(r >= rowSize || c >= colSize || r < 0 || c < 0)return false;
return true;
}
// check if its knight next move is valid move or not
private bool ValidMoves(int r, int c){
if(r >= rowSize || c >= colSize || r < 0 || c < 0 || board[r,c] != 0)return false;
return true;
}
private void GenerateAccessibility(){
for(int i = 0;i < rowSize; ++i){
for(int j = 0;j < colSize;++j){
int cnt = 0;
// if accessible then increase count
// check all possible 8 moves
for(int k = 0;k < 8; ++k){
int r = i + vertical[k], c = j + horizontal[k];
cnt += (IsInsideBoard(r, c)?1:0);
}
accessibility[i, j] = cnt;
}
}
}
public void Tour(){
int moves = 0;
int r = rand.Next(8), c = rand.Next(8); // randomly generate first position of knight
board[r, c] = ++moves;
while(true){
// check all possible 8 moves
bool knightCanMove = false;
for(int i = 0;i < 8; ++i){
int newR = r + vertical[i], newC = c + horizontal[i];
if(ValidMoves(newR, newC)){
knightCanMove = true;
r = newR;
c = newC;
board[r, c] = ++moves;
break;
}
}
// if knight can't move further
if(!knightCanMove){
break;
}
}
}
public void PrintAccessibility(){
for(int i = 0;i < rowSize; ++i){
for(int j = 0;j < colSize; ++j){
Console.Write(accessibility[i, j]+" ");
}
Console.WriteLine();
}
}
public void PrintBoard(){
for(int i = 0;i < rowSize; ++i){
for(int j = 0;j < colSize; ++j){
Console.Write(board[i, j]+" ");
}
Console.WriteLine();
}
}
public static void Main(string []args){
Knight game = new Knight();
//game.PrintAccessibility();
game.Tour();
game.PrintBoard();
}
}
The tour ends with 36 moves
That was not full tour
3 36 13 22 1 6 11 18
14 23 2 5 12 17 8 31
35 4 21 16 7 30 19 10
24 15 34 0 20 9 32 0
0 0 0 26 33 0 29 0
0 25 0 0 28 0 0 0
0 0 27 0 0 0 0 0
0 0 0 0 0 0 0 0
The tour ends with 42 moves
That was not full tour
7 42 25 14 5 10 19 12
26 15 6 9 18 13 4 21
41 8 17 24 3 20 11 36
16 27 2 39 30 35 22 33
1 40 29 0 23 32 37 0
28 0 0 31 38 0 34 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
c)
using System;
public class Knight{
Random rand = new Random();
int rowSize, colSize;
int [,] accessibility;
int [,] board;
int maxMoves;
// possible 8 moves
int[] horizontal = { 2, 1, -1, -2, -2, -1, 1, 2 };
int[] vertical = { -1, -2, -2, -1, 1, 2, 2, 1 };
public Knight(){
rowSize = 8;
colSize = 8;
accessibility = new int[rowSize, colSize];
GenerateAccessibility();
board = new int[rowSize, colSize];
}
// check if particular box is inside board or not
private bool IsInsideBoard(int r, int c){
if(r >= rowSize || c >= colSize || r < 0 || c < 0)return false;
return true;
}
// check if its knight next move is valid move or not
private bool ValidMoves(int r, int c){
if(r >= rowSize || c >= colSize || r < 0 || c < 0 || board[r,c] != 0)return false;
return true;
}
private void GenerateAccessibility(){
for(int i = 0;i < rowSize; ++i){
for(int j = 0;j < colSize;++j){
int cnt = 0;
// if accessible then increase count
// check all possible 8 moves
for(int k = 0;k < 8; ++k){
int r = i + vertical[k], c = j + horizontal[k];
cnt += (IsInsideBoard(r, c)?1:0);
}
accessibility[i, j] = cnt;
}
}
}
public void Tour(){
int moves = 0;
int r = rand.Next(8), c = rand.Next(8); // randomly generate first position of knight
board[r, c] = ++moves;
while(true){
// check all possible 8 moves
bool knightCanMove = false;
int r1 = -1, c1 = -1, minAccessible = 10;
for(int i = 0;i < 8; ++i){
int newR = r + vertical[i], newC = c + horizontal[i];
if(ValidMoves(newR, newC)){
knightCanMove = true;
if(minAccessible > accessibility[newR, newC]){
// find the minimum accessible box
minAccessible = accessibility[newR, newC];
r1 = newR;
c1 = newC;
}
}
}
// if knight can't move further
if(!knightCanMove){
break;
}
// assign to new min accessible box
r = r1;
c = c1;
board[r, c] = ++moves;
}
maxMoves = moves;
}
public void PrintAccessibility(){
Console.WriteLine("Accessibility of knight in the board");
for(int i = 0;i < rowSize; ++i){
for(int j = 0;j < colSize; ++j){
Console.Write(accessibility[i, j]+" ");
}
Console.WriteLine();
}
}
public void PrintBoard(){
Console.WriteLine("The tour ends with "+maxMoves+" moves");
if(maxMoves == 64){
Console.WriteLine("That was full tour");
}else{
Console.WriteLine("That was not full tour");
}
for(int i = 0;i < rowSize; ++i){
for(int j = 0;j < colSize; ++j){
Console.Write(board[i, j]+" ");
}
Console.WriteLine();
}
}
public static void Main(string []args){
Knight game = new Knight();
//game.PrintAccessibility();
game.Tour();
game.PrintBoard();
}
}
The tour ends with 51 moves
That was not full tour
23 20 39 6 25 10 41 8
38 5 24 21 40 7 26 11
19 22 51 0 35 0 9 42
4 37 34 0 50 0 12 27
33 18 49 36 0 0 43 0
48 3 0 0 0 0 28 13
17 32 1 46 15 30 0 44
2 47 16 31 0 45 14 29
The tour ends with 57 moves
That was not full tour
23 38 19 4 33 48 17 2
20 5 22 37 18 3 32 47
39 24 57 34 49 0 1 16
6 21 50 0 36 55 46 31
25 40 35 56 0 0 15 54
10 7 0 51 0 0 30 45
41 26 9 12 43 28 53 14
8 11 42 27 52 13 44 29
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.