You are trying to solve the famous N queens problem. You broke one of the queens from your chess pieces collections. Now, you have created the following puzzle:

You are given an N*N chessboard. Is it possible to place N-1 queens on it in such a way that no pair of queens is attacking each other?

Two queens are attacking each other if at least one of the following conditions is true:

They share the same row They share the same column They share the same diagonal You are given a single integer N. Print any possible configuration in the format below. It is guaranteed that there is always an answer

for example N=4. one of the possible answer is

* . . .
. . * .
. . . .
. * . .
  • 2
    $\begingroup$ Of course N-1 queens are possible: just pick a solution of N queens then remove one of them. $\endgroup$ – athin May 2 at 5:33
  • $\begingroup$ @athin but how to print that pattern $\endgroup$ – sukesh May 2 at 5:33
  • 2
    $\begingroup$ Printing patterns makes me wonder.. Is it from a programming contest, in some sense? $\endgroup$ – athin May 2 at 5:42
  • 1
    $\begingroup$ In that case, could you give first which contest does this come from? Otherwise the question might be closed as a result of not having a proper attribution. I also want to help, but if this is from an on-going competition then we need to wait until it's over too. $\endgroup$ – athin May 2 at 5:48
  • 4
    $\begingroup$ If you need help with constructing a program to solve this problem, then it would be better to ask on a programming site, not on a puzzle site. You can find many programs for the standard N-queens problem very easily. Once you understand how those programs work, try to adapt one them to this problem. $\endgroup$ – Jaap Scherphuis May 2 at 7:22

Note that the $N$ queens problem is always solvable except for $N=2$ and $3$, so by removing any queen from the solution we get a valid $N-1$ queens solution. For $N=2$, it's trivial to place $2-1=1$ queen into any square. For $N=3$, it's sufficient to place $3-1=2$ queens at a distance of a knight's move, so they would not attack each other.

| improve this answer | |
  • $\begingroup$ can u help me how to print patterns $\endgroup$ – sukesh May 2 at 5:47
  • 1
    $\begingroup$ @trolley813 Note that your solution method is not necessarily reversible, so there will usually also be solutions to the N-1 queens problem that cannot be generated in this way. The 4x4 example in the problem statement is one example. $\endgroup$ – Jaap Scherphuis May 2 at 7:35
  • $\begingroup$ Yes, you're right. It's sufficient but not necessary to build a full N-queen solution, there are positions with N-1 queens where it's impossible to add the Nth queen. $\endgroup$ – trolley813 May 2 at 7:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.