473,287 Members | 3,295 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,287 software developers and data experts.

Knight's tour, recursion, dynamic programming, optimization

5 Nibble
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.

Expand|Select|Wrap|Line Numbers
  1. using System;
  2.  
  3. namespace KnightChess
  4. {
  5.     class Field
  6.     {
  7.         public int index { get; set; }
  8.         public Field(int _index)
  9.         {
  10.             index = _index;
  11.         }
  12.     }
  13.     class Board
  14.     {
  15.         int height;
  16.         int width;
  17.         public (int, int) curKnightPos;
  18.         int value;
  19.         public Field[,] boardArr;
  20.         public static bool CanMoveKnight1(Board Board)
  21.         {
  22.             return (Board.width > Board.curKnightPos.Item1 + 1) && (Board.height > Board.curKnightPos.Item2) &&
  23.                     (Board.boardArr[Board.curKnightPos.Item1 + 1, Board.curKnightPos.Item2].index == -1);
  24.         }
  25.         public static Board MoveKnight1(Board Board)
  26.         {
  27.             Board Transformed = new Board(Board);
  28.             Transformed.curKnightPos.Item1 += 2;
  29.             Transformed.curKnightPos.Item2++;
  30.             Transformed.boardArr[Transformed.curKnightPos.Item1 - 1, Transformed.curKnightPos.Item2 - 1].index = ++Transformed.value;
  31.  
  32.             return Transformed;
  33.         }
  34.         public static bool CanMoveKnight2(Board Board)
  35.         {
  36.             return (Board.width > Board.curKnightPos.Item1) && (Board.height > Board.curKnightPos.Item2 + 1) &&
  37.                     (Board.boardArr[Board.curKnightPos.Item1, Board.curKnightPos.Item2 + 1].index == -1);
  38.         }
  39.         public static Board MoveKnight2(Board Board)
  40.         {
  41.             Board Transformed = new Board(Board);
  42.             Transformed.curKnightPos.Item1++;
  43.             Transformed.curKnightPos.Item2 += 2;
  44.             Transformed.boardArr[Transformed.curKnightPos.Item1 - 1, Transformed.curKnightPos.Item2 - 1].index = ++Transformed.value;
  45.  
  46.             return Transformed;
  47.         }
  48.         public static bool CanMoveKnight3(Board Board)
  49.         {
  50.             return (Board.curKnightPos.Item1 > 1) && (Board.height > Board.curKnightPos.Item2 + 1) &&
  51.                     (Board.boardArr[Board.curKnightPos.Item1 - 2, Board.curKnightPos.Item2 + 1].index == -1);
  52.         }
  53.         public static Board MoveKnight3(Board Board)
  54.         {
  55.             Board Transformed = new Board(Board);
  56.             Transformed.curKnightPos.Item1--;
  57.             Transformed.curKnightPos.Item2 += 2;
  58.             Transformed.boardArr[Transformed.curKnightPos.Item1 - 1, Transformed.curKnightPos.Item2 - 1].index = ++Transformed.value;
  59.  
  60.             return Transformed;
  61.         }
  62.         public static bool CanMoveKnight4(Board Board)
  63.         {
  64.             return (Board.curKnightPos.Item1 > 2) && (Board.height > Board.curKnightPos.Item2) &&
  65.                     (Board.boardArr[Board.curKnightPos.Item1 - 3, Board.curKnightPos.Item2].index == -1);
  66.         }
  67.         public static Board MoveKnight4(Board Board)
  68.         {
  69.             Board Transformed = new Board(Board);
  70.             Transformed.curKnightPos.Item1 -= 2;
  71.             Transformed.curKnightPos.Item2++;
  72.             Transformed.boardArr[Transformed.curKnightPos.Item1 - 1, Transformed.curKnightPos.Item2 - 1].index = ++Transformed.value;
  73.  
  74.             return Transformed;
  75.         }
  76.         public static bool CanMoveKnight5(Board Board)
  77.         {
  78.             return (Board.curKnightPos.Item1 > 2) && (Board.curKnightPos.Item2 > 1) &&
  79.                     (Board.boardArr[Board.curKnightPos.Item1 - 3, Board.curKnightPos.Item2 - 2].index == -1);
  80.         }
  81.         public static Board MoveKnight5(Board Board)
  82.         {
  83.             Board Transformed = new Board(Board);
  84.             Transformed.curKnightPos.Item1 -= 2;
  85.             Transformed.curKnightPos.Item2--;
  86.             Transformed.boardArr[Transformed.curKnightPos.Item1 - 1, Transformed.curKnightPos.Item2 - 1].index = ++Transformed.value;
  87.  
  88.             return Transformed;
  89.         }
  90.         public static bool CanMoveKnight6(Board Board)
  91.         {
  92.             return (Board.curKnightPos.Item1 > 1) && (Board.curKnightPos.Item2 > 2) &&
  93.                     (Board.boardArr[Board.curKnightPos.Item1 - 2, Board.curKnightPos.Item2 - 3].index == -1);
  94.         }
  95.         public static Board MoveKnight6(Board Board)
  96.         {
  97.             Board Transformed = new Board(Board);
  98.             Transformed.curKnightPos.Item1--;
  99.             Transformed.curKnightPos.Item2 -= 2;
  100.             Transformed.boardArr[Transformed.curKnightPos.Item1 - 1, Transformed.curKnightPos.Item2 - 1].index = ++Transformed.value;
  101.  
  102.             return Transformed;
  103.         }
  104.         public static bool CanMoveKnight7(Board Board)
  105.         {
  106.             return (Board.width > Board.curKnightPos.Item1) && (Board.curKnightPos.Item2 > 2) &&
  107.                     (Board.boardArr[Board.curKnightPos.Item1, Board.curKnightPos.Item2 - 3].index == -1);
  108.         }
  109.         public static Board MoveKnight7(Board Board)
  110.         {
  111.             Board Transformed = new Board(Board);
  112.             Transformed.curKnightPos.Item1++;
  113.             Transformed.curKnightPos.Item2 -= 2;
  114.             Transformed.boardArr[Transformed.curKnightPos.Item1 - 1, Transformed.curKnightPos.Item2 - 1].index = ++Transformed.value;
  115.  
  116.             return Transformed;
  117.         }
  118.         public static bool CanMoveKnight8(Board Board)
  119.         {
  120.             return (Board.width > Board.curKnightPos.Item1 + 1) && (Board.curKnightPos.Item2 > 1) &&
  121.                     (Board.boardArr[Board.curKnightPos.Item1 + 1, Board.curKnightPos.Item2 - 2].index == -1);
  122.         }
  123.         public static Board MoveKnight8(Board Board)
  124.         {
  125.             Board Transformed = new Board(Board);
  126.             Transformed.curKnightPos.Item1 += 2;
  127.             Transformed.curKnightPos.Item2--;
  128.             Transformed.boardArr[Transformed.curKnightPos.Item1 - 1, Transformed.curKnightPos.Item2 - 1].index = ++Transformed.value;
  129.  
  130.             return Transformed;
  131.         }
  132.         public static void Print(Board Board)
  133.         {
  134.             for (int i = Board.width - 1; i >= 0; i--)
  135.             {
  136.                 for (int j = 0; j < Board.height; j++)
  137.                 {
  138.                     Console.Write(Board.boardArr[i, j].index + " ");
  139.                 }
  140.                 Console.WriteLine();
  141.             }
  142.             Console.WriteLine();
  143.         }
  144.         public static bool isFull(Board Board)
  145.         {
  146.             foreach(var el in Board.boardArr)
  147.             {
  148.                 if (el.index == -1)
  149.                 {
  150.                     return false;
  151.                 }
  152.             }
  153.  
  154.             return true;
  155.         }
  156.  
  157.         public Board(Board Board)
  158.         {
  159.             height = Board.height;
  160.             width = Board.width;
  161.             curKnightPos = Board.curKnightPos;
  162.             value = Board.value;
  163.             boardArr = new Field[width, height];
  164.             for (int i = 0; i < width; i++)
  165.             {
  166.                 for (int j = 0; j < height; j++)
  167.                 {
  168.                     boardArr[i, j] = new Field(Board.boardArr[i, j].index);
  169.                 }
  170.             }
  171.         }
  172.         public Board(int _height, int _width, (int, int) _curKnightPos)
  173.         {
  174.             height = _height;
  175.             width = _width;
  176.             curKnightPos = _curKnightPos;
  177.             value = 1;
  178.             boardArr = new Field[_width, _height];
  179.             for(int i = 0; i < _width; i++)
  180.             {
  181.                 for (int j = 0; j < _height; j++)
  182.                 {
  183.                     boardArr[i, j] = new Field(-1);
  184.                 }
  185.             }
  186.             boardArr[_curKnightPos.Item1 - 1, _curKnightPos.Item2 - 1].index = 1;
  187.         }
  188.     }
  189.     class Program
  190.     {
  191.         static void Main(string[] args)
  192.         {
  193.             #region input and define
  194.             Console.WriteLine("Please enter board's width");
  195.             string temp;
  196.             temp = Console.ReadLine();
  197.             int width;
  198.             bool success;
  199.             success = int.TryParse(temp, out width);
  200.             if (!success)
  201.             {
  202.                 Console.WriteLine("Width be natural a number");
  203.                 return;
  204.             }
  205.  
  206.             Console.WriteLine("Please enter board's height");
  207.             temp = Console.ReadLine();
  208.             int height;
  209.             success = int.TryParse(temp, out height);
  210.             if (!success)
  211.             {
  212.                 Console.WriteLine("Height be natural a number");
  213.                 return;
  214.             }
  215.  
  216.             Console.WriteLine("Please enter board's curKnightPosX");
  217.             temp = Console.ReadLine();
  218.             int curKnightPosX;
  219.             success = int.TryParse(temp, out curKnightPosX);
  220.             if (!success)
  221.             {
  222.                 Console.WriteLine("CurKnightPosX be natural a number");
  223.                 return;
  224.             }
  225.  
  226.             Console.WriteLine("Please enter board's curKnightPosY");
  227.             temp = Console.ReadLine();
  228.             int curKnightPosY;
  229.             success = int.TryParse(temp, out curKnightPosY);
  230.             if (!success)
  231.             {
  232.                 Console.WriteLine("CurKnightPosY be natural a number");
  233.                 return;
  234.             }
  235.  
  236.             if ((curKnightPosX > width) || (curKnightPosY > height))
  237.             {
  238.                 Console.WriteLine("curKnightPos out of range");
  239.                 return;
  240.             }
  241.  
  242.             Board Board = new Board(height, width, (curKnightPosX, curKnightPosY));
  243.             #endregion
  244.  
  245.             GetTransformsMap(Board);
  246.  
  247.             Console.ReadKey();
  248.         }
  249.         private static void GetTransformsMap(Board board)
  250.         {
  251.             if (!Board.CanMoveKnight1(board) && !Board.CanMoveKnight2(board) && !Board.CanMoveKnight3(board) && !Board.CanMoveKnight4(board) &&
  252.                 !Board.CanMoveKnight5(board) && !Board.CanMoveKnight6(board) && !Board.CanMoveKnight7(board) && !Board.CanMoveKnight8(board))
  253.             {
  254.                 if (Board.isFull(board))
  255.                 {
  256.                     Board.Print(board);
  257.                 }
  258.             }
  259.  
  260.             if (Board.CanMoveKnight1(board))
  261.             {
  262.                 GetTransformsMap(Board.MoveKnight1(board));
  263.             }
  264.             if (Board.CanMoveKnight2(board))
  265.             {
  266.                 GetTransformsMap(Board.MoveKnight2(board));
  267.             }
  268.             if (Board.CanMoveKnight3(board))
  269.             {
  270.                 GetTransformsMap(Board.MoveKnight3(board));
  271.             }
  272.             if (Board.CanMoveKnight4(board))
  273.             {
  274.                 GetTransformsMap(Board.MoveKnight4(board));
  275.             }
  276.             if (Board.CanMoveKnight5(board))
  277.             {
  278.                 GetTransformsMap(Board.MoveKnight5(board));
  279.             }
  280.             if (Board.CanMoveKnight6(board))
  281.             {
  282.                 GetTransformsMap(Board.MoveKnight6(board));
  283.             }
  284.             if (Board.CanMoveKnight7(board))
  285.             {
  286.                 GetTransformsMap(Board.MoveKnight7(board));
  287.             }
  288.             if (Board.CanMoveKnight8(board))
  289.             {
  290.                 GetTransformsMap(Board.MoveKnight8(board));
  291.             }
  292.         }
  293.     }
  294. }
  295.  
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?
Mar 1 '21 #1
9 2688
Banfa
9,065 Expert Mod 8TB
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.
Mar 2 '21 #2
Tricui11
5 Nibble
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...
Mar 2 '21 #3
Rabbit
12,516 Expert Mod 8TB
I see the recursion in your code, but I see no dynamic programming. Where's the memoization?
Mar 3 '21 #4
Banfa
9,065 Expert Mod 8TB
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?
Mar 3 '21 #5
Tricui11
5 Nibble
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...
Mar 3 '21 #6
Tricui11
5 Nibble
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...)
Mar 3 '21 #7
Rabbit
12,516 Expert Mod 8TB
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.
Mar 3 '21 #8
Tricui11
5 Nibble
Rabbit, OK, task is find 1000 paths in a reasonable amount of time.
Mar 3 '21 #9
Rabbit
12,516 Expert Mod 8TB
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.
Mar 3 '21 #10

Sign in to post your reply or Sign up for a free account.

Similar topics

5
by: The Directive | last post by:
Does C++ support dynamic programming? I hope I'm using the correct term. I want to write code that can dynamically rewrite itself! I want to dynamically create functions and call them and etc. If...
10
by: paulw | last post by:
Hi Please give problems that "HAS TO" to use recursion (recursive calls to itself.) Preferrably real world examples, not knights tour. I'm thinking about eliminating the use of stack... ...
4
by: Nicky | last post by:
Hello, I have to explain my problem with an example : public class DecisionTables { public ObjectName ObjectName; // ObjectName defined in other .cs public DecisionTables() {
0
by: Pascal Costanza | last post by:
Dynamic Languages Day @ Vrije Universiteit Brussel ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Monday, February 13, 2006, VUB Campus Etterbeek The VUB (Programming Technology Lab,...
9
by: whitehatmiracle | last post by:
im stuck, thers a prob with the backtrack function. #include <iostream.h> #include <conio.h> #include <stdio.h> #include <string.h> #include <ctype.h> #include <stdlib.h> #define size 5
1
by: James A Taber | last post by:
Dear friends! I am wondering if someone can recommend a few good books about Dynamic Programming / Reflection?
4
by: Csaba Gabor | last post by:
I suppose spring fever has hit at alt.math.undergrad since I didn't get any rise from them when I posted this a week ago, so I am reposting this to some of my favorite programming groups: I'm...
1
by: atl2 | last post by:
Please do not crosspost to other forums...
10
by: slix | last post by:
Recursion is awesome for writing some functions, like searching trees etc but wow how can it be THAT much slower for computing fibonacci- numbers? is the recursive definition counting fib 1 to...
2
AmberJain
by: AmberJain | last post by:
HELLO, I studied recursion in C programming. But I still think that I'm unable to grab the concept of recursion. OR better said I cannot get recursion inside my mind from the book I'm referring...
2
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 7 Feb 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:30 (7.30PM). In this month's session, the creator of the excellent VBE...
0
by: MeoLessi9 | last post by:
I have VirtualBox installed on Windows 11 and now I would like to install Kali on a virtual machine. However, on the official website, I see two options: "Installer images" and "Virtual machines"....
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: Aftab Ahmad | last post by:
Hello Experts! I have written a code in MS Access for a cmd called "WhatsApp Message" to open WhatsApp using that very code but the problem is that it gives a popup message everytime I clicked on...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: marcoviolo | last post by:
Dear all, I would like to implement on my worksheet an vlookup dynamic , that consider a change of pivot excel via win32com, from an external excel (without open it) and save the new file into a...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.