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.
Expand|Select|Wrap|Line Numbers
- 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));
- }
- }
- }
- }
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?