I have a problem at hand which is a variation of the N-Queen-Problem.The problem goes: Find a way to place 4 queens and 1 knight on a 8*8 chessboard, so that all blocks can be attacked by these pieces.It is OK for the pieces to attack each other.
I understand how to solve the original N-Queen-Problem using backtracking. However, I could not come up with an idea on how to reduce the number of searches in this new problem here. I hope someone could give me a hint.Thank you.
Thank you people.@vish4071 @Karoly Horvath @M Oehm I will consider using brute force and see what I get.
Use Brute Force. It should give you answer in short time.
You have 64 squares to consider and 5 pieces to put. Simply select 5 squares and put 5 pieces and see if this scenario covers all squares. This can be done in C(64,5) * 5 ways, which is ~3.8e7, which is easily computable in well under 1s on a standard machine now a days.
Also, you can reduce some computation if you put 4 queens in select 4 of 64 squares and then place the knight to cover the remaining squares only. This will take around C(64,4) * k computations, which is ~1e6.