Saturday, May 14, 2011

Chess Queen Puzzle

Imagine there are infinite number of Queens (Chess Game Piece) with u. Find the minimum number of queens required so that every square grid on the chess board is under the attack of a queen. Arrange this minimum no. of Queens on a chess board.

to solve it we have to think all possible combination. because we have to find out the one can easily solve it if he has strong foundation of backtracking algorithm its the geeks way to solve . although it can also be solve by trying all possible combinatios thats the normal way

start by putting queen at all position where i=j e.g. 1,1, 2,2 3,3, & so on
so then we have 8 queens like It can also be keeping one at diagonal (0,0) (1,1) (2,2) (3,3) (4,4) (5,5) (6,6) (7,7)

can we do better ..??

as we know This problem has more than one solutions. I found one with 6 queens placed at (0,0), (1,7), (2,1), (3,4), (4,2), (6, 3) now if we rotate the chess board then we can get other solution so in this case we need 6 queen can we do still do better..?? think again

it requires much deep thinking then i was able to come up with two more solution that requires 5 queens & i think that are minimum number of queens we are looking for ...

1st (1,1) (3,4) (3,6) (4,2) (5,5)
2nd (0,0) (1,7) (2,4) (4,0), (7,6)

Queen Needed 5

Feel Free to Update & Optimize Th Solution

No comments: