CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 5 of 5
  1. #1
    Join Date
    Feb 2021
    Posts
    2

    Knight's tour, recursion, dynamic programming, optimization

    Hello everyone. I am just a beginner programmer.
    I am learning recursion and dynamic programming.
    I realized that even for Fibonacci numbers, recursion is not suitable - and there you need to use dynamic programming.

    Well, I looked at the tutorials, it's good when you can deduce the recurrent relation and then everything is clear...
    But if we cannot do it, how then?
    ????
    For example, I took the famous task "Knight's tour" and solved it using recursion.

    Code:
    using System;
     
    namespace KnightChess
    {
        class Field
        {
            public int index { get; set; }
            public Field(int _index)
            {
                index = _index;
            }
        }
        class Board
        {
            int height;
            int width;
            public (int, int) curKnightPos;
            int value;
            public Field[,] boardArr;
            public static bool CanMoveKnight1(Board Board)
            {
                return (Board.width > Board.curKnightPos.Item1 + 1) && (Board.height > Board.curKnightPos.Item2) &&
                        (Board.boardArr[Board.curKnightPos.Item1 + 1, Board.curKnightPos.Item2].index == -1);
            }
            public static Board MoveKnight1(Board Board)
            {
                Board Transformed = new Board(Board);
                Transformed.curKnightPos.Item1 += 2;
                Transformed.curKnightPos.Item2++;
                Transformed.boardArr[Transformed.curKnightPos.Item1 - 1, Transformed.curKnightPos.Item2 - 1].index = ++Transformed.value;
     
                return Transformed;
            }
            public static bool CanMoveKnight2(Board Board)
            {
                return (Board.width > Board.curKnightPos.Item1) && (Board.height > Board.curKnightPos.Item2 + 1) &&
                        (Board.boardArr[Board.curKnightPos.Item1, Board.curKnightPos.Item2 + 1].index == -1);
            }
            public static Board MoveKnight2(Board Board)
            {
                Board Transformed = new Board(Board);
                Transformed.curKnightPos.Item1++;
                Transformed.curKnightPos.Item2 += 2;
                Transformed.boardArr[Transformed.curKnightPos.Item1 - 1, Transformed.curKnightPos.Item2 - 1].index = ++Transformed.value;
     
                return Transformed;
            }
            public static bool CanMoveKnight3(Board Board)
            {
                return (Board.curKnightPos.Item1 > 1) && (Board.height > Board.curKnightPos.Item2 + 1) &&
                        (Board.boardArr[Board.curKnightPos.Item1 - 2, Board.curKnightPos.Item2 + 1].index == -1);
            }
            public static Board MoveKnight3(Board Board)
            {
                Board Transformed = new Board(Board);
                Transformed.curKnightPos.Item1--;
                Transformed.curKnightPos.Item2 += 2;
                Transformed.boardArr[Transformed.curKnightPos.Item1 - 1, Transformed.curKnightPos.Item2 - 1].index = ++Transformed.value;
     
                return Transformed;
            }
            public static bool CanMoveKnight4(Board Board)
            {
                return (Board.curKnightPos.Item1 > 2) && (Board.height > Board.curKnightPos.Item2) &&
                        (Board.boardArr[Board.curKnightPos.Item1 - 3, Board.curKnightPos.Item2].index == -1);
            }
            public static Board MoveKnight4(Board Board)
            {
                Board Transformed = new Board(Board);
                Transformed.curKnightPos.Item1 -= 2;
                Transformed.curKnightPos.Item2++;
                Transformed.boardArr[Transformed.curKnightPos.Item1 - 1, Transformed.curKnightPos.Item2 - 1].index = ++Transformed.value;
     
                return Transformed;
            }
            public static bool CanMoveKnight5(Board Board)
            {
                return (Board.curKnightPos.Item1 > 2) && (Board.curKnightPos.Item2 > 1) &&
                        (Board.boardArr[Board.curKnightPos.Item1 - 3, Board.curKnightPos.Item2 - 2].index == -1);
            }
            public static Board MoveKnight5(Board Board)
            {
                Board Transformed = new Board(Board);
                Transformed.curKnightPos.Item1 -= 2;
                Transformed.curKnightPos.Item2--;
                Transformed.boardArr[Transformed.curKnightPos.Item1 - 1, Transformed.curKnightPos.Item2 - 1].index = ++Transformed.value;
     
                return Transformed;
            }
            public static bool CanMoveKnight6(Board Board)
            {
                return (Board.curKnightPos.Item1 > 1) && (Board.curKnightPos.Item2 > 2) &&
                        (Board.boardArr[Board.curKnightPos.Item1 - 2, Board.curKnightPos.Item2 - 3].index == -1);
            }
            public static Board MoveKnight6(Board Board)
            {
                Board Transformed = new Board(Board);
                Transformed.curKnightPos.Item1--;
                Transformed.curKnightPos.Item2 -= 2;
                Transformed.boardArr[Transformed.curKnightPos.Item1 - 1, Transformed.curKnightPos.Item2 - 1].index = ++Transformed.value;
     
                return Transformed;
            }
            public static bool CanMoveKnight7(Board Board)
            {
                return (Board.width > Board.curKnightPos.Item1) && (Board.curKnightPos.Item2 > 2) &&
                        (Board.boardArr[Board.curKnightPos.Item1, Board.curKnightPos.Item2 - 3].index == -1);
            }
            public static Board MoveKnight7(Board Board)
            {
                Board Transformed = new Board(Board);
                Transformed.curKnightPos.Item1++;
                Transformed.curKnightPos.Item2 -= 2;
                Transformed.boardArr[Transformed.curKnightPos.Item1 - 1, Transformed.curKnightPos.Item2 - 1].index = ++Transformed.value;
     
                return Transformed;
            }
            public static bool CanMoveKnight8(Board Board)
            {
                return (Board.width > Board.curKnightPos.Item1 + 1) && (Board.curKnightPos.Item2 > 1) &&
                        (Board.boardArr[Board.curKnightPos.Item1 + 1, Board.curKnightPos.Item2 - 2].index == -1);
            }
            public static Board MoveKnight8(Board Board)
            {
                Board Transformed = new Board(Board);
                Transformed.curKnightPos.Item1 += 2;
                Transformed.curKnightPos.Item2--;
                Transformed.boardArr[Transformed.curKnightPos.Item1 - 1, Transformed.curKnightPos.Item2 - 1].index = ++Transformed.value;
     
                return Transformed;
            }
            public static void Print(Board Board)
            {
                for (int i = Board.width - 1; i >= 0; i--)
                {
                    for (int j = 0; j < Board.height; j++)
                    {
                        Console.Write(Board.boardArr[i, j].index + " ");
                    }
                    Console.WriteLine();
                }
                Console.WriteLine();
            }
            public static bool isFull(Board Board)
            {
                foreach(var el in Board.boardArr)
                {
                    if (el.index == -1)
                    {
                        return false;
                    }
                }
     
                return true;
            }
     
            public Board(Board Board)
            {
                height = Board.height;
                width = Board.width;
                curKnightPos = Board.curKnightPos;
                value = Board.value;
                boardArr = new Field[width, height];
                for (int i = 0; i < width; i++)
                {
                    for (int j = 0; j < height; j++)
                    {
                        boardArr[i, j] = new Field(Board.boardArr[i, j].index);
                    }
                }
            }
            public Board(int _height, int _width, (int, int) _curKnightPos)
            {
                height = _height;
                width = _width;
                curKnightPos = _curKnightPos;
                value = 1;
                boardArr = new Field[_width, _height];
                for(int i = 0; i < _width; i++)
                {
                    for (int j = 0; j < _height; j++)
                    {
                        boardArr[i, j] = new Field(-1);
                    }
                }
                boardArr[_curKnightPos.Item1 - 1, _curKnightPos.Item2 - 1].index = 1;
            }
        }
        class Program
        {
            static void Main(string[] args)
            {
                #region input and define
                Console.WriteLine("Please enter board's width");
                string temp;
                temp = Console.ReadLine();
                int width;
                bool success;
                success = int.TryParse(temp, out width);
                if (!success)
                {
                    Console.WriteLine("Width be natural a number");
                    return;
                }
     
                Console.WriteLine("Please enter board's height");
                temp = Console.ReadLine();
                int height;
                success = int.TryParse(temp, out height);
                if (!success)
                {
                    Console.WriteLine("Height be natural a number");
                    return;
                }
     
                Console.WriteLine("Please enter board's curKnightPosX");
                temp = Console.ReadLine();
                int curKnightPosX;
                success = int.TryParse(temp, out curKnightPosX);
                if (!success)
                {
                    Console.WriteLine("CurKnightPosX be natural a number");
                    return;
                }
     
                Console.WriteLine("Please enter board's curKnightPosY");
                temp = Console.ReadLine();
                int curKnightPosY;
                success = int.TryParse(temp, out curKnightPosY);
                if (!success)
                {
                    Console.WriteLine("CurKnightPosY be natural a number");
                    return;
                }
     
                if ((curKnightPosX > width) || (curKnightPosY > height))
                {
                    Console.WriteLine("curKnightPos out of range");
                    return;
                }
     
                Board Board = new Board(height, width, (curKnightPosX, curKnightPosY));
                #endregion
     
                GetTransformsMap(Board);
                
                Console.ReadKey();
            }
            private static void GetTransformsMap(Board board)
            {
                if (!Board.CanMoveKnight1(board) && !Board.CanMoveKnight2(board) && !Board.CanMoveKnight3(board) && !Board.CanMoveKnight4(board) &&
                    !Board.CanMoveKnight5(board) && !Board.CanMoveKnight6(board) && !Board.CanMoveKnight7(board) && !Board.CanMoveKnight8(board))
                {
                    if (Board.isFull(board))
                    {
                        Board.Print(board);
                    }
                }
     
                if (Board.CanMoveKnight1(board))
                {
                    GetTransformsMap(Board.MoveKnight1(board));
                }
                if (Board.CanMoveKnight2(board))
                {
                    GetTransformsMap(Board.MoveKnight2(board));
                }
                if (Board.CanMoveKnight3(board))
                {
                    GetTransformsMap(Board.MoveKnight3(board));
                }
                if (Board.CanMoveKnight4(board))
                {
                    GetTransformsMap(Board.MoveKnight4(board));
                }
                if (Board.CanMoveKnight5(board))
                {
                    GetTransformsMap(Board.MoveKnight5(board));
                }
                if (Board.CanMoveKnight6(board))
                {
                    GetTransformsMap(Board.MoveKnight6(board));
                }
                if (Board.CanMoveKnight7(board))
                {
                    GetTransformsMap(Board.MoveKnight7(board));
                }
                if (Board.CanMoveKnight8(board))
                {
                    GetTransformsMap(Board.MoveKnight8(board));
                }
            }
        }
    }
    We enter the size of the board and the coordinates of the initial position of the knight - after which the calculation takes place.
    Video attached

    https://dropmefiles.com/eeM8j

    As you can see from the video for 8x8, we get one of the solutions in a reasonable amount of time.
    But if the task is to get all the solutions?
    Even for 6x6 it already freezes - everything depends on memory, I have 8GB of RAM.

    Help, how can this example be optimized to get ALL solutions?
    Will it change anything if rewritten in C ++ or there in python?

  2. #2
    Join Date
    Feb 2017
    Posts
    618

    Re: Knight's tour, recursion, dynamic programming, optimization

    Quote Originally Posted by Tricui11 View Post
    Help, how can this example be optimized to get ALL solutions?
    Will it change anything if rewritten in C ++ or there in python?
    The Wikipedia entry to Knight's tour,

    https://en.wikipedia.org/wiki/Knight%27s_tour

    reveals that there are 26,534,728,821,064 (directed closed) tours on an 8x8 board. It will take a lot of time to generate them all regardless of algorithm and programming language.

  3. #3
    Join Date
    Feb 2021
    Posts
    2

    Re: Knight's tour, recursion, dynamic programming, optimization

    Quote Originally Posted by wolle View Post
    The Wikipedia entry to Knight's tour,

    https://en.wikipedia.org/wiki/Knight%27s_tour

    reveals that there are 26,534,728,821,064 (directed closed) tours on an 8x8 board. It will take a lot of time to generate them all regardless of algorithm and programming language.

    I understand. Ok I mean my algorithm very ineffective. How it can be improved according dynamic programming for example?
    ...or may be even according your wiki page it will be "Neural network solutions"...

  4. #4
    Join Date
    Feb 2017
    Posts
    618

    Re: Knight's tour, recursion, dynamic programming, optimization

    Quote Originally Posted by Tricui11 View Post
    I understand. Ok I mean my algorithm very ineffective. How it can be improved according dynamic programming for example?
    ...or may be even according your wiki page it will be "Neural network solutions"...
    Dynamic programming is an optimization method and as such is used when you are looking for what is best in some sense. It could be to find the shortest or the cheapest of something. But that does not apply here since all tours are considered equal. It makes this a purely combinatorial problem. The link I provided suggests there are Divide-and-conquer algorithms available that finish in linear time O(N). That is very fast, and these kinds of algorithms are suitable for recursive solutions. To me, it looks like a recursive Divide-and-conquer algorithm with linear complexity may fit the bill. But remember that recursion itself does not make an algorithm faster. It is more that it suits recursively formulated problems.
    Last edited by wolle; March 5th, 2021 at 03:37 PM.

  5. #5
    Join Date
    Feb 2017
    Posts
    618

    Re: Knight's tour, recursion, dynamic programming, optimization

    Quote Originally Posted by wolle View Post
    But that does not apply here since all tours are considered equal. It makes this a purely combinatorial problem.
    But the Knight's tour can be formulated as an optimization problem, so I guess my claim is wrong.

    One can define the distance between two squares as the fewest moves it takes for the knight to go between them. Then the optimization problem becomes to find the shortest route the knight can take to visit all squares once. It is the Traveling salesman problem, and it is NP-hard. So I suppose it is correct to say that even though the Knight's tour is solvable by optimization, it is inefficient.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured