Matrix problem

[nick30266]

can somebody help me with this program??
i have to program a matrix with n column and n row and it should be able to find a path moving like a horse in chess game(L) that touch every point of the matrix once. the program consist in enter the location where i want to start (n,n) n=1,2,3,4,5 and the computer will calculate the path...
ex: starting from (1,1) we have:
1 6 15 10 21
14 9 20 5 16
19 2 7 22 11
8 13 24 17 4
25 18 3 12 23
you can see that the sequence of the numbers is in L. i need at least a start head

[thines01]

I like this one a lot.
Here is step 1:

namespace MatrixProblem
{
   class CMatrixProblem
   {
      static void Main(string[] args)
      {
         int[,] arr_arr_int = new int[5,5]
         {
            { 1, 6,15,10,21},
            {14, 9,20, 5,16},
            {19, 2, 7,22,11},
            { 8,13,24,17, 4},
            {25,18, 3,12,23}
         };
      }
   }
}

[Geekitygeek]

can somebody help me with this program??
i have to program a matrix with n column and n row and it should be able to find a path moving like a horse in chess game(L) that touch every point of the matrix once. the program consist in enter the location where i want to start (n,n) n=1,2,3,4,5 and the computer will calculate the path...
ex: starting from (1,1) we have:
1 6 15 10 21
14 9 20 5 16
19 2 7 22 11
8 13 24 17 4
25 18 3 12 23
you can see that the sequence of the numbers is in L. i need at least a start head

I think i can kinda see what your saying, but i'm curious...from the matrix given here the L shape can be turned and mirrored...what determines the direction it moves or is that what you need help figuring out?

And what's the minimum dimensions for the matrix? If you had a 3x3 or smaller matrix i'm not sure what the expected behaviour would be since there isnt space to move two squares in any direction :/

[thines01]

If the concept is to simply make the move of the "Knight" (horse), then maybe we could study the pattern the implied solution could take through that matrix and see if a formula emerges.

If we look at the pattern in doRawCoordDump(), does it speak of a formula for X and Y?

We know we can limit (or modulus) the edges by 5 or by 25 depending on how you do it.

Here's some more testing:

using System;
using System.Collections.Generic;
using System.Text;

namespace MatrixProblem
{
   class CMatrixProblem
   {
#if DEBUG
      private static void doRawCoordDump(int[,] arr_arr_int)
      {
         Console.WriteLine(arr_arr_int[0, 0]);// 1
         Console.WriteLine(arr_arr_int[2, 1]);// 2
         Console.WriteLine(arr_arr_int[4, 2]);// 3
         Console.WriteLine(arr_arr_int[3, 4]);// 4
         Console.WriteLine(arr_arr_int[1, 3]);// 5
         //
         Console.WriteLine(arr_arr_int[0, 1]);// 6
         Console.WriteLine(arr_arr_int[2, 2]);// 7
         Console.WriteLine(arr_arr_int[3, 0]);// 8
         Console.WriteLine(arr_arr_int[1, 1]);// 9
         Console.WriteLine(arr_arr_int[0, 3]);//10
         //
         Console.WriteLine(arr_arr_int[2, 4]);//11
         Console.WriteLine(arr_arr_int[4, 3]);//12
         Console.WriteLine(arr_arr_int[3, 1]);//13
         Console.WriteLine(arr_arr_int[1, 0]);//14
         Console.WriteLine(arr_arr_int[0, 2]);//15
         //
         Console.WriteLine(arr_arr_int[1, 4]);//16
         Console.WriteLine(arr_arr_int[3, 3]);//17
         Console.WriteLine(arr_arr_int[4, 1]);//18
         Console.WriteLine(arr_arr_int[2, 0]);//19
         Console.WriteLine(arr_arr_int[1, 2]);//20
         //
         Console.WriteLine(arr_arr_int[0, 4]);//21
         Console.WriteLine(arr_arr_int[2, 3]);//22
         Console.WriteLine(arr_arr_int[4, 4]);//23
         Console.WriteLine(arr_arr_int[3, 2]);//24
         Console.WriteLine(arr_arr_int[4, 0]);//25
      }
#endif
      static void Main(string[] args)
      {
         int[,] arr_arr_int = new int[5,5]
         {
            { 1, 6,15,10,21},
            {14, 9,20, 5,16},
            {19, 2, 7,22,11},
            { 8,13,24,17, 4},
            {25,18, 3,12,23}
         };

#if DEBUG
         doRawCoordDump(arr_arr_int);
#endif
      }
   }
}

[Geekitygeek]

A little bit of googling resulted in this:

"Warnsdorff's algorithm is a heuristic method for solving the knight's tour, based on the rule of choosing the square among those immediately accessible by the knight move that would give the fewest possible knight's moves following the move to that square. In graph-theoretic terms, each move is made to the adjacent vertex with the least degree. (Pohl has devised a rule for breaking ties.) This algorithm may also more generally be applied to any graph. Although the Hamiltonian path problem is NP-hard in general, on many graphs that occur in practice this heuristic is able to successfully locate a solution in linear time. The knight's tour is a special case.

The algorithm was first described in "Des Rösselsprungs einfachste und allgemeinste Lösung" by H. C. Warnsdorff in 1823.

Algorithm
Warnsdorff’s algorithm will do for any initial position of the knight on the board. All the possible squares which may be reached in one move from this position are located, and the number of moves that the knight would be able to make from each of these squares is found. Then, the algorithm dictates that the knight move to the square that has the least number of possible following moves. The process is then repeated until each square has been visited.

Some definitions:

A position Q is accessible from a position P if P can move to Q by a single knight's move, and Q has not yet been visited.
The accessibility of a position P is the number of positions accessible from P.

Algorithm:

-set P to be a random initial position on the board
-mark the board at P with the move number "1"
-for each move number from 2 to the number of squares on the board:
-let S be the set of positions accessible from the input position
-set P to be the position in S with minimum accessibility
-mark the board at P with the current move number
return the marked board – each square will be marked with the move number on which it is visited."

courtesy of wikipedia

As is the policy here at Daniweb, we will gladly help you once you have had a go for yourself. So have a go at converting the algorythm into C#. If you have any problems, then post a specific thread and we'll help you there :)
Good luck.

[thines01]

By the way, here is an online implementation of "Kight's Tour" :
http://www.knightstour.co.uk/
...with multiple sized grids.

Here's more than you ever wanted to know about it:
http://en.wikipedia.org/wiki/Knight's_tour