10
\$\begingroup\$

The following is my solution to a problem. While it works - I want to learn how to optimize this in a much better way (I'm new to C++). My original idea was the use a map to map the r,c pairs and then test those but hoping someone can help optimize this for me.

Write a function using a grid of string and two row/column pairs (r1, c1), (r2, c2) which returns true if there is a knight at chess board square (r1, c1) who can move to empty square (r2, c2). For your function to return true, there must be a knight at square (r1, c1), and the square at (r2, c2) must store an empty string, and both locations must be within the bounds of the grid. A knight makes an "L" shaped move, going 2 squares in one dimension and 1 square in the other. i.e. if the chess board (1, 2) stores "knight", then the call of knightMoves(board, 1, 2, 2, 4) returns true.

Here is my current solution

bool knightMoves(Grid<string>& board, int r1, int c1, int r2, int c2);

int main() {

    //create a fake board
    Grid<string> board(7,7);
    board[1][2] = "knight";
    board[3][1] = "rock";
    board[0][4] = "king";

    //fire the function
    bool result = knightCanMove(board, 1, 2, 2, 4);
    cout << result << endl;

    return 0;
}

bool knightMoves(Grid<string>& board, int r1, int c1, int r2, int c2) {

    bool canMove = false;
    string knight = "knight";

    //within grid bounds
    if(r1 > board.numRows() || c1 > board.numCols()) return false;
    if(r2 > board.numRows() || c2 > board.numCols()) return false;

    //test whether the co-ords match a knight string,
    //if yes, continue
    if (board[r1][c1] == knight) {
        if(board[r1 + 2][c1 + 1] == "" && r1+2 == r2 && c1+1 == c2) {
            canMove = true;
        }
        if(board[r1 + 2][c1 - 1] == "" && r1+2 == r2 && c1-1 == c2) {
            canMove = true;
        }
        if(r1 >= 2 && board[r1 - 2][c1 + 1] == "" && r1-2 == r2 && c1+1 == c2) {
            canMove = true;
        }
        if(r1 >= 2 && board[r1 - 2][c1 - 1] == "" && r1-2 == r2 && c1-1 == c2) {
            canMove = true;
        }
        if(board[r1 + 1][c1 + 2] == "" && r1+1 == r2 && c1+2 == c2) {
            canMove = true;
        }
        if(c1 >= 2 && board[r1 + 1][c1 - 2] == "" && r1+1 == r2 && c1-2 == c2) {
            canMove = true;
        }
        if(board[r1 - 1][c1 + 2] == "" && r1-1 == r2 && c1+2 == c2) {
            canMove = true;
        }
        if(c1 >= 2 && board[r1 - 1][c1 - 2] == "" && r1-1 == r2 && c1-2 == c2) {
            canMove = true;
        }
    }
    return canMove;
}
\$\endgroup\$

3 Answers 3

7
\$\begingroup\$

It looks like there may be an issue in range-checking.

  1. You don't check for the rows and columns to be non-negative. ( < 0 ) The types aren't marked as unsigned, so they might be negative.
  2. If board is zero-based, and it seems to be, checking against numXYZ should include the boundary. ( >= board.numXYZ() )

The range check becomes:

if ( r1 < 0 || r1 >= board.numRows() ||
     r2 < 0 || r2 >= board.numRows() ||
     c1 < 0 || c1 >= board.numCols() ||
     c2 < 0 || c2 >= board.numCols() ) {
  return false;
}

The jump check can be simplified. The absolute distance in one dimension must be one, and in the other must be two.

unsigned int rowdiff = abs(r1 - r2);
unsigned int coldiff = abs(c1 - c2);
if ( rowdiff == 1 && coldiff == 2 || rowdiff == 2 && coldiff == 1 )

Alternatively, we can note that the product of the distances must be ±2, leading to a more concise check, but that may obscure the underlying objective:

if ( abs((r1 - r2) * (c1 - c2)) != 2 ) return false;

At which point the final check is:

return board[r1][c1] == "knight" && board[r2][c2] == "";
\$\endgroup\$
4
  • \$\begingroup\$ You final check only checks for empty squares but would not allow a square occupied by an opposition piece so the knight would never be able to capture. \$\endgroup\$ Oct 8, 2017 at 3:44
  • 4
    \$\begingroup\$ I personally think abs((r1 - r2) * (c1 - c2)) != 2 is overly clever. It takes some thought to realize that it's the correct condition. I would put rd = abs(r1 - r2) and cd = abs(c1 - c2) and then test something like (rd == 1 && cd == 2) || (rd == 2 && cd == 1) \$\endgroup\$ Oct 8, 2017 at 12:22
  • 1
    \$\begingroup\$ @SteveBarnes The problem statement is that the end square must be empty. \$\endgroup\$
    – JvR
    Oct 8, 2017 at 15:34
  • \$\begingroup\$ Thanks so much for the suggestions! Its funny that I realized the product must be 2 or -2 but you definitely write that elegantly and thats exactly what I was looking for! \$\endgroup\$
    – Andy
    Oct 8, 2017 at 18:18
7
\$\begingroup\$
  • It is not rock but Rook. Sorry for nitpicking, I am a chess player.

  • Testing only for the coordinates being less than the board size means that you presume them being non-negative. The best way to assure non-negativity is to declare your arguments unsigned.

  • Testing the availability of destination square is independent of the source square, and can be done just once. It is better to factor both tests into independent functions:

        if (!knight_can_reach(c1, r1, c2, r2))
            return false;
        if (square_is_occupied_by_the_piece_of_same_color(board, c2, r2))
            return false;
        // Test for pins here if you wish
        return true;
    
  • Some people (including me) would argue that an illegal source square should result in an exception.

\$\endgroup\$
1
  • \$\begingroup\$ Thanks so much. Great suggestions! The unsigned part is something I know about and definitely missed! \$\endgroup\$
    – Andy
    Oct 8, 2017 at 18:16
6
\$\begingroup\$

I agree with both the other answers. They have good advice. There are some much bigger problems with your code that I'd like to point out.

Named Constants

There are several places where there are important strings in your code. You've got the right idea in the knightMoves() function by assigning a variable to hold the string "knight". (Also, nice name for the function! Not sure if you're a Bob Seger fan, but that gave me a chuckle.) If you were going to use strings to represent all of the chess pieces, you should define them as named constants and only type them once so you don't make a typo somewhere. Something like:

const std::string kKing = "king";
const std::string kQueen = "queen";
//... etc.

However, there's a better way.

Use Types

Your code is what we refer to as stringly typed. This is an antipattern that should be avoided.

C++ is a strongly type (as opposed to stringly typed) language. That is, it allows you to create types for your data and can give you warnings or errors if you use them incorrectly. By making your board be a Grid<string>, anything can go into it and the compiler won't be able to tell you whether it was a mistake or not. For example, instead of a "king" you could accidentally put a "knig" on the board, and it's likely that the rest of your code would be confused by that and do something unexpected. (Or you could put a "frog" or "Norway" or "Erma Bombeck" on the board, too.)

Instead, you should use a named type. In this case, you should use an enumerated type. Something like:

typedef enum ChessPiece {
    kNone,
    kPawn,
    kRook,
    kBishop,
    kKnight,
    kKing,
    kQueen
} ChessPiece;

Then you can make your board be a Grid<ChessPiece> and if you mistype a piece, then the compiler will tell you as soon as it happens.

\$\endgroup\$
2
  • \$\begingroup\$ Awesome suggestion! The enum is definitely the better approach here - thanks! \$\endgroup\$
    – Andy
    Oct 8, 2017 at 18:19
  • 1
    \$\begingroup\$ That looks like a c style enum declaration here. The typedef is unnecessary in c++. Additionally, it is now possible to use enum class which makes the k prefix superfluous. Using class puts the enumerators e.g. kNone here in their own scope ChessPiece::kNone in this case (en.cppreference.com/w/cpp/language/enum) @Andy the reference is a little bit dense and might be overwhelming, but parsing this kind of documentation is a valuable skill to learn, even if you just skim the examples to start with. \$\endgroup\$ Oct 10, 2017 at 18:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.