Incorrect n-Queens Constraints?
- Dominant language
- Linear Programming
- Stars
- 600
- Forks
- 108
- PR merge metrics
- No merged PRs in 30d
Description
**Describe the bug**
I was able to get the solution
[[0 0 Q 0]
[0 Q 0 0]
[0 0 0 Q]
[Q 0 0 0]]
For a 4x4 4-Queens problem. I believe this is because the "diagonal /" constraints are slightly off.
I believe the correct code is
```diff
diff --git a/benchmarks/queens-pulp.py b/benchmarks/queens-pulp.py
index 0768dbf..f6d5323 100644
--- a/benchmarks/queens-pulp.py
+++ b/benchmarks/queens-pulp.py
@@ -45,7 +45,7 @@ def gen_model(n):
if i - j == k) <= 1, 'diag1({})'.format(p)
# diagonal /
- for p, k in enumerate(range(3, n + n)):
+ for p, k in enumerate(range(1, n + n - 2)):
queens += lpSum(x[i][j] for i in range(n) for j in range(n)
if i + j == k) <= 1, 'diag2({})'.format(p)
```
At least, this seemed to produce correct solutions to me.
**To Reproduce**
Solve the n-Queens problem with PuLP and the example will be present in the solutions.
**Expected behavior**
I was expecting no queens to share diagonals, like
[[0 Q 0 0]
[0 0 0 Q]
[Q 0 0 0]
[0 0 Q 0]]
**Desktop (please complete the following information):**
- Operating System, version: Ubuntu 22.04
- Python version: Python 3.9
- Python-MIP version (we recommend you to test with the latest version): Latest commit [6044fc8](https://github.com/coin-or/python-mip/commit/6044fc8f0414d71430e94b8a08573b695dc35b5a)
**Additional context**
I was looking for a PuLP n-Queens problem to test my SMT solvers backend.
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.