Databases
StackOverflow2013
Postsdbo
POGetting the shortest path for chess pieces on n*m board
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POGetting the shortest path for chess pieces on n*m board
    primarykey
    data
    text
    <p>I am stuck solving a task requiring me to calculate the minimal number of steps required to go from point A to point B with different chess pieces on a n*m board that also has obstacles and also output the path taken.</p> <p>I was looking at the A* algorithm, but it requires me to get a good heuristic estimate which I have no idea how to get for a chess piece like a knight</p> <p>What I have been trying to do is first using Breadth-First Search to find the minimal number of steps required to get from point A to point B without obstacles and then use the A* algorithm</p> <pre><code>public void AllPaths(int[,] chessBoard, int startX, int startY, int dimension) { // All the moves a knight can make int[] movementX = new int[8]{-2, -2, -1, -1, 1, 1, 2, 2}; int[] movementY = new int[8]{-1, 1, -2, 2, -2, 2, -1, 1}; chessBoard[startX, startY] = 0; for (int step = 0; step &lt; dimension-1; step++) { for (int x = 0; x &lt; dimension; x++) { for (int j = 0; j &lt; dimension; j++) { if (chessBoard[x, j] == step) { for (int k = 0; k &lt; 8; k++) { if (movementY[k] + x&gt;= 0 &amp;&amp; movementY[k] + x &lt; dimension &amp;&amp; movementX[k] + j &gt;= 0 &amp;&amp; movementX[k]+j &lt; dimension) { if (chessBoard[movementY[k]+x,movementX[k]+j] == -1) { chessBoard[movementY[k]+x,movementX[k]+j] = step + 1; } } } } } } } } </code></pre> <p>The input and output for a knight's moves are as follows:</p> <pre><code>-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 - starting from the top left 0 3 2 3 2 3 4 5 3 4 1 2 3 4 3 4 2 1 4 3 2 3 4 5 3 2 3 2 3 4 3 4 2 3 2 3 4 3 4 5 3 4 3 4 3 4 5 4 4 3 4 3 4 5 4 5 5 4 5 4 5 4 5 6 </code></pre> <p>This works for n*n boards, but I need it to work for n*m boards as well. Am I going in the right direction or should I use something else completely? What do I have to change for it to work for n*m boards? Thanks for any suggestions you may have about solving the problem I have.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USJoonasL
    1. USJoonasL
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POGetting the shortest path for chess pieces on n*m board
      1. USPieter Müller
      1. VTFavorite
    2. VO
      singulars
      1. POGetting the shortest path for chess pieces on n*m board
      1. This table or related slice is empty.
      1. VTUpMod
    1. COYou might have more luck with this question over at http://math.stackexchange.com
      singulars
      1. POGetting the shortest path for chess pieces on n*m board
      1. USmagritte
    2. CODo you have problem in coding your algorithm or you have a problem about establishing your algorithm ? I havent calculated but does brute force approach take too much time ?
      singulars
      1. POGetting the shortest path for chess pieces on n*m board
      1. USOzgur Dogus
    3. COI got the answer for my immediate problem, but I am worried if I am doing the right thing. Is it reasonable to find the heuristic with DFS and then use A* or am I doing a lot of pointless work?
      singulars
      1. POGetting the shortest path for chess pieces on n*m board
      1. USJoonasL
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload