Now I have had a crack at another problem, the description is below, sans images
Quote:
CHESS (100 points)
You are working on a chess variant game with a standard 8x8 board and two sides
(black and white), but with different piece types:
The queen moves exactly like a queen in standard chess.
The elephant moves like a rook or a knight
The hawk moves like a bishop or a knight
Elephant moves Hawk moves
Bishop moves in standard chess. Rook moves in standard chess.
Knight moves in standard chess.
Queen moves in standard chess.
Pure straight-line moves can only go as far as they are unobstructed: jumping over other pieces is not allowed. No piece may land on a square occupied by another piece of the same colour. A piece can always land on a square occupied by the opposite colour (capturing that piece).
You are working on the AI for this game, and as part of this, you must write code to generate all possible moves for a given board position.
TASK
Write a program that, given a description of a board position, and a piece, computes the number of possible moves by that piece.
TIME LIMIT
A time limit of 1 second will be placed upon your programme for each test case.
INPUT
Your programme must read from standard input, the following set of data:
Line 1 contains an integer N, the number of pieces on the board.
Each of the next N lines describes a single piece with 3 fields: colour, type,
and square in that order, separated by a space. “Colour” is ‘w’ or ‘b’ for
white or black respectively. “Type” is ‘q’, ‘e’ or ‘h’ for queen, elephant and
hawk respectively. The square is a letter-number (column-row) pair, from
‘a1’ for the bottom left and ‘h8’ for the top right corner of the board.
The last line of the file contains the letter-number pair for a piece; this is the piece your programme should calculate moves for.
OUTPUT
Your programme must write to standard output a single integer M, the number of
possible moves for the given piece
EXAMPLE
Sample input
6
b q d6
b q f6
w e f3
w h e4
b q e5
w e d3
f3
Sample Output
16
And my code is as follows, it works for the above test case but I was wondering about a tidier, cleaner approach to evaluating all the possible knight moves
[source lang = "cpp"]//program to look for possible moves of a chess piece - asks for a number of pieces present from a user and //then the user enters the grid reference on an 8x8 board, the type of piece and color for each piece. //The Grid reference for the piece to test is then entered, and then each of the possible moves by the piece are //counted and output #include <iostream> #include <string> using namespace std;//enums for piece and colour typesenum PIECE{EMPTY,HAWK,ELEPHANT,QUEEN}; enum COLOUR{BLACK,WHITE};//a struct to hold a grid reference struct Position { int x; int y; };//a struct to represent a square on a chess board //shows if the square is empty or not and what colour the piece is if sostruct Square { PIECE pieceType; COLOUR pieceColour; };//const values for the size of the board, and to help work out grid refs //from string inputconst int BOARDSIZE = 8; const int ASCIIVALCHAR = 97; const int ASCIIVALNUM = 49;//const values to represent possible directions on a chess board, with a value //STILL to represent no movement, its just a lot more explanatory than a 0const int LEFT = -1; const int RIGHT = 1; const int DOWN = 1; const int UP = -1; const int STILL = 0;//typedef an int DIR just to make prototypes clearer typedef int DIR;//typedef a chessboard, an 8 x 8 grid of squares typedef Square board[BOARDSIZE][BOARDSIZE];//function prototypes void initBoard(board&); void getData(board&,string&); Square returnPiece(char,char); void evaluateMoves(board&,string&); void EvalDiagonalMoves(board&, COLOUR, Position&,int& );void EvalStraightMoves(board&, COLOUR, Position&,int&);void EvalKnightMoves(board&, COLOUR, Position&,int&);void TestDirection(board&, COLOUR, int, int,int&,DIR, DIR);PIECE returnPiece(char);int main() { string testingSquare; board ChessBoard; initBoard(ChessBoard); getData(ChessBoard,testingSquare); evaluateMoves(ChessBoard,testingSquare); return 0; }//initialise all the board squares to EMPTY void initBoard(board& chessboard) { for(int i = 0; i < BOARDSIZE; i++) { for(int j = 0; j < BOARDSIZE; j++) { chessboard[j].pieceType = EMPTY; } } }//gets all input necessary from the user, assumes that all input is correct void getData(board& chessboard, string& testSquare) { int numPieces; char colour; char piece; string position; cin >> numPieces; for(int i = 0; i < numPieces; i++) { cin >> colour >> piece >> position; chessboard[position[0] - ASCIIVALCHAR ][position[1] - ASCIIVALNUM].pieceType = returnPiece(piece); if(colour == 'b') chessboard[position[0] -ASCIIVALCHAR][position[1]- ASCIIVALNUM].pieceColour = BLACK; else chessboard[position[0] - ASCIIVALCHAR][position[1]- ASCIIVALNUM].pieceColour = WHITE; } cin >>testSquare; }//returns a piece value depending on the passed char value PIECE returnPiece(char piece) { switch(piece) { case 'e' : return ELEPHANT; case 'h' : return HAWK; case 'q' : return QUEEN; default : return EMPTY; } }//this evaluates the amount of moves depending on the configuration of the //chess board, and the string representation of the grid ref that gets broken down //into two integer indexes. These indexes are used to get the type of the piece, colour //etc. It assumes all info passed in to be correct.void evaluateMoves(board& chessboard,string& testSquare) { Position testPos; testPos.x = testSquare[0] - ASCIIVALCHAR; testPos.y = testSquare[1] - ASCIIVALNUM; PIECE piece = chessboard[testPos.x][testPos.y].pieceType; COLOUR colour = chessboard[testPos.x][testPos.y].pieceColour; int numMoves = 0; //now the possible num of moves are calculated by calling routines depending //on the piece type, the total number is passed by reference so it is added up. switch(piece) { case HAWK : EvalDiagonalMoves(chessboard,colour,testPos,numMoves); EvalKnightMoves(chessboard,colour,testPos,numMoves); break; case ELEPHANT : EvalStraightMoves(chessboard,colour,testPos,numMoves); EvalKnightMoves(chessboard,colour,testPos,numMoves); break; case QUEEN : EvalStraightMoves(chessboard,colour,testPos,numMoves); EvalDiagonalMoves(chessboard,colour,testPos,numMoves); break; } cout << numMoves<<endl; }//Wrapper function for TestDirection() - passes appropriate values for horizontal and //vertical movement to represent straight lines of movementvoid EvalStraightMoves(board& chessboard, COLOUR colour, Position& pos,int& moves) { //strategy - check up, down, left, right TestDirection(chessboard,colour, pos.x, pos.y + UP ,moves,UP,STILL); TestDirection(chessboard,colour, pos.x, pos.y + DOWN ,moves,DOWN,STILL); TestDirection(chessboard,colour, pos.x + LEFT, pos.y,moves,STILL,LEFT); TestDirection(chessboard,colour, pos.x + RIGHT, pos.y,moves,STILL,RIGHT); }//Wrapper function for TestDirection() - passes appropriate values for horizontal and //vertical movement to represent diagonal lines of movementvoid EvalDiagonalMoves(board& chessboard, COLOUR colour, Position& pos,int& moves) { //strategy - check up-left,up-right,down-right,down-left TestDirection(chessboard,colour, pos.x + LEFT, pos.y + UP ,moves,UP,LEFT); TestDirection(chessboard,colour, pos.x + RIGHT, pos.y + UP ,moves,UP,RIGHT); TestDirection(chessboard,colour, pos.x + RIGHT, pos.y + DOWN,moves,DOWN,RIGHT); TestDirection(chessboard,colour, pos.x + LEFT, pos.y + DOWN,moves,DOWN,LEFT); }//tests each possible knight move individually to see if legal using //bounds checking and testing if square is emptyvoid EvalKnightMoves(board& chessboard, COLOUR colour, Position& pos,int& moves) { //own algorithm for this - check if landing square is //either out of bounds, on another piece - if so check colour if(pos.x + 2 < BOARDSIZE && pos.y - 1 >= 0) { if(chessboard[pos.x+2][pos.y-1].pieceType == EMPTY) { moves++; } else { if(chessboard[pos.x+2][pos.y-1].pieceColour != colour) moves++; } } if(pos.x + 2 < BOARDSIZE && pos.y + 1 < BOARDSIZE) { if(chessboard[pos.x+2][pos.y+1].pieceType == EMPTY) { moves++; } else { if(chessboard[pos.x+2][pos.y+1].pieceColour != colour) moves++; } } if(pos.x - 2 >= 0 && pos.y - 1 >= 0) { if(chessboard[pos.x-2][pos.y-1].pieceType == EMPTY) { moves++; } else { if(chessboard[pos.x-2][pos.y-1].pieceColour != colour) moves++; } } if(pos.x - 2 >= 0 && pos.y + 1 < BOARDSIZE) { if(chessboard[pos.x-2][pos.y+1].pieceType == EMPTY) { moves++; } else { if(chessboard[pos.x-2][pos.y+1].pieceColour != colour) moves++; } } if(pos.x + 1 < BOARDSIZE && pos.y - 2 >= 0) { if(chessboard[pos.x+1][pos.y-2].pieceType == EMPTY) { moves++; } else { if(chessboard[pos.x+1][pos.y-2].pieceColour != colour) moves++; } } if(pos.x - 1 >= 0 && pos.y - 2 >= 0) { if(chessboard[pos.x-1][pos.y-2].pieceType == EMPTY) { moves++; } else { if(chessboard[pos.x-1][pos.y-2].pieceColour != colour) moves++; } } if(pos.x + 1 < BOARDSIZE && pos.y + 2 < BOARDSIZE) { if(chessboard[pos.x+1][pos.y+2].pieceType == EMPTY) { moves++; } else { if(chessboard[pos.x+1][pos.y+2].pieceColour != colour) moves++; } } if(pos.x - 1 >= 0 && pos.y +2 < BOARDSIZE) { if(chessboard[pos.x - 1][pos.y + 2].pieceType == EMPTY) { moves++; } else { if(chessboard[pos.x - 1][pos.y + 2].pieceColour != colour) moves++; } } }//recursive procedure used to calculate possible number of moves - first of all tests if passed //position is within the board and legal, then tests if the square is empty. If so this is a legal //move, increment the total by one and call the procedure again by one square in the appropriate direction. //If not test if the piece in the square is the same color - if it is no go, if not increase by one and //end the recursion.void TestDirection(board& chessboard, COLOUR colour, int x, int y,int& moves,DIR vert, DIR horiz) { if(x < BOARDSIZE && x >= 0 && y < BOARDSIZE && y >= 0) { if(chessboard[x][y].pieceType == EMPTY) { moves++; TestDirection(chessboard,colour,x+horiz,y+vert,moves,vert,horiz); } else { if(chessboard[x][y].pieceColour != colour) moves++; } } }I will post some images to explain the sample input asap, as well as some other diagrams
Thanks in advance, I'm curious to see what we can all learn here
[Edited by - MrLloyd1981 on December 7, 2010 4:53:49 PM]
