Simultaneously solve N-queens and no-3-in-line

Question

An intriguing MathsSE question asked if there were large N-queens solutions where no three queens lie on a line. That question's body included the unique ×ばつ4 solution up to symmetries

. Q . .
. . . Q
Q . . .
. . Q .

and noted that there are no solutions for ×ばつ5 to ×ばつ7 because of knight lines. However, joriki over there then wrote some code and found solutions from ×ばつ8 to ×ばつ16, counting all of them in the process: $$\begin{array}{c|cc} N&4&5&6&7&8&9&10&11&12&13&14&15&16\\\hline \text{up to symmetries}&1&0&0&0&1&4&5&12&53&174&555&2344&8968\\ \text{all}&2&0&0&0&8&32&40&96&410&1392&4416&18752&71486 \end{array}$$ I find these restricted solutions quite interesting. Here is a ×ばつ40 solution:

. . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . .
Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . .
. . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . .
. . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . .
. . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . .
. . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . .
. . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . .
. . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q .
. . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . .
. . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q
. . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . .
. . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . .
. . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . .
. . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . .

But my formulation of the problem as an integer linear program takes some time. I'd like to see results faster.

Task

Write the fastest-code that when given an integer \$N\ge8\$ (handling lesser numbers is optional) outputs any \$N\$-queens solution that also has the no-3-in-line property. Although it is not proven that solutions exist for all \$N\ge8\$, your code may assume that they do.

The code will be run on my Lenovo ThinkPad E14 Gen 2 laptop with an 8-core Intel Core i7 processor running Ubuntu 22.10. A program's score is the highest \$N\$ for which a solution is returned in 2 minutes. You may output in any reasonable format, including graphical formats as above and as a list with the queen indices for each row (the above solution corresponds to the 0-indexed list [10, 21, 28, 0, 7, 12, 15, 36, 29, 17, 6, 34, 13, 35, 18, 5, 22, 11, 1, 8, 32, 38, 14, 37, 26, 30, 39, 2, 16, 24, 3, 31, 25, 9, 20, 33, 27, 4, 23, 19]).

I encourage you to post the results for your code on your own machine for my reference.

• Arnauld: Should our code be deterministic?
• Parcly Taxel: @Arnauld There's no restriction – see what works for you – unlike the other one.

Answer 1

MiniZinc, N = 70

int: n;
array [1..n] of var 1..n: q;
predicate 
 noattack(int: i, int: j, var int: qi, var int: qj) =
 qi != qj /\
 qi + i != qj + j /\
 qi - i != qj - j;
constraint
 forall (i in 1..n, j in i+1..n) (
 noattack(i, j, q[i], q[j])
 );
predicate
 no3inline(int: i, int: j, int: k, var int: qi, var int: qj, var int: qk) =
 i * (qk - qj) + j * (qi - qk) + k * (qj - qi) != 0;
constraint
 forall (i in 1..n, j in i+1..n, k in j+1..n) (
 no3inline(i, j, k, q[i], q[j], q[k])
 );
solve :: int_search(q, first_fail, indomain_random)
 satisfy;

Adapted from https://github.com/MiniZinc/minizinc-benchmarks/blob/master/queens/queens.mzn.

Solution for \$N = 70\$ in less than 9s on i5-6300U.

It is worth noting that the time required does not always increase when increasing \$N\$. For example, for \$N = 69\$, 2 minutes were not enough.

---

The goal of this answer is not to show off my skills, but the power of MiniZinc and constraint programming in general.

• Jonah: How does this compare to Prolog?
• matteo_c: @Jonah I've never used standard Prolog, but besides minizinc I'm familiar with 'Answer set programming' (ASP), which is roughly a superset of Prolog. From my personal experience, sometimes it is easier to model a problem in minizinc, sometimes in ASP. Sometimes you get a faster solution using minizinc, sometimes using an ASP solver.

Answer 2

Python 3 (PyPy), N = 565

import math
import random
import multiprocessing
import itertools
import argparse
def line(x0, y0, x1, y1):
 a = y0 - y1
 b = x1 - x0
 gcd = math.gcd(a, b)
 a //= gcd
 b //= gcd
 if a < 0:
 return -a, -b
 elif a == 0:
 if b < 0:
 return 0, -b
 return 0, b
 return a, b
def num_conflicts(l, x, y):
 lines = {(1,1),(1,-1),(1,0),(0,1)}
 n = 0
 for x1, y1 in enumerate(l):
 if x1 == x: continue
 l1 = line(x, y, x1, y1)
 if l1 in lines:
 n += 1
 else:
 lines.add(l1)
 return n
def greedy(n):
 l = []
 for x in range(n):
 z = [num_conflicts(l, x, y) for y in range(n)]
 v = min(z)
 y = random.choice([y for y, k in enumerate(z) if k == v])
 l.append(y)
 return l
def fix_row(n, l, x):
 y0 = l[x]
 nc = num_conflicts(l, x, y0)
 if nc == 0: return 1
 z = [num_conflicts(l, x, y) if y != y0 else nc for y in range(n)]
 v = min(z)
 options = [y for y, k in enumerate(z) if k == v]
 if options == [y0]: return -1
 y = random.choice(options)
 l[x] = y
def solve(t):
 s, n = t
 random.seed(s)
 l = greedy(n)
 for i in range(3*n):
 outcomes = {fix_row(n, l, x) for x in range(n)}
 if outcomes == {1}:
 return l
 if None not in outcomes:
 break
def full(n):
 return next(filter(None, map(solve, enumerate(itertools.repeat(n)))))
def full_mp(n, p):
 with multiprocessing.Pool(p) as p:
 return next(filter(None, p.imap_unordered(solve, enumerate(itertools.repeat(n)))))
def main():
 parser = argparse.ArgumentParser(
 prog = "queensthree",
 description = "Finds solution for the no-three-in-a-line n-queens problem"
 )
 parser.add_argument('n', help='number of rows/columns', type=int)
 parser.add_argument('-j', default=1, help='number of processes to use (defaults to 1)', type=int)
 args = parser.parse_args()
 if args.j > 1:
 l = full_mp(args.n, args.j)
 else:
 l = full(args.n)
 print(all(num_conflicts(l, x, l[x]) == 0 for x in range(args.n)))
 print(l)
if __name__ == '__main__':
 main()

Try it online! (N=327)

Uses the Min-conflicts algorithm. The gist of the algorithm is to start with a random arrangement of the queens, and repeat the step of choosing a random queen that is in conflict (in check or in a line with two other queens), and move it to a square in the same row with the least conflicts. After a number of steps, if a solution hasn't been found, start over with a different random arrangement.

Because of how the algorithm works, it occasionally gets lucky and finds a solution on the first try (which is what happened with N=565, the previous solution that could be found in 2 minutes was for N=532).

Answer 3

Wolfram Language (Mathematica), N=20

N=20 in less than a min on my old laptop

queens=20;
put[n_,m_,q_]:=(pl={n,m};s[[n,m]]="X";{i,j}=pl;
While[i>1&&j>1,i--;j--;s[[i,j]]++];
{i,j}=pl;
While[i<q&&j<q,i++;j++;s[[i,j]]++];
{i,j}=pl;
While[i<q&&j>1,i++;j--;s[[i,j]]++];
{i,j}=pl;
While[i>1&&j<q,i--;j++;s[[i,j]]++];
{i,j}=pl;
While[i<q,i++;s[[i,j]]++];
{i,j}=pl;
While[i>1,i--;s[[i,j]]++];
{i,j}=pl;
While[j<q,j++;s[[i,j]]++];
{i,j}=pl;
While[j>1,j--;s[[i,j]]++];)
While[(t=0;
qu=queens;
While[t!=qu,s=Table[0,{i,qu},{j,qu}];
put[RandomInteger[{1,qu}],RandomInteger[{1,qu}],qu];
t=1;
While[!FreeQ[s,0],
pos=Position[s,0];
put[First@#,Last@#,qu]&[RandomChoice@pos];t++];];
posi=Position[s,"X"];
Select[(Last@#/First@#&[First@Differences[#]])&/@#&/@(Partition[#,2,1]&/@Subsets[posi,{3}]),SameQ@@#&])!={}]
s=s/. a_/;IntegerQ@a:>".";

Try it online!

Answer 4

Rust, N=128

Adapted from @gsitcia's answer

Try it online!(N=128)

use std::collections::HashSet;
// use std::env;
use std::iter;
use std::sync::mpsc;
use std::thread;
use rand::rngs::StdRng;
fn gcd(a: i32, b: i32) -> i32 {
 if b == 0 {
 a.abs()
 } else {
 gcd(b, a % b)
 }
}
fn line(x0: usize, y0: usize, x1: usize, y1: usize) -> (i32, i32) {
 let mut a = (y0 as i32) - (y1 as i32);
 let mut b = (x1 as i32) - (x0 as i32);
 let gcd_val = gcd(a, b);
 a /= gcd_val;
 b /= gcd_val;
 if a < 0 {
 (-a, -b)
 } else if a == 0 {
 if b < 0 {
 (0, -b)
 } else {
 (0, b)
 }
 } else {
 (a, b)
 }
}
fn num_conflicts(l: &[usize], x: usize, y: usize) -> usize {
 let mut lines = HashSet::new();
 let mut n = 0;
 for (x1, &y1) in l.iter().enumerate() {
 if x1 == x {
 continue;
 }
 let l1 = line(x, y, x1, y1);
 if lines.contains(&l1) {
 n += 1;
 } else {
 lines.insert(l1);
 }
 }
 n
}
fn greedy(n: usize) -> Vec<usize> {
 let mut l = Vec::with_capacity(n);
 for x in 0..n {
 let z: Vec<usize> = (0..n).map(|y| num_conflicts(&l, x, y)).collect();
 let v = *z.iter().min().unwrap();
 let options: Vec<usize> = z
 .iter()
 .enumerate()
 .filter_map(|(y, &k)| if k == v { Some(y) } else { None })
 .collect();
 let y = options[rand::random::<usize>() % options.len()];
 l.push(y);
 }
 l
}
fn fix_row(n: usize, l: &mut [usize], x: usize) -> Option<bool> {
 let y0 = l[x];
 let nc = num_conflicts(l, x, y0);
 if nc == 0 {
 return Some(true);
 }
 let z: Vec<usize> = (0..n).map(|y| if y != y0 { num_conflicts(l, x, y) } else { nc }).collect();
 let v = *z.iter().min().unwrap();
 let options: Vec<usize> = z.iter().enumerate().filter_map(|(y, &k)| if k == v { Some(y) } else { None }).collect();
 if options == [y0] {
 return Some(false);
 }
 let y = options[rand::random::<usize>() % options.len()];
 l[x] = y;
 None
}
fn solve(t: (usize, usize)) -> Option<Vec<usize>> {
 let (s, n) = t;
 let _rng: StdRng = rand::SeedableRng::seed_from_u64(s as u64);
 let mut l = greedy(n);
 for _ in 0..3 * n {
 let outcomes: HashSet<Option<bool>> = (0..n).map(|x| fix_row(n, &mut l, x)).collect();
 let all_true = outcomes.iter().all(|outcome| outcome == &Some(true));
 if all_true {
 return Some(l);
 }
 if !outcomes.contains(&None) {
 break;
 }
 }
 None
}
fn full(n: usize) -> Vec<usize> {
 iter::repeat(n)
 .enumerate()
 .filter_map(solve)
 .next()
 .unwrap()
}
fn full_mp(n: usize, p: usize) -> Vec<usize> {
 let (tx, rx) = mpsc::channel();
 let tasks = iter::repeat(n).take(p).enumerate();
 for task in tasks {
 let tx = tx.clone();
 thread::spawn(move || {
 let result = solve(task);
 if let Some(solution) = result {
 tx.send(solution).unwrap();
 }
 });
 }
 rx.recv().unwrap()
}
fn main() {
 // let args: Vec<String> = env::args().collect();
 // if args.len() < 2 {
 // eprintln!("Usage: {} n [-j processes]", args[0]);
 // std::process::exit(1);
 // }
 // let n: usize = args[1].parse().expect("n must be an integer");
 // let processes: usize = if args.len() >= 4 && args[2] == "-j" {
 // args[3].parse().expect("processes must be an integer")
 // } else {
 // 1
 // };
 
 let n: usize = 128;
 let processes: usize =1;
 let l = if processes > 1 {
 full_mp(n, processes)
 } else {
 full(n)
 };
 println!(
 "{}",
 l.iter()
 .enumerate()
 .all(|(x, &y)| num_conflicts(&l, x, y) == 0)
 );
 println!("{:?}", l);
}

Answer 5

Python, with Z3Py

# !pip install z3-solver
from z3 import *
# Set the value of n
n = Int('n') # Or you can set a specific value, e.g., n = 8
n_value = 8 # Example with n = 8
# Create an array q[1..n] of integer variables ranging from 1 to n
q = [Int('q_%i' % i) for i in range(1, n_value + 1)]
# Initialize the solver
s = Solver()
# Add constraints that each q[i] is between 1 and n
for i in range(n_value):
 s.add(q[i] >= 1, q[i] <= n_value)
# Define the noattack predicate constraints
for i in range(1, n_value + 1):
 for j in range(i + 1, n_value + 1):
 qi = q[i - 1]
 qj = q[j - 1]
 s.add(qi != qj) # Not in the same row
 s.add(qi + i != qj + j) # Not in the same major diagonal
 s.add(qi - i != qj - j) # Not in the same minor diagonal
# Define the no3inline predicate constraints
for i in range(1, n_value + 1):
 for j in range(i + 1, n_value + 1):
 for k in range(j + 1, n_value + 1):
 qi = q[i - 1]
 qj = q[j - 1]
 qk = q[k - 1]
 s.add(i * (qk - qj) + j * (qi - qk) + k * (qj - qi) != 0)
# Solve the constraints
if s.check() == sat:
 m = s.model()
 solution = [m.evaluate(q[i]) for i in range(n_value)]
 print("Solution:", solution)
else:
 print("No solution found.")