-
February 28th, 2021, 08:35 PM
#1
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?
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|