1
2
Here's one generalized version of the famous Eight Queen's Puzzle:
Given an
n×nchess board, and an integerm(≤n). Find all possible ways to putnmQueens such that
- there are
mQueens at each row- there are
mQueens 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!
xxx---
Posted 2017-02-13T17:08:36.153
Reputation: 157
Back of the envelope suggests about
10^50solutions forn = 15, m = 8. – xnor – 2017-02-13T17:36:32.5871This is the third time today I've run into this problem. The world is a funny place. – beaker – 2017-02-13T23:21:15.020
@xnor, it's 649920606971625785993833472182540933121831448000. Pretty good estimate. – Peter Taylor – 2017-02-14T08:41:05.313
1
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.
– Peter Taylor – 2017-02-14T08:47:05.010