Programming Challenge 7 - Validate Chess Positions

This programming Challenge runs until the end of December 31st 2007. You are provided with a file of 10,000 strings representing a position in a chess game. Write a function to determine if each position is valid or not according to the pieces and pawns.

The Strings are made up of individual characters KQRBPN (white) and kqrbpn (black). Upper case is white, lower case is black.

8 x P (8 White Pawns)
8 x p (8 Black Pawns)
1 x K 1 White King
1 x k 1 Black King
1 x Q 1 White Queen
1 x q 1 Black queen
2 x R 2 White Rooks
2 x r 2 Black Rooks
2 x B 2 White Bishops
2 x b 1 Black Bishops
2 x N 2 White Knights
2 x n 2 Black Knights
32 x . 32 Empty Squares

The starting layout is Black at the top, white at the bottom.

rnbqkbnr
pppppppp
........
........
........
........
PPPPPPPP
RNBQKBNR

So the string for this position is

rnbqkbnrpppppppp................................PPPPPPPPRNBQKBNR

This is the layout After the Kings pawn moves two squares forward

rnbqkbnr
pppppppp
........
........
....P...
........
PPPP.PPP
RNBQKBNR

would be

rnbqkbnrpppppppp....................P...........PPPP.PPPRNBQKBNR

A chessboard squares are alternating black and white color with the bottom right square being white.

WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

A valid position is a position with a valid number of pieces which I've summarized below. Assume absolutely nothing about the provided strings- they may even be the wrong length or contain invalid chars both of which would be invalid.

Scoring is by points. You get 1 point for each line that is correctly identified as a valid or invalid position. (Theoretically a maximum of 10,000 points) plus 100 points for each position which is valid and you correctly spot that a King is in Check (if they are). In the case of a tie the total fastest time wins, so please add timing code!

• How To Time C Code.
• How To Time C++ Code.
• How To Time C# Code.

Valid Positions

• The game must have no more than the correct number of pawns and pieces (King, Queen, Rook, Knight and Bishop). The minimum number of pieces and pawns is just two kings. To simplify things, no pawn promotion is allowed so the maximum number of rooks, bishops and knights is two, and one Queen.

• The position must not be an impossible situation (e.g. both Kings next to each other). A position is in check (i.e. an opponent's piece or pawn will take the opposing King on its next move) is a valid position.

• Bishops of the same player must always be on opposite color squares. One starts on a black square, the other on a white square and as they only move diagonally, they can never move to a different colored square.

Wikipedia has the rules of Chess if you are unfamiliar with them.

Note: This does not need to check that a position is reachable. That would be impossibly tough! Just check that the number of pieces is ok as quickly as possible.

The Challenge

Write an application to read the file (which will be made available here shortly). It will be 10,000 lines long, with each line terminating in a '\n''\r' sequence, i.e. (0xd, 0xa) which is a Carriage Return and a Linefeed character.

Download boards.zip

Please time how long it took to validate the positions as the first line of output before the validation output. I.e. you should time after you have read the 10,000 lines in and before you output the 200 lines below.

Your application (GUI or Command line) should then output to a text file with 50 characters per line, making 200 lines, i.e. one character per position with positions 1-50 in the first line, 51-100 in the second etc. Each character represents one of the positions and should be one of the letters I, V or C.

• I - Invalid
• V- Valid
• C - Valid and in Check.

How you determine if a position could be valid or not is up to you! That's where your ingenuity comes in. E.g. your output file will look a bit like this:

Time To Validate = 23.456 seconds
IIIVIVVCIVIIVVIVIVIIVVIIIIIVIVVCIVIIVVIVIVIIVVII
IVIVVCIVIIVVIVIVIIVVIIIIIVIVVCIVIIVVIVIVIIVVIIVC
...

The Results

Thanks to everyone who entered. There were five entries and congratulations to Robert C Cartaino who won with 8645 points just ahead of Ennixo with 8578.

1. Robert C. Cartaino, c#, 8645 Points (USA, 41)
2. Ennixo, C#, 8578 Points
3. Tingly Ling, C#, 8012 Points
4. Siridion Cabudlan, C++ 7596 Points
5. Chris,C++, 7528 Points

I'll upload the source code tomorrow and add links to these.

More Programming Challenges

• Link to Rock, Scissors and Paper Bot Ongoing Programming Challenge - Runs weekly until 2008.
• Link to Programming Challenge 2 - Count the Islands. (Finished)
• Link to Programming Challenge 3 - Manage Elevators. (Finished)
• Link to Programming Challenge 4 - Guess the Mastermind Code - (Finished)
• Link to Programming Challenge 5 - Squeeze words into a crossword grid - (Finished)
• Link to Programming Challenge 6 - Guess the Mastermind Code - (Finished)
• Link to Programming Challenge 8 - Score Texas Holdem Poker Hands - (Deadline January 31 2008)