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.

<?php

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

echo GetValidKnightSquares('e4');

function GetValidKnightSquares($strStartingMove) {$cb_rows = array('a' => 1, 'b' => 2, 'c' => 3, 'd' => 4, 'e' => 5, 'f' => 6, 'g' => 7, 'h' => 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 > 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 <= 8 &&$new_valid_row > 0) && ($new_valid_col <= 8 &&$new_valid_col > 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";
}

?>


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 */
}


migrated from stackoverflow.comJun 1 '11 at 0:36

This question came from our site for professional and enthusiast programmers.

• what is the question? :O – SpyrosP Jun 1 '11 at 0:06
• Erm, what's the actual problem you get ? – Russ C Jun 1 '11 at 0:07
• Whats the question? It's passed my quick read/obvious error test. Does it work? – Paystey Jun 1 '11 at 0:08
• "Share our thoughts"? my thought is that it should work, what else were you looking for? – trutheality Jun 1 '11 at 0:10
• This can certainly be restructured more nicely. Short tip: instead of substr use $row =$strStartingMove[0]; and $col =$strStartingMove[1]; or better yet pass the coordinates around as array and/or integers only. – mario Jun 1 '11 at 0:10

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 < 120; $i++) {$row[] = ($i < 20 ||$i > 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] => 2f
[1] => 3g
)
Array
(
[0] => 6d
[1] => 4d
[2] => 3a
[3] => 7c
[4] => 3c
[5] => 7a
)
Array
(
[0] => 5a
[1] => 7e
[2] => 5e
[3] => 7a
[4] => 4b
[5] => 8d
[6] => 4d
[7] => 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.

• Note: I should have used notation like "a8" instead of "8a" of course. That should be a trivial fix left to anyone who finds this in the future. – Wayne Burkett Jan 5 '14 at 6:06

function GetValidKnightSquares($strStartingMove){$rowvals='abcdefgh';
$row_assoc=array_flip(str_split($rowvals));
$row =$strStartingMove[0]-1;
if(!strstr($rowvals,$row)){
die('invalid row');
}
$col =$strStartingMove[1];
if($col<1 ||$col>7){
die('invalid column');
}
$srow=$row_assoc[$row];$valid_moves=array(
$row_assoc[$srow+2].$col+1,$row_assoc[$srow+2].$col-1,
$row_assoc[$srow-2].$col+1,$row_assoc[$srow-2].$col-1,
$row_assoc[$srow+1].$col+2,$row_assoc[$srow+1].$col-2,
$row_assoc[$srow-1].$col+2,$row_assoc[$srow-1].$col-2,
);
return "Valid knight moves for knight on $strStartingMove are: ".implode(', ',$valid_moves);
}

• This one doesn't check the board borders. Also you could make it even shorter by setting up two nested for loops to change the signs. – trutheality Jun 1 '11 at 0:28
• shorter != faster, but yes I didn't check for borders, if he wrote the other code, he should be able to figure out where that goes;) – trey Jun 1 '11 at 0:31
• Well we don't know whether he's going for easily maintainable code or fast code. Also the performance difference is going to be insignificant here unless he's doing calling that function thousands of times in a row. – trutheality Jun 1 '11 at 0:34
• I always worry about overhead beacuse I generally run large multi-user sites an web apps.... do you have any useful criticism? – Trey Jun 1 '11 at 0:38
• Nothing besides the fact that seeing a programmer do something the program should be doing (like generate 8 lines of almost identical code, or map letters to numbers in alphabetical order) is usually a bad sign. – trutheality Jun 1 '11 at 0:56

Another way:

function GetValidKnightSquares($strStartingMove){$row_letters = array_combine(range(1,8),range('a','h'));
$row_numbers = array_flip($row_letters);
$row =$row_numbers[$strStartingMove[0]];$col = $strStartingMove[1];$valid_moves = array();
foreach( array( 1=>2, 2=>1 ) as $r=>$c )
foreach( array( -1, 1 ) as $r_sign ) foreach( array( -1, 1 ) as$c_sign )
$valid_moves[] =$row_letters[$row +$r * $r_sign].($col + $c *$c_sign);

// This line from trey's code is actually pretty neat.
return "Valid knight moves for knight on $strStartingMove are: ".implode(', ',$valid_moves);
}