- 9th Apr 2023
- 05:49 am
- Admin
C# Homework Question
C# Logical Puzzles, Games, and Algorithms: Knight Tour
C# Homework Solution
using System;
using System.Collections.Generic;
namespace KnightTour
{
class Program
{
static int size = 8; // size of the board
static int[,] board = new int[size, size]; // chess board
static int[] xOffset = { 2, 1, -1, -2, -2, -1, 1, 2 }; // x-axis movement of knight
static int[] yOffset = { 1, 2, 2, 1, -1, -2, -2, -1 }; // y-axis movement of knight
static void Main(string[] args)
{
SolveKnightTour();
}
static void SolveKnightTour()
{
int startX = 0;
int startY = 0;
int moveNumber = 1;
board[startX, startY] = moveNumber; // mark the starting square as visited
while (moveNumber < size * size) // while there are still unvisited squares
{
List> moves = GetPossibleMoves(startX, startY);
if (moves.Count == 0) // if there are no more possible moves from current position
{
Console.WriteLine("No solution found");
return;
}
Tuple nextMove = ChooseNextMove(moves); // select the next move
startX = nextMove.Item1;
startY = nextMove.Item2;
moveNumber++;
board[startX, startY] = moveNumber; // mark the next square as visited
}
PrintBoard();
}
static List> GetPossibleMoves(int x, int y)
{
List> moves = new List>();
for (int i = 0; i < xOffset.Length; i++)
{
int nextX = x + xOffset[i];
int nextY = y + yOffset[i];
if (nextX >= 0 && nextX < size && nextY >= 0 && nextY < size && board[nextX, nextY] == 0)
{
moves.Add(Tuple.Create(nextX, nextY));
}
}
return moves;
}
static Tuple ChooseNextMove(List> moves)
{
List> nextMoves = new List>();
foreach (var move in moves)
{
int x = move.Item1;
int y = move.Item2;
int count = GetPossibleMoves(x, y).Count;
nextMoves.Add(Tuple.Create(x, y, count));
}
nextMoves.Sort((a, b) => a.Item3.CompareTo(b.Item3)); // sort the moves by the number of possible moves from that square
return nextMoves[0];
}
static void PrintBoard()
{
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
Console.Write(board[i, j].ToString().PadLeft(2) + " ");
}
Console.WriteLine();
}
}
}
}
The program starts by initializing a chess board of size 8x8 and placing the knight on the top-left square. It then iteratively selects the next move using Warnsdorff's algorithm, which selects the move that has the fewest number of unvisited squares reachable from that square. If there are multiple moves