Click here to Skip to main content
14,845,979 members
Home / Discussions / C#
   

C#

 
GeneralRe: Hacking Pin
Eddy Vluggen2-Mar-21 16:48
professionalEddy Vluggen2-Mar-21 16:48 
GeneralRe: Hacking Pin
trønderen2-Mar-21 17:38
Membertrønderen2-Mar-21 17:38 
GeneralRe: Hacking Pin
Eddy Vluggen6-Mar-21 10:10
professionalEddy Vluggen6-Mar-21 10:10 
GeneralRe: Hacking Pin
Mycroft Holmes1-Mar-21 11:02
professionalMycroft Holmes1-Mar-21 11:02 
GeneralRe: Hacking Pin
Pete O'Hanlon3-Mar-21 2:03
mvePete O'Hanlon3-Mar-21 2:03 
GeneralRe: Hacking Pin
Eddy Vluggen2-Mar-21 9:56
professionalEddy Vluggen2-Mar-21 9:56 
GeneralRe: Hacking Pin
Gerry Schmitz2-Mar-21 18:29
mveGerry Schmitz2-Mar-21 18:29 
QuestionKnight's tour, recursion, dynamic programming, optimization Pin
Kari Trust28-Feb-21 14:30
MemberKari Trust28-Feb-21 14:30 
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

DropMeFiles – free one-click file sharing service[^]

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?











AnswerRe: Knight's tour, recursion, dynamic programming, optimization Pin
trønderen28-Feb-21 15:59
Membertrønderen28-Feb-21 15:59 
GeneralRe: Knight's tour, recursion, dynamic programming, optimization Pin
Kari Trust2-Mar-21 2:04
MemberKari Trust2-Mar-21 2:04 
GeneralRe: Knight's tour, recursion, dynamic programming, optimization Pin
trønderen2-Mar-21 8:53
Membertrønderen2-Mar-21 8:53 
QuestionApplication crashes suddenly without any message [Solved] Pin
Alex Dunlop26-Feb-21 22:05
MemberAlex Dunlop26-Feb-21 22:05 
AnswerRe: Application crashes suddenly without any message Pin
BillWoodruff26-Feb-21 22:23
mveBillWoodruff26-Feb-21 22:23 
GeneralRe: Application crashes suddenly without any message Pin
Alex Dunlop26-Feb-21 22:29
MemberAlex Dunlop26-Feb-21 22:29 
GeneralRe: Application crashes suddenly without any message Pin
OriginalGriff26-Feb-21 22:35
mveOriginalGriff26-Feb-21 22:35 
AnswerRe: Application crashes suddenly without any message Pin
OriginalGriff26-Feb-21 22:32
mveOriginalGriff26-Feb-21 22:32 
GeneralRe: Application crashes suddenly without any message Pin
Alex Dunlop26-Feb-21 23:01
MemberAlex Dunlop26-Feb-21 23:01 
QuestionHow to reset TextBoxes at once? [Solved] Pin
Alex Dunlop25-Feb-21 7:06
MemberAlex Dunlop25-Feb-21 7:06 
AnswerRe: How to reset TextBoxes at once? Pin
Gerry Schmitz25-Feb-21 8:42
mveGerry Schmitz25-Feb-21 8:42 
GeneralRe: How to reset TextBoxes at once? Pin
OriginalGriff25-Feb-21 8:51
mveOriginalGriff25-Feb-21 8:51 
GeneralRe: How to reset TextBoxes at once? Pin
Gerry Schmitz25-Feb-21 9:17
mveGerry Schmitz25-Feb-21 9:17 
AnswerRe: How to reset TextBoxes at once? Pin
OriginalGriff25-Feb-21 8:50
mveOriginalGriff25-Feb-21 8:50 
GeneralRe: How to reset TextBoxes at once? Pin
Alex Dunlop25-Feb-21 19:10
MemberAlex Dunlop25-Feb-21 19:10 
GeneralRe: How to reset TextBoxes at once? Pin
Dave Kreskowiak25-Feb-21 19:44
mveDave Kreskowiak25-Feb-21 19:44 
GeneralRe: How to reset TextBoxes at once? Pin
OriginalGriff25-Feb-21 19:59
mveOriginalGriff25-Feb-21 19:59 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.