Need help with valid knight moves in Chess Last weekend I was writing a short PHP function that accepts a starting move and returns valid knight squares for that move.

&lt;?php

/* get's starting move and returns valid knight moves */

echo GetValidKnightSquares('e4');

function GetValidKnightSquares($strStartingMove) {

  $cb_rows = array('a' =&gt; 1, 'b' =&gt; 2, 'c' =&gt; 3, 'd' =&gt; 4, 'e' =&gt; 5, 'f' =&gt; 6, 'g' =&gt; 7, 'h' =&gt; 8);
  $valids  = array(array(-1, -2), array(-2, -1), array(-2, 1), array(-1, 2), array(1, 2), array(2, 1), array(2, -1), array(1, -2));

  $row = substr($strStartingMove, 0, 1);
  $col = substr($strStartingMove, 1, 1);

  $current_row = $cb_rows[$row];
  if(!in_array($current_row, $cb_rows)) {
    die("Hey, use chars from a to h only!");
  }

  $current_col = $col;
  if($current_col &gt; 8) {
    die("Hey, use numbers from 1 to 8 only!");
  }

  $valid_moves = '';

  foreach ($valids as $valid) {
    $new_valid_row = $current_row + $valid[0];
    $new_valid_col = $current_col + $valid[1];

    if(($new_valid_row &lt;= 8 &amp;&amp; $new_valid_row &gt; 0) &amp;&amp; ($new_valid_col &lt;= 8 &amp;&amp; $new_valid_col &gt; 0)) {
      $row_char = array_search($new_valid_row, $cb_rows);
      $valid_moves .= $row_char . "$new_valid_col ";
    }
  }

  return "Valid knight moves for knight on $strStartingMove are: $valid_moves";
} 

?&gt;


Could you please take a look at it and share your thoughts about it?  The code can also be found here.



I was kinda 'criticized' about the code. One guy said it's messy, too long and not 'clever' enough. So I needed second opinion on it, a code review if you like. I think there is a place for improvement (always), but for me this was the first time I've coded something related with Chess. I've found something like this that caught my attention:

if ((abs(newX-currentX)==1 and abs(newY-currentY)==2) or (abs(newX-currentX)==2 and abs(newY-currentY)==1)) {
  /* VALID MOVE FOR A KNIGHT */
}
else {
  /* INVALID MOVE FOR A KNIGHT */
}
First of all, a function called GetValidKnightSquares shouldn't be translating chessboard locations. Any code that performs a distinct operation and can be named should be extracted into its own function. It makes everything much easier to read and understand. Name things.

Second, I would probably leverage whatever data structure you choose for your board to determine the valid moves on that board. The structure I'm going to choose looks like this:

-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 
-1, "8a", "8b", "8c", "8d", "8e", "8f", "8g", "8h", -1, 
-1, "7a", "7b", "7c", "7d", "7e", "7f", "7g", "7h", -1, 
-1, "6a", "6b", "6c", "6d", "6e", "6f", "6g", "6h", -1, 
-1, "5a", "5b", "5c", "5d", "5e", "5f", "5g", "5h", -1, 
-1, "4a", "4b", "4c", "4d", "4e", "4f", "4g", "4h", -1, 
-1, "3a", "3b", "3c", "3d", "3e", "3f", "3g", "3h", -1, 
-1, "2a", "2b", "2c", "2d", "2e", "2f", "2g", "2h", -1, 
-1, "1a", "1b", "1c", "1d", "1e", "1f", "1g", "1h", -1, 
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1


It's a one-dimensional array that represents the ranks and files of the  two-dimensional board. The negative ones are there to pad the board and make it easier to detect when a piece has moved out of play. (We'll see this later.) This type of data structure is called a Mailbox (because some old-timer thought it looked like one, I guess) and it's very common in chess programming.

Here's how to generate it:

// converts an index in the mailbox into its corresponding value in algebraic notation
function i2an($i) {
    $files = "abcdefgh";
    return 10 - floor($i / 10) . $files[($i % 10) - 1];
}

function generateEmptyBoard() {
    $row = array();
    for($i = 0; $i &lt; 120; $i++) {
        $row[] = ($i &lt; 20 || $i &gt; 100 || !($i % 10) || $i % 10 == 9)
            ? -1
            : i2an($i);
    }
    return $row;
}


This gives us the array we saw above. All that's left is to use it:

function knightMoves($square, $board) {
    $i = an2i($square);
    $moves = array();
    foreach(array(8, -8, 12, -12, 19, -19, 21, -21) as $offset) {
        $move = $board[$i + $offset];
        if ($move != -1) {
            $moves[] = $move;
        }
    }
    return $moves;
}

// converts a position in algebraic notation into its location in the mailbox
function an2i($square) {
    return (10 - $square[0]) * 10 + strpos("abcdefgh", $square[1]) + 1;
}


Notice that the mailbox's borders make it very easy to tell when we've moved to a position off the board. 

Here are some examples:

$board = generateEmptyBoard();
print_r(knightMoves("1h", $board));
print_r(knightMoves("5b", $board));
print_r(knightMoves("6c", $board));


Output:

$ php knights.php
Array
(
    [0] =&gt; 2f
    [1] =&gt; 3g
)
Array
(
    [0] =&gt; 6d
    [1] =&gt; 4d
    [2] =&gt; 3a
    [3] =&gt; 7c
    [4] =&gt; 3c
    [5] =&gt; 7a
)
Array
(
    [0] =&gt; 5a
    [1] =&gt; 7e
    [2] =&gt; 5e
    [3] =&gt; 7a
    [4] =&gt; 4b
    [5] =&gt; 8d
    [6] =&gt; 4d
    [7] =&gt; 8b
)


What's cool is that you can use this mailbox throughout your entire application by substituting some representation of actual pieces for the location names in the inner elements. It's useful for more than just your narrow problem, in other words.