Knight's tour, recursion, dynamic programming, optimization

[Tricui11]

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.
:thumbsup:
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.

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?

[Banfa]

The logic in you CanMoveKnight?? functions is not right in many cases and doesn't match the logic in your MoveKnight?? functions so the CanMoveKnight?? don't actually verify that a given move is valid.

I guess that in finding the first solution somehow you avoid the inherent issues but in finding all solutions you hit them and that causes the logic of the whole program to fail.

[Tricui11]

https://www.youtube.com/watch?v=wEPElbWsFXQ&t=5s

Logic in CanMoveKnight is - If knight near border of the board - that can't possible move there... also if field is not empty...
it's reason why we must check it

concerning second part - PROGRAM WORKS WITH OUT ERRORS, but needs realy much RAM - how to avoid it?
that makes sense of dynamic programming, and advanced in comparison with recursion in my understanding...

[Rabbit]

I see the recursion in your code, but I see no dynamic programming. Where's the memoization?

[Banfa]

The memory usage I think must come from you allocating a new board every time a MoveKnight?? function is called.

It is possible to implement this algorithm either with a single board or building up an array of coordinates defining the knights path, which should never have more than 64 entries (or board height x board width).

That said you also should not get more than 64 (or board height x board width) boards using your current algorithm and although that is a bit wasteful I wouldn't expect it to be a lot of RAM, about 532 bytes per board, or about 34kbytes all told.

So how much RAM is being used? What do you consider a lot?

[Tricui11]

Rabbit, sense of the topic - I ask You to help me optimize my recursion algorithm according dynamic programming or may be any another one like Neural network solutions, etc.

By wiki
https://en.wikipedia.org/wiki/Knight%27s_tour
there are several different available algorithms...

[Tricui11]

https://github.com/Tricui11/KnightChess

Just comitted "int to sbyte" (from 4 bytes to 1 byte memory retrenchment) - byt just a little improvement...

I wonder by google there are several open solutions are already exists on github (Neural network mostly),
but I ask PROs to help me understand me how can I improve my algorithm? :):):)

Banfa, yes I create a new board every time a MoveKnight, otherwise if change current board by MoveKnight1 for example,
we can not call it after for another Move actions (MoveKnight2, MoveKnight3, MoveKnight4...)

[Rabbit]

I just read the wiki, and what you want to do is unfeasible. It says there are algorithms to find a single path. But it's computationally unfeasible to find all paths. For an 8x8, there are 19.5 quadrillion such paths, trying to list them all is just not possible in any amount of time.

[Tricui11]

Rabbit, OK, task is find 1000 paths in a reasonable amount of time.

[Rabbit]

There's no computationally feasible way to guarantee finding a specified number of paths either, because while there are 19.5 quadrillion complete paths, there are 4 x 10^51 total paths. There's no way to guarantee that you will find 1000 paths without getting stuck exploring many many incomplete paths. The best you can do is use one of the algorithms suggested in the wiki and keep exploring but stop after a predetermined amount of time has passed.