DIFFICULTY:
MODERATE
PREREQUISITES: Data Structure, Backtracking Algorithm
PROBLEM: CodeChef: Practical coding for everyone
Author: Sumanta Chakraborty
EXPLANATION:
Input:
(1,1)
(2,2)
(3,3)
(4,3)
Output:
Invalid
Queen 4
2
Hence, for the above input the 1st queen has been placed at the 1st row, the 2nd queen has been placed at the 2nd row, the 3rd queen has been placed at the 3rd row and the 4th queen has been placed at the 4th row. Also, the column position of each queen is in the range between 1 and 4 (inclusive). Hence, the 1st queen’s cell position is valid.
Now, the 2nd queen is placed in the same diagonal with the 1st queen. Hence, the 2nd queen’s cell position is valid.
The the 3rd queen is placed in the same diagonal with the 1st queen and in the same diagonal with the 2nd queen. So, the 3rd queen’s cell position is valid.
Now, the 4th queen is neither in the same column or in the same diagonal with the 1st queen. So, the 4th queen’s cell position is not valid. Therefore, the output will display ‘Invalid’.
Since the placement is invalid, the output displays ‘Queen 4’ which is the 1st wrongly placed queen which is detected to be at the wrong cell position, starting from the 1st cell position.
Also, since the placement is invalid, Prof. Mondal has imposed new criteria. According to the new criteria, there are 2 sets of intermediate cell positions possible between the 1st and the 4th cell positions. One set of intermediate cell positions between the 1st and the 4th cell positions is {(2,2), (3,4)} for the 2nd and the 3rd queens, respectively because in such moves no two queens have been placed in the same row or in the same column. Similarly, another set of intermediate cell positions between the 1st and the 4th cell positions is {(2,4), (3,2)} for the 2nd and the 3rd queens, respectively.
Test Cases:
1
Input :
(1,1)
(2,2)
(3,3)
(4,3)
Output:
Invalid
Queen 4
2
2
Input :
(2,1)
(3,2)
(4,3)
(1,3)
Output:
Invalid
Queen 1
0
3
Input :
(1,9)
(2,1)
(3,1)
(4,1)
Output:
Invalid
Queen 1
0
4
Input :
(1,1)
(2,2)
(3,3)
(4,4)
Output:
Valid
5
Input :
(1,4)
(2,3)
(3,1)
(4,1)
Output:
Invalid
Queen 3
2
6
Input :
(1,4)
(2,3)
(3,2)
(4,1)
Output:
Valid
7
Input :
(1,1)
(2,2)
(3,1)
(4,3)
Output:
Invalid
Queen 4
2