CODEWITHSUNDEEP
algorithmrecursionchessbacktrackingn-queens
NedStarkOfWinterfell
NedStarkOfWinterfell

Reputation: 5173

Variant of N-Queens algorithm

I don't know whether this problem has been studied or not, it just came to my mind while trying out the general N-Queens problem. Given a N*N chessboard , what is the minimum number of Queens required, which, when placed strategically, renders all cells under attack by at least one of the queens.

I tried it with pen and paper for N = 3,4,5, I got 2,3,4. So is the answer always N-1? Is there a proof for it? And secondly, if so, how to print out that configuration (if more than 1 configuration is possible, print them all)?

Upvotes: 2

Views: 1632

Answers (2)

Gunther Piez
Gunther Piez

Reputation: 30449

The problem has been studied and the minimum number at which k queens cover an nxn grid is known as the domination number.

The k for the first n are

1, 1, 1, 2, 3, 3, 4, 5, 5, 5, 5, 6, 7, 8, 9, 9, 9, 9

as given by OEIS. This means for an 8x8 board 5 queens are sufficient.

It has been conjectured that for all n which satisfy n=4m+1 (such as 5,9,13...) 2m+1 queens are sufficient. This and lot more advanced algorithms are presented in Matthew D. Kearse and Peter B. Gibbons, "Computational Methods and New Results for Chessboard Problems"

Upvotes: 3

j_random_hacker
j_random_hacker

Reputation: 51226

Well, it's not N-2, because an 11x11 grid requires at most 8 queens (and possibly fewer -- this is just an example I found by hand):

11x11 grid covered by 8 queens

Upvotes: 2

Related Questions