C# Homework Help - Puzzles, Games, and Algorithms: Knight Tour

C# Homework Help

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