Incorrect n-Queens Constraints?
Nobody has claimed this yet.
Assessment
- Difficulty
- 2/5
- Estimated time
- 1-3 hours
- Newbie friendliness
- 35/100
Research direction
Start with benchmarks/queens-pulp.py and reproduce the 4x4 n-Queens solve described in the issue. Inspect the diagonal constraint ranges, then rerun the example to verify that no returned solution places queens on a shared diagonal; done means the invalid arrangement is excluded.
Written by the indexing model from the issue text.
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 --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
Additional context
I was looking for a PuLP n-Queens problem to test my SMT solvers backend.
- Dominant language
- Linear Programming
- Stars
- 605
- Forks
- 108
- Avg merge
- 1d 22m
- Merged PRs (30d)
- 1
Getting set up
This project ships no dev container, Dockerfile or contributing guide, so setting up is up to you: start from its README, and see our first-contribution guide for the general steps.
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from coin-or/python-mip
-
Difficulty 3/5 1-2 days Newbie friendliness 45/100
coin-or/python-mip#426 ·
-
Difficulty 4/5 3-5 days Newbie friendliness 45/100
coin-or/python-mip#425 · 1 comment ·
-
Difficulty 4/5 3-5 days Newbie friendliness 35/100
coin-or/python-mip#423 · 5 comments · 3 reactions ·
-
Difficulty 3/5 1-2 days Newbie friendliness 55/100
coin-or/python-mip#422 · 1 comment ·
-
Difficulty 4/5 3-5 days Newbie friendliness 45/100
coin-or/python-mip#420 · 4 comments ·
All issues in coin-or/python-mip
Similar issues
-
Difficulty 2/5 1-3 hours Newbie friendliness 72/100
wormhole-foundation/wormhole#5062 ·
Maintainers usually reply within 1 day
-
needs-triage
Difficulty 2/5 1-3 hours Newbie friendliness 62/100
mattpocock/skills#1279 ·
Maintainers usually reply within 1 day
-
Difficulty 2/5 1-3 hours Newbie friendliness 65/100
uwolfer/gerrit-intellij-plugin#768 ·
Maintainers usually reply within 1 day
-
Difficulty 2/5 1-3 hours Newbie friendliness 66/100
sindresorhus/p-memoize#62 ·
-
[Bug]: Python Code Interpreter Result drops non-standard MIME types instead of collecting them into extraPossibly taken @lemonzoey claimed this today. Openbug Code Interpreter python sdk
Difficulty 2/5 1-3 hours Newbie friendliness 74/100
e2b-dev/E2B#1984 · 1 comment ·
Maintainers usually reply within 1 day