Programming Challenges: Check the Check

Filed under: Blog — krkhan @ 7:55 pm

PC/UVa IDs: 110107/10196, Popularity: B, Success rate: average, Level: 1

I had two approaches in mind for checking the check before solving this problem:

return a flag value from the move-generation functions as soon as opponent’s king is encountered in a reachable square.
Generate all reachable squares for a side first, and then check whether opponent’s king is positioned on one.

I opted for the latter because even though it was more performance-intensive, it made my move-generation functions more generic and appropriate for extensibility.

#include <iostream>
#include <vector>
#include <iterator>
 
using namespace std;
 
#define EMPTY '.'
#define CROSS 'x'
 
typedef vector< vector< char > > twod_vector;
 
bool opponent(twod_vector board, int row1, int col1, int row2, int col2)
{
	return (islower(board.at(row1).at(col1))
			&& isupper(board.at(row2).at(col2)))
		|| (isupper(board.at(row1).at(col1))
			&& islower(board.at(row2).at(col2)));
}
 
twod_vector generate_move_rook_limit(twod_vector board,
		int row, int col, int limit)
{
	for(int i = row - 1, n = 0; i >= 0 && n < limit; i--, n++) {
		if(board.at(i).at(col) != EMPTY) {
			if(opponent(board, row, col, i, col)) {
				board.at(i).at(col) = CROSS;
			}
			break;
		}
		board.at(i).at(col) = CROSS;
	}
 
	for(int i = row + 1, n = 0; i <= 7 && n < limit; i++, n++) {
		if(board.at(i).at(col) != EMPTY) {
			if(opponent(board, row, col, i, col)) {
				board.at(i).at(col) = CROSS;
			}
			break;
		}
		board.at(i).at(col) = CROSS;
	}
 
	for(int j = col - 1, n = 0; j >= 0 && n < limit; j--, n++) {
		if(board.at(row).at(j) != EMPTY) {
			if(opponent(board, row, col, row, j)) {
				board.at(row).at(j) = CROSS;
			}
			break;
		}
		board.at(row).at(j) = CROSS;
	}
 
	for(int j = col + 1, n = 0; j <= 7 && n < limit; j++, n++) {
		if(board.at(row).at(j) != EMPTY) {
			if(opponent(board, row, col, row, j)) {
				board.at(row).at(j) = CROSS;
			}
			break;
		}
		board.at(row).at(j) = CROSS;
	}
 
	return board;
}
 
twod_vector generate_move_bishop_limit(twod_vector board,
		int row, int col, int limit)
{
	for(int i = row - 1, j = col - 1, n = 0;
			i >= 0 && j >= 0 && n < limit;
			i--, j--, n++) {
		if(board.at(i).at(j) != EMPTY) {
			if(opponent(board, row, col, i, j)) {
				board.at(i).at(j) = CROSS;
			}
			break;
		}
		board.at(i).at(j) = CROSS;
	}
 
	for(int i = row + 1, j = col - 1, n = 0;
			i <= 7 && j >= 0 && n < limit;
			i++, j--, n++) {
		if(board.at(i).at(j) != EMPTY) {
			if(opponent(board, row, col, i, j)) {
				board.at(i).at(j) = CROSS;
			}
			break;
		}
		board.at(i).at(j) = CROSS;
	}
 
	for(int i = row - 1, j = col + 1, n = 0;
			i >= 0 && j <= 7 && n < limit;
			i--, j++, n++) {
		if(board.at(i).at(j) != EMPTY) {
			if(opponent(board, row, col, i, j)) {
				board.at(i).at(j) = CROSS;
			}
			break;
		}
		board.at(i).at(j) = CROSS;
	}
 
	for(int i = row + 1, j = col + 1, n = 0;
			i <= 7
			&& j <= 7
			&& n < limit;
			i++, j++, n++) {
		if(board.at(i).at(j) != EMPTY) {
			if(opponent(board, row, col, i, j)) {
				board.at(i).at(j) = CROSS;
			}
			break;
		}
		board.at(i).at(j) = CROSS;
	}
 
	return board;
}
 
twod_vector generate_move_rook(twod_vector board, int row, int col)
{
	return generate_move_rook_limit(board, row, col, 8);
}
 
twod_vector generate_move_bishop(twod_vector board, int row, int col)
{
	return generate_move_bishop_limit(board, row, col, 8);
}
 
twod_vector generate_move_queen(twod_vector board, int row, int col)
{
	return generate_move_bishop_limit(
			generate_move_rook_limit(board, row, col, 8),
			row,
			col,
			8);
}
 
twod_vector generate_move_king(twod_vector board, int row, int col)
{
	return generate_move_bishop_limit(
			generate_move_rook_limit(board, row, col, 1),
			row,
			col,
			1);
}
 
twod_vector generate_move_pawn_white(twod_vector board, int row, int col)
{
	if(row - 1 >= 0) {
		if(col - 1 >= 0) {
			if(board.at(row - 1).at(col - 1) == EMPTY
				|| opponent(board, row, col,
						row - 1, col - 1)) {
				board.at(row - 1).at(col - 1) = CROSS;
			}
		}
		if(col + 1 <= 7) {
			if(board.at(row - 1).at(col + 1) == EMPTY
				|| opponent(board, row, col,
						row - 1, col + 1)) {
				board.at(row - 1).at(col + 1) = CROSS;
			}
		}
	}
 
	return board;
}
 
twod_vector generate_move_pawn_black(twod_vector board, int row, int col)
{
	if(row + 1 <= 7) {
		if(col - 1 >= 0) {
			if(board.at(row + 1).at(col - 1) == EMPTY
				|| opponent(board, row, col,
						row + 1, col - 1)) {
				board.at(row + 1).at(col - 1) = CROSS;
			}
		}
		if(col + 1 <= 7) {
			if(board.at(row + 1).at(col + 1) == EMPTY
				|| opponent(board, row, col,
						row + 1, col + 1)) {
				board.at(row + 1).at(col + 1) = CROSS;
			}
		}
	}
 
	return board;
}
 
twod_vector generate_move_knight(twod_vector board, int row, int col)
{
	if(row - 2 >= 0) {
		if(col - 1 >= 0) {
			if(board.at(row - 2).at(col - 1) == EMPTY
				|| opponent(board, row, col,
						row - 2, col - 1)) {
				board.at(row - 2).at(col - 1) = CROSS;
			}
		}
		if(col + 1 <= 7) {
			if(board.at(row - 2).at(col + 1) == EMPTY
				|| opponent(board, row, col,
						row - 2, col + 1)) {
				board.at(row - 2).at(col + 1) = CROSS;
			}
		}
	}
 
	if(row + 2 <= 7) {
		if(col - 1 >= 0) {
			if(board.at(row + 2).at(col - 1) == EMPTY
				|| opponent(board, row, col,
						row + 2, col - 1)) {
				board.at(row + 2).at(col - 1) = CROSS;
			}
		}
		if(col + 1 <= 7) {
			if(board.at(row + 2).at(col + 1) == EMPTY
				|| opponent(board, row, col,
						row + 2, col + 1)) {
				board.at(row + 2).at(col + 1) = CROSS;
			}
		}
	}
 
	if(row - 1 >= 0) {
		if(col - 2 >= 0) {
			if(board.at(row - 1).at(col - 2) == EMPTY
				|| opponent(board, row, col,
						row - 1, col - 2)) {
				board.at(row - 1).at(col - 2) = CROSS;
			}
		}
		if(col + 2 <= 7) {
			if(board.at(row - 1).at(col + 2) == EMPTY
				|| opponent(board, row, col,
						row - 1, col + 2)) {
				board.at(row - 1).at(col + 2) = CROSS;
			}
		}
	}
 
	if(row + 1 <= 7) {
		if(col - 2 >= 0) {
			if(board.at(row + 1).at(col - 2) == EMPTY
				|| opponent(board, row,
						col, row + 1, col - 2)) {
				board.at(row + 1).at(col - 2) = CROSS;
			}
		}
		if(col + 2 <= 7) {
			if(board.at(row + 1).at(col + 2) == EMPTY
				|| opponent(board, row, col,
						row + 1, col + 2)) {
				board.at(row + 1).at(col + 2) = CROSS;
			}
		}
	}
 
	return board;
}
 
twod_vector generate_move(twod_vector board, int row, int col)
{
	switch(board.at(row).at(col)) {
	case 'R':
	case 'r':
		return generate_move_rook(board, row, col);
		break;
	case 'B':
	case 'b':
		return generate_move_bishop(board, row, col);
		break;
	case 'Q':
	case 'q':
		return generate_move_queen(board, row, col);
		break;
	case 'K':
	case 'k':
		return generate_move_king(board, row, col);
		break;
	case 'P':
		return generate_move_pawn_white(board, row, col);
		break;
	case 'p':
		return generate_move_pawn_black(board, row, col);
		break;
	case 'N':
	case 'n':
		return generate_move_knight(board, row, col);
		break;
	}
 
	return board;
}
 
char mix_board_position(char a, char b)
{
	if(a == CROSS || b == CROSS) {
		return CROSS;
	}
	if(a == EMPTY) {
		return b;
	}
	return a;
}
 
twod_vector join_boards(twod_vector board1, twod_vector board2)
{
	twod_vector v(8, vector< char >(8, EMPTY));
 
	for(int i = 0; i <=7; i++) {
		transform(board1.at(i).begin(),
				board1.at(i).end(),
				board2.at(i).begin(),
				v.at(i).begin(),
				mix_board_position);
	}
 
	return v;
}
 
twod_vector calculate_reach(const twod_vector board, bool white)
{
	twod_vector reach(8, vector< char >(8, EMPTY));
 
	for(int i = 0; i <= 7; i++) {
		for(int j = 0; j<= 7; j++) {
			if((bool) isupper(board.at(i).at(j)) == white) {
				reach = join_boards(
						generate_move(
							board,
							i,
							j),
						reach
						);
			}
		}
	}
 
	return reach;
}
 
bool check_check(twod_vector board, bool white)
{
	char king = (white ? 'K' : 'k');
	twod_vector reach = calculate_reach(board, !white);
 
	for(int i = 0; i <= 7; i++) {
		for(int j = 0; j <= 7; j++) {
			if(board.at(i).at(j) == king) {
				if(reach.at(i).at(j) == CROSS) {
					return true;
				} else {
					return false;
				}
			}
		}
	}
 
	return false;
}
 
bool is_board_empty(twod_vector board)
{
	for(int i = 0; i <= 7; i++) {
		for(int j = 0; j <= 7; j++) {
			if(board.at(i).at(j) != EMPTY) {
				return false;
			}
		}
	}
 
	return true;
}
 
ostream& operator<<(ostream &out, twod_vector v)
{
	twod_vector::const_iterator p;
 
	for(p = v.begin(); p < v.end(); p++) {
		copy((*p).begin(), (*p).end(),
				ostream_iterator< char >(cout, ""));
		cout<<endl;
	}
 
	return out;
}
 
istream& operator>>(istream& in, twod_vector &v)
{
	for(twod_vector::iterator p = v.begin(); p < v.end(); p++) {
		for(vector< char >::iterator pr = (*p).begin();
				pr < (*p).end();
				pr++) {
			*pr = *istream_iterator< char >(in);
		}
	}
 
	return in;
}
 
int main(int argc, char *argv[])
{
	twod_vector board(8, vector< char >(8, '\0'));
 
	int i = 1;
	cin>>board;
	while(!is_board_empty(board)) {
		if(check_check(board, true)) {
			cout<<"Game #"<<i<<": white king is in check."
				<<endl;
		} else if(check_check(board, false)) {
			cout<<"Game #"<<i<<": black king is in check."
				<<endl;
		} else {
			cout<<"Game #"<<i<<": no king is in check."
				<<endl;
		}
 
		string dummy;
		getline(cin, dummy);
		cin>>board;
 
		i++;
	}
 
	return 0;
}

#include <iostream> #include <vector> #include <iterator> using namespace std; #define EMPTY '.' #define CROSS 'x' typedef vector< vector< char > > twod_vector; bool opponent(twod_vector board, int row1, int col1, int row2, int col2) { return (islower(board.at(row1).at(col1)) && isupper(board.at(row2).at(col2))) || (isupper(board.at(row1).at(col1)) && islower(board.at(row2).at(col2))); } twod_vector generate_move_rook_limit(twod_vector board, int row, int col, int limit) { for(int i = row - 1, n = 0; i >= 0 && n < limit; i--, n++) { if(board.at(i).at(col) != EMPTY) { if(opponent(board, row, col, i, col)) { board.at(i).at(col) = CROSS; } break; } board.at(i).at(col) = CROSS; } for(int i = row + 1, n = 0; i <= 7 && n < limit; i++, n++) { if(board.at(i).at(col) != EMPTY) { if(opponent(board, row, col, i, col)) { board.at(i).at(col) = CROSS; } break; } board.at(i).at(col) = CROSS; } for(int j = col - 1, n = 0; j >= 0 && n < limit; j--, n++) { if(board.at(row).at(j) != EMPTY) { if(opponent(board, row, col, row, j)) { board.at(row).at(j) = CROSS; } break; } board.at(row).at(j) = CROSS; } for(int j = col + 1, n = 0; j <= 7 && n < limit; j++, n++) { if(board.at(row).at(j) != EMPTY) { if(opponent(board, row, col, row, j)) { board.at(row).at(j) = CROSS; } break; } board.at(row).at(j) = CROSS; } return board; } twod_vector generate_move_bishop_limit(twod_vector board, int row, int col, int limit) { for(int i = row - 1, j = col - 1, n = 0; i >= 0 && j >= 0 && n < limit; i--, j--, n++) { if(board.at(i).at(j) != EMPTY) { if(opponent(board, row, col, i, j)) { board.at(i).at(j) = CROSS; } break; } board.at(i).at(j) = CROSS; } for(int i = row + 1, j = col - 1, n = 0; i <= 7 && j >= 0 && n < limit; i++, j--, n++) { if(board.at(i).at(j) != EMPTY) { if(opponent(board, row, col, i, j)) { board.at(i).at(j) = CROSS; } break; } board.at(i).at(j) = CROSS; } for(int i = row - 1, j = col + 1, n = 0; i >= 0 && j <= 7 && n < limit; i--, j++, n++) { if(board.at(i).at(j) != EMPTY) { if(opponent(board, row, col, i, j)) { board.at(i).at(j) = CROSS; } break; } board.at(i).at(j) = CROSS; } for(int i = row + 1, j = col + 1, n = 0; i <= 7 && j <= 7 && n < limit; i++, j++, n++) { if(board.at(i).at(j) != EMPTY) { if(opponent(board, row, col, i, j)) { board.at(i).at(j) = CROSS; } break; } board.at(i).at(j) = CROSS; } return board; } twod_vector generate_move_rook(twod_vector board, int row, int col) { return generate_move_rook_limit(board, row, col, 8); } twod_vector generate_move_bishop(twod_vector board, int row, int col) { return generate_move_bishop_limit(board, row, col, 8); } twod_vector generate_move_queen(twod_vector board, int row, int col) { return generate_move_bishop_limit( generate_move_rook_limit(board, row, col, 8), row, col, 8); } twod_vector generate_move_king(twod_vector board, int row, int col) { return generate_move_bishop_limit( generate_move_rook_limit(board, row, col, 1), row, col, 1); } twod_vector generate_move_pawn_white(twod_vector board, int row, int col) { if(row - 1 >= 0) { if(col - 1 >= 0) { if(board.at(row - 1).at(col - 1) == EMPTY || opponent(board, row, col, row - 1, col - 1)) { board.at(row - 1).at(col - 1) = CROSS; } } if(col + 1 <= 7) { if(board.at(row - 1).at(col + 1) == EMPTY || opponent(board, row, col, row - 1, col + 1)) { board.at(row - 1).at(col + 1) = CROSS; } } } return board; } twod_vector generate_move_pawn_black(twod_vector board, int row, int col) { if(row + 1 <= 7) { if(col - 1 >= 0) { if(board.at(row + 1).at(col - 1) == EMPTY || opponent(board, row, col, row + 1, col - 1)) { board.at(row + 1).at(col - 1) = CROSS; } } if(col + 1 <= 7) { if(board.at(row + 1).at(col + 1) == EMPTY || opponent(board, row, col, row + 1, col + 1)) { board.at(row + 1).at(col + 1) = CROSS; } } } return board; } twod_vector generate_move_knight(twod_vector board, int row, int col) { if(row - 2 >= 0) { if(col - 1 >= 0) { if(board.at(row - 2).at(col - 1) == EMPTY || opponent(board, row, col, row - 2, col - 1)) { board.at(row - 2).at(col - 1) = CROSS; } } if(col + 1 <= 7) { if(board.at(row - 2).at(col + 1) == EMPTY || opponent(board, row, col, row - 2, col + 1)) { board.at(row - 2).at(col + 1) = CROSS; } } } if(row + 2 <= 7) { if(col - 1 >= 0) { if(board.at(row + 2).at(col - 1) == EMPTY || opponent(board, row, col, row + 2, col - 1)) { board.at(row + 2).at(col - 1) = CROSS; } } if(col + 1 <= 7) { if(board.at(row + 2).at(col + 1) == EMPTY || opponent(board, row, col, row + 2, col + 1)) { board.at(row + 2).at(col + 1) = CROSS; } } } if(row - 1 >= 0) { if(col - 2 >= 0) { if(board.at(row - 1).at(col - 2) == EMPTY || opponent(board, row, col, row - 1, col - 2)) { board.at(row - 1).at(col - 2) = CROSS; } } if(col + 2 <= 7) { if(board.at(row - 1).at(col + 2) == EMPTY || opponent(board, row, col, row - 1, col + 2)) { board.at(row - 1).at(col + 2) = CROSS; } } } if(row + 1 <= 7) { if(col - 2 >= 0) { if(board.at(row + 1).at(col - 2) == EMPTY || opponent(board, row, col, row + 1, col - 2)) { board.at(row + 1).at(col - 2) = CROSS; } } if(col + 2 <= 7) { if(board.at(row + 1).at(col + 2) == EMPTY || opponent(board, row, col, row + 1, col + 2)) { board.at(row + 1).at(col + 2) = CROSS; } } } return board; } twod_vector generate_move(twod_vector board, int row, int col) { switch(board.at(row).at(col)) { case 'R': case 'r': return generate_move_rook(board, row, col); break; case 'B': case 'b': return generate_move_bishop(board, row, col); break; case 'Q': case 'q': return generate_move_queen(board, row, col); break; case 'K': case 'k': return generate_move_king(board, row, col); break; case 'P': return generate_move_pawn_white(board, row, col); break; case 'p': return generate_move_pawn_black(board, row, col); break; case 'N': case 'n': return generate_move_knight(board, row, col); break; } return board; } char mix_board_position(char a, char b) { if(a == CROSS || b == CROSS) { return CROSS; } if(a == EMPTY) { return b; } return a; } twod_vector join_boards(twod_vector board1, twod_vector board2) { twod_vector v(8, vector< char >(8, EMPTY)); for(int i = 0; i <=7; i++) { transform(board1.at(i).begin(), board1.at(i).end(), board2.at(i).begin(), v.at(i).begin(), mix_board_position); } return v; } twod_vector calculate_reach(const twod_vector board, bool white) { twod_vector reach(8, vector< char >(8, EMPTY)); for(int i = 0; i <= 7; i++) { for(int j = 0; j<= 7; j++) { if((bool) isupper(board.at(i).at(j)) == white) { reach = join_boards( generate_move( board, i, j), reach ); } } } return reach; } bool check_check(twod_vector board, bool white) { char king = (white ? 'K' : 'k'); twod_vector reach = calculate_reach(board, !white); for(int i = 0; i <= 7; i++) { for(int j = 0; j <= 7; j++) { if(board.at(i).at(j) == king) { if(reach.at(i).at(j) == CROSS) { return true; } else { return false; } } } } return false; } bool is_board_empty(twod_vector board) { for(int i = 0; i <= 7; i++) { for(int j = 0; j <= 7; j++) { if(board.at(i).at(j) != EMPTY) { return false; } } } return true; } ostream& operator<<(ostream &out, twod_vector v) { twod_vector::const_iterator p; for(p = v.begin(); p < v.end(); p++) { copy((*p).begin(), (*p).end(), ostream_iterator< char >(cout, "")); cout<<endl; } return out; } istream& operator>>(istream& in, twod_vector &v) { for(twod_vector::iterator p = v.begin(); p < v.end(); p++) { for(vector< char >::iterator pr = (*p).begin(); pr < (*p).end(); pr++) { *pr = *istream_iterator< char >(in); } } return in; } int main(int argc, char *argv[]) { twod_vector board(8, vector< char >(8, '\0')); int i = 1; cin>>board; while(!is_board_empty(board)) { if(check_check(board, true)) { cout<<"Game #"<<i<<": white king is in check." <<endl; } else if(check_check(board, false)) { cout<<"Game #"<<i<<": black king is in check." <<endl; } else { cout<<"Game #"<<i<<": no king is in check." <<endl; } string dummy; getline(cin, dummy); cin>>board; i++; } return 0; }

Tags: Algorithms, Bishop, C++, Check, Chess, Code, Function, King, Knight, Pawn, Programming Challenges, Queen, Reference, Rook, STL, Transform, UVa, Vector

Comments (1)

Inspirated

Programming Challenges: Check the Check

1 Comment