coin-or / coin-or/python-mip

Incorrect n-Queens Constraints?

Open
#344 1 comment 0 reactions 0 assignees View on GitHub
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.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.