1
\$\begingroup\$

Here's one generalized version of the famous Eight Queen's Puzzle:

Given an n × n chess board, and an integer m (≤ n). Find all possible ways to put nm Queens such that

  • there are m Queens at each row
  • there are m Queens at each column

(note that we do not impose any restriction on the diagonals).


As you might see, it is possible, e.g. [1 denotes a Queen]:

n = 3, m = 2

1   1   0
0   1   1
1   0   1

n = 15, m = 2

0   0   0   0   0   0   1   0   0   1   0   0   0   0   0
0   0   0   0   0   0   1   0   1   0   0   0   0   0   0
0   0   1   0   0   0   0   0   0   0   0   0   0   1   0
1   0   0   0   0   0   0   0   0   0   0   0   0   1   0
1   0   1   0   0   0   0   0   0   0   0   0   0   0   0
0   1   0   0   0   0   0   0   0   1   0   0   0   0   0
0   0   0   1   0   0   0   0   0   0   0   0   0   0   1
0   0   0   1   0   1   0   0   0   0   0   0   0   0   0
0   1   0   0   0   0   0   1   0   0   0   0   0   0   0
0   0   0   0   0   0   0   1   1   0   0   0   0   0   0
0   0   0   0   1   0   0   0   0   0   0   1   0   0   0
0   0   0   0   1   0   0   0   0   0   0   0   0   0   1
0   0   0   0   0   1   0   0   0   0   0   1   0   0   0
0   0   0   0   0   0   0   0   0   0   1   0   1   0   0
0   0   0   0   0   0   0   0   0   0   1   0   1   0   0

Input: n, m

Output: Number of solutions

Winning Criteria: Single thread, Fastest [I will test with n = 15, m = 8 in my computer]

Optional: Print all solutions (as in the format given in examples)

Preferred Language: Python 2.7, Julia

Good luck!

\$\endgroup\$

closed as unclear what you're asking by mbomb007, Blue, Mego, betseg, AdmBorkBork Feb 13 '17 at 17:39

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ Back of the envelope suggests about 10^50 solutions for n = 15, m = 8. \$\endgroup\$ – xnor Feb 13 '17 at 17:36
  • 1
    \$\begingroup\$ This is the third time today I've run into this problem. The world is a funny place. \$\endgroup\$ – beaker Feb 13 '17 at 23:21
  • \$\begingroup\$ @xnor, it's 649920606971625785993833472182540933121831448000. Pretty good estimate. \$\endgroup\$ – Peter Taylor Feb 14 '17 at 8:41
  • 1
    \$\begingroup\$ I find it quite distracting to call this a generalisation of the eight queens problem. It would make slightly more sense to call it a generalisation of the eight rooks problem, but the literature (A008300 and see refs.) seems to describe the problem principally in terms of 0-1 matrices. It's clear that printing all solutions is a non-goer for all but some very small inputs, so I would remove that suggestion. \$\endgroup\$ – Peter Taylor Feb 14 '17 at 8:47