Problem
I’m creating a console application that takes as input starting column and starting row, also the ending column and the ending row and it’s going to output all the possible way’s to get to that point and also highlight the best turn/s.
It’s all working, however, I’m not satisfied with the time it takes to calculate it. Since the Knight can make a total of 8 different turns that makes all possible turns 88 which is 16.7 million variations. It’s a lot but it really takes a lot of time, 25-30 secs or so. On a slower machine it will probably take even longer.
internal class Program
{
private const int size = 8;
private static readonly int[,] duska = new int[size, size];
private static readonly string[] redoveBukvi = {"A", "B", "C", "D", "E", "F", "G", "H"};
private static List<List<int>> minMinatRed = new List<List<int>>();
private static List<List<int>> minMinataKolona = new List<List<int>>();
private static int minCount = int.MaxValue;
private static int count;
private static int nachalenRed;
private static int nachalnaKolona;
private static int kraenRed;
private static int krainaKolona;
private static readonly int[] tempArr = {0, 1, 2, 3, 4, 5, 6, 7, 8};
private static readonly double numberOfVariations = Math.Pow(size, size);
private static readonly int[] result = new int[size];
private static void Main()
{
nachalenRed = VuvejdaneNaRed("nachalen");
nachalnaKolona = VuvejdaneNaKolona("nachalna");
kraenRed = VuvejdaneNaRed("kraen");
krainaKolona = VuvejdaneNaKolona("kraina");
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
duska[i, j] = j + 1;
}
}
Dvijenie(nachalenRed,nachalnaKolona);
if (minCount == int.MaxValue)
{
Console.ForegroundColor = ConsoleColor.Red;
Console.WriteLine("Nevuzmojen hod !");
}
else
{
Izvejdane();
}
Console.ReadKey();
}
private static void Dvijenie(int red, int kolona)
{
var comparer = new ListComparer<int>();
var tempHodove = new List<Tuple<bool, int[]>>();
int novMinatRed = red;
int novaMinataKolona = kolona;
for (int i = 0; i < numberOfVariations; i++)
{
var minatRed = new List<int>();
var minataKolona = new List<int>();
minatRed.Add(nachalenRed);
minataKolona.Add(nachalnaKolona);
tempHodove.Clear();
var hodove = UpdateList(novMinatRed, novaMinataKolona,minatRed,minataKolona);
int x = i;
for (int j = 0; j < size; j++)
{
result[j] = tempArr[x % size];
x /= size;
}
for (int k = result.Length - 1; k >= 0; k--)
{
tempHodove.Add(hodove[result[k]]);
}
bool trueValue = tempHodove.Any(c => c.Item1);
while (trueValue)
{
foreach (var hod in tempHodove.Where(hod => hod.Item1))
{
novMinatRed += hod.Item2[0];
novaMinataKolona += hod.Item2[1];
minatRed.Add(novMinatRed);
minataKolona.Add(novaMinataKolona);
count++;
break;
}
if (novMinatRed == kraenRed && novaMinataKolona == krainaKolona)
{
if (minCount > count)
{
minCount = count;
}
minMinatRed.Add(minatRed);
minMinataKolona.Add(minataKolona);
minMinatRed = minMinatRed.Distinct(comparer).ToList();
minMinataKolona = minMinataKolona.Distinct(comparer).ToList();
}
hodove = UpdateList(novMinatRed, novaMinataKolona,minatRed,minataKolona);
tempHodove.Clear();
for (int k = result.Length - 1; k >= 0; k--)
{
tempHodove.Add(hodove[result[k]]);
}
trueValue = tempHodove.Any(c => c.Item1);
}
count = 0;
novMinatRed = nachalenRed;
novaMinataKolona = nachalnaKolona;
}
}
private static List<Tuple<bool, int[]>> UpdateList(int red, int kolona, ICollection<int> minatiRedove,
ICollection<int> minatiKoloni)
{
var vsichkiHodove = new List<Tuple<bool, int[]>>()
{
new Tuple<bool, int[]>(Nadqsno(red, 1, minatiRedove) && Napred(kolona, 2, minatiKoloni), new[]
{
+1,
+2
}),
new Tuple<bool, int[]>(Nadqsno(red, 2, minatiRedove) && Napred(kolona, 1, minatiKoloni), new[]
{
+2,
+1
}),
new Tuple<bool, int[]>(Nalqvo(red, 1, minatiRedove) && Napred(kolona, 2, minatiKoloni), new[]
{
-1,
+2
}),
new Tuple<bool, int[]>(Nalqvo(red, 2, minatiRedove) && Napred(kolona, 1, minatiKoloni), new[]
{
-2,
+1
}),
new Tuple<bool, int[]>(Nadqsno(red, 2, minatiRedove) && Nazad(kolona, 1, minatiKoloni), new[]
{
+2,
-1
}),
new Tuple<bool, int[]>(Nalqvo(red, 2, minatiRedove) && Nazad(kolona, 1, minatiKoloni), new[]
{
-2,
-1
}),
new Tuple<bool, int[]>(Nadqsno(red, 1, minatiRedove) && Nazad(kolona, 2, minatiKoloni), new[]
{
+1,
-2
}),
new Tuple<bool, int[]>(Nalqvo(red, 1, minatiRedove) && Nazad(kolona, 2, minatiKoloni), new[]
{
-1,
-2
})
};
return vsichkiHodove;
}
private static bool Napred(int segashnaKolona,int broiHodove, ICollection<int> minatiKoloni)
{
if (segashnaKolona + broiHodove >= size) return false;
bool a = ValidnaKolona(segashnaKolona + broiHodove, minatiKoloni);
return a;
}
private static bool Nazad(int segashnaKolona, int broiHodove, ICollection<int> minatiKoloni)
{
if (segashnaKolona - broiHodove <= 0) return false;
bool a = ValidnaKolona(segashnaKolona - broiHodove, minatiKoloni);
return a;
}
private static bool Nalqvo(int segashenRed, int broiHodove, ICollection<int> minatiRedove)
{
if (segashenRed - broiHodove < 0) return false;
bool a = ValidenRed(segashenRed - broiHodove, minatiRedove);
return a;
}
private static bool Nadqsno(int segashenRed, int broiHodove, ICollection<int> minatiRedove)
{
if (segashenRed + broiHodove >= size) return false;
bool a = ValidenRed(segashenRed + broiHodove, minatiRedove);
return a;
}
private static bool ValidenRed(int novRed, ICollection<int> minatiRedove)
{
if (minatiRedove.Count <= 1) return true;
bool a = !minatiRedove.Contains(novRed);
return a;
}
private static bool ValidnaKolona(int novaKolona, ICollection<int> minatiKoloni)
{
if (minatiKoloni.Count <= 1) return true;
bool a = !minatiKoloni.Contains(novaKolona);
return a;
}
private static int VuvejdaneNaRed(string text)
{
Console.Write("Vuvedi {0} red (A-H) : ",text);
string red = Console.ReadLine();
while (!redoveBukvi.ToList().Contains(red?.ToUpper()))
{
Console.WriteLine("Nevaliden red");
red = Console.ReadLine();
}
return Array.FindIndex(redoveBukvi, item => item == red?.ToUpper()) ;
}
private static int VuvejdaneNaKolona(string text)
{
int ret;
Console.Write("Vuvedi {0} kolona (1-8) : ",text);
while (!int.TryParse(Console.ReadLine(), out ret) || ret > size || ret < 1)
{
Console.WriteLine("Nevalidna Kolona");
}
return ret - 1;
}
private static void Izvejdane()
{
Console.WriteLine("Nachalna Poziciq : {0},{1}", redoveBukvi[nachalenRed], nachalnaKolona + 1);
var naiDobriRedove = new List<List<int>>();
var naiDobriKoloni = new List<List<int>>();
var skipRedove = new List<int>();
if (minMinatRed.Count > 1)
{
for (int i = 0; i < minMinatRed.Count; i++)
{
var uspeshenHod = minMinatRed[i];
if (uspeshenHod.Count - 1 != minCount) continue;
naiDobriRedove.Add(uspeshenHod);
skipRedove.Add(i);
}
}
if (minMinataKolona.Count > 1)
{
naiDobriKoloni.AddRange(minMinataKolona.Where(uspeshenHod => uspeshenHod.Count - 1 == minCount));
}
for (int i = 0; i < minMinatRed.Count; i++)
{
Console.ForegroundColor = ConsoleColor.Red;
if (skipRedove.Contains(i)) continue;
Console.WriteLine("Variant {0} : {1} hoda", i + 1, minMinatRed[i].Count - 1);
var tempRedove = minMinatRed[i];
var tempKoloni = minMinataKolona[i];
for (int j = 1; j < tempRedove.Count; j++)
{
Console.WriteLine("Hod {0} : {1},{2}", j, redoveBukvi[tempRedove[j]], tempKoloni[j] + 1);
}
Console.WriteLine();
}
Console.WriteLine();
Console.ForegroundColor = ConsoleColor.Green;
Console.WriteLine(naiDobriRedove.Count > 1 ? "Nai dobri hodove : {0}" : "Nai dobur hod : {0}", minCount);
for (int i = 0; i < naiDobriRedove.Count; i++)
{
Console.WriteLine("Variant {0} : {1} hoda", i + 1, minCount);
var tempRedove = naiDobriRedove[i];
var tempKoloni = naiDobriKoloni[i];
for (int j = 1; j < tempRedove.Count; j++)
{
Console.WriteLine("Hod {0} : {1},{2}", j, redoveBukvi[tempRedove[j]], tempKoloni[j] + 1);
}
Console.WriteLine();
}
}
}
internal class ListComparer<T> : EqualityComparer<List<T>>
{
public override bool Equals(List<T> l1, List<T> l2)
{
if (l1 == null && l2 == null) return true;
if (l1 == null || l2 == null) return false;
return l1.SequenceEqual(l2);
}
public override int GetHashCode(List<T> list)
{
return list.Count;
}
}
The Knight must NOT repeat a column or a row. The methods ValidenRed and ValidnaKolona are checking if the Knight has already been on that spot.
I’m looking for performance improvement in the Dvijenie method because all the combination switching is happening there.
Solution
Your outer loop is forcing the program to go through 16.7 Million iterations of the loop, it’s not clear how many times the inner loops execute. This type of programming is sometimes known as a BRUTE FORCE algorithm. The website that @RubberDuck pointed to clearly states that Brute Force solutions don’t work well for this problem. The 8 power 8 is not the correct number to use in the outer loop, because you can’t return to a previous point (after each move you only have 7 possible moves, not 8).
As a test of performance I suggest you create this very small program and time it, this will give you a baseline for the most you can optimize your current solution.
Main()
{
int a = 0;
int b = 1;
for (i = 0; i < Math.Pow(8, 8); i++) {
a = b;
}
}
Your outer loop can be as few as 8 iterations if you change your algorithm. 8 moves is the maximum number of moves that the knight can make from a starting point.
Basics Facts:
The Knight can make 8 possible moves in the center of the board. The knight can make 4 possible moves on any edge of the board. The knight can make 2 moves if it is in a corner of the board. From any given location there are as many as 8 moves and as few as 2 moves. This provides you with a filter. Lets call this filter1.
Stated in logic terms filter1 is
Foreach move from this location is the new location on the board?
If you apply filter1 at the start you have a maximum of 8 moves and a minimum of 2 moves that you can make, reducing the number of executions of the outer loop.
With the limitation that a knight can visit a row or a column only once, using a standard 8X8 chessboard, with each move this goes down by 1 row and 1 column so the maximum number of moves from the starting point is limited to 8. This is also a filter. Let’s call this filter2.
Stated in logic terms filter2 is
Foreach move from this location is the new location in a row that has been visited before.
Foreach move from this location is the new location in a column that has been visited before.
These 2 filters provide a large reduction in the number of possibilities. These 2 filters can be applied in any order.
The use of these 2 filters implies that this problem can be solved with a tree search (sometimes called a decision tree). A breadth first tree search trims broken branches from the tree at each step before doing a deeper tree search. A depth first tree search follows one path all the way to the bottom first, and then backs up and tries another branch. Tree searches are often implemented using recursion. I find it very difficult to come up with an iterative (looping) solution for this problem. In this case a branch is broken when the Knight does not arrive at the destination and the Knight can’t make any more moves.
A recursive function is a function that calls itself until certain conditions are met. In the case of this particular search, there are 2 halting conditions.
1) Have we arrived at the destination yet? If so, stop searching this branch.
2) Are there any moves that can be made from this location? If so try them, if not, stop searching this branch.
Recursive searches allow the program to back up to a known good location and try another path from that point. When you use recursion you are using the computers stack to store the current state of your program, one possible alternative to using recursion is to store each of you moves in a stack data structure. Once your loop encounters one of the halting conditions you pop the current move off the stack and try another move.
You should check out this link for more information on recursion and this link
The problem you described is to output all the possible paths that a Knight can use to get from the point origin to the destination on a chessboard given the restriction that the Knight can only visit a row or column once. One way to solve this is to move the Knight to one of the possible squares, make sure that the limiting conditions apply, record the location, record the row, record the column and then repeat this process until you either arrive at the destination or you can’t move anymore. At each location you must repeat this full process.
Using a tree search, some branches will be broken after the first move; some branches will be broken after the second move.
Possible Problem:
Due to the break; statement at the end the following loop executes only once per while (trueValue) is this what you wanted?
foreach (var hod in tempHodove.Where(hod => hod.Item1))
{
novMinatRed += hod.Item2[0];
novaMinataKolona += hod.Item2[1];
minatRed.Add(novMinatRed);
minataKolona.Add(novaMinataKolona);
count++;
break;
}