CODEWITHSUNDEEP
algorithmbacktrackingn-queens
antande
antande

Reputation: 169

4 Queens and 1 Knight to attack all blocks on a 8*8 board

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.

Upvotes: 2

Views: 305

Answers (2)

vish4071
vish4071

Reputation: 5277

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.

Upvotes: 3

Karoly Horvath
Karoly Horvath

Reputation: 96266

I don't think a naive algorithm needs any kind of optimization as it's probably going to be fast anyways... but, here it is:

You can always restrict the first move to one of the quarters (e.g.: upper left), since the rest of the solutions can be generated from that by mirroring or rotating.

You can count the covered places, and there's a limit how much one piece can cover (22 for a queen and 9 for a king), so you can use that as a rule for early terminating a hopeless branch.

Note: since you have only 4 queens, putting 2 in the same row or column is probably a bad idea. You can try that as a restriction.

Upvotes: 0

Related Questions