Microsoft Interview Question Software Engineer / Developers
Country: India
We can take two array[16] of bytes each contains coordinates of each pieces.
We store coordinates of black pieces in first array and white ones on second one.
Coordinate of each piece can be stored in one byte value:
0, 0 => 0x00
0, 1 =>0x01
1, 0 => 0x10
...
7, 6 => 0x76
I like this solution. Only 32 bytes needed. If you were insane about compressing things you can store every position with just 6 bits too, reducing memory use further to 24 bytes. The extra complexity's probably not worth it though.
We can further reduce the space to 24 bytes. Lets see how.
There can be only 8 information: pawn,king,queen,bishop,knight,rook,no piece[empty] & color of piece.
So, we need 3 bits to represent to represent these information.
We can design a 8x8 chessboard with each slot occupying exactly 3 bits using bit-field[can represent range from 0 to 7].So, the space reduces to 64x3bits=24bytes.
You are assuming that only 16 pieces( i think 8 soldiers) can be on a board.But the soldiers can be converted into queen.So at one instance maximum 9 queens on board?..
or am i missing anything here?
@shondik: you need 4 bits per square. The color of the piece is in combination with the other attributes. In other words, the distinct possibilities are (king, black), (king, white), (queen, black), (queen, white);, etc.
I think we can accomplish this using 32 bytes.Since each byte has 8 bits, we can use
1. The Least significant 6 bits to store the location of a piece 2. The 7th bit to identify if it is present or not on the board.
3. The 8th bit can be used to specify if it is a black piece or a white piece.
Please correct me if Im wrong..or if I missed something here.
I think it should be something close to listing 8x8 cells, and the occupany status of each cell. Also, for the cells being occupied, we should be able to tell which piece (pawn/bishop/king....etc) has occupied that cell.
Can't think of a simple primitive datastructure for this. Must have to be a combination of 2 or more datastructures.
We can take a 2D array[8x8], where each slot can contain one of the 7 things.
rook,bishop,king,queen,knight, pawn & empty.
So, the pieces can be represented by a single integer using bit vector.
a 8x8 byte array would be more optimized in space. 1 byte can represent 255 different things. so its easy to represent all the 32 peices (16 for each player black and white) using 1 byte.
I think there is little more to this problem. State of the chess board is not only which of the cells are occupied, but what that cell contain. So each cell would be representing the following
1) State ( Occupied/Empty)
2) Color of the Piece (White/Black)
3) Type of the Piece.
I think the problem will be focusing on, storing the state of the chessboard so that we can recover the state from the data structure at any point in time.
Lets consider the requirements for a piece first and then can be taken care of for all the 32 pieces.
In a 2-D matrix we need following to represent a piece:
1. coordinates-(x,y): can be represented by 6 bits, 3 for x and 3 for y
2. If the piece is present or not: 1 bit
hence to represent one piece we need 7 bits and to represent 32 pieces we need 32*7 bits = 28bytes
DS can be an array, whose index will give us the type of piece.
Say, first 7 bits of a[0] would give us a black pawn status
cant it be char [2^64][8][8] array ?? we can create a character map for 8X8 elements like this
black (all odd numbers):
queen : 1
king : 3
pawns : 11
white (all even numbers):
queen ; 2
king : 4
pawns : 10
ideally it should be 2^64 - 1 positions if we are ignoring the nothing on chess board :) : ) !!
We need to store 4 things
1. color
2. presence
3. type of the coin
4. location
Locations range is (0,0) = 0x00 to (7,7) = 0x77 which need 6bits. That means 32 * 6bits = 24bytes (for storing the locations)
1 bit for color => 32 bits = 4 bytes
1 bit for presence => 32 bits = 4 bytes
3 bits for type of coin (000 - pawn, 001 - bishop, 010 - knight , 011 -rook, 100- queen, 101 - king) => 3*32 = 12 bytes
Total = 44 bytes
start with simple solutions -
- nil_dream June 26, 20121) we can use multi dimentional matrix with arrays in C, where each element indicates position of piece as 0 or 1. you can even implement one dimentional array and use it as 2 dimentional by using row size.
2) In Java we can use arrayList also for the same..
As it is 8*8 array, you dont need any advanced DS to lookup or insert into it..