Computing tighter bounds on the n-queens constant via Newton's method

DOI10.1007/S11590-022-01933-2MaRDI QIDQ6097488zbMATH OpenFDO

Authors Parth Nobel, Akshay Agrawal, Stephen Boyd

Publication date 5 June 2023

Published in Optimization Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2112.03336

zbMATH Keywords

combinatorial optimizationconvex optimizationNewton's method\(n\)-queens constant

Mathematics Subject Classification ID

Convex programming (90C25) Combinatorial optimization (90C27)

Abstract: In recent work Simkin shows that bounds on an exponent occurring in the famous $n$-queens problem can be evaluated by solving convex optimization problems, allowing him to find bounds far tighter than previously known. In this note we use Simkin's formulation, a sharper bound developed by Knuth, and a Newton method that scales to large problem instances, to find even sharper bounds.

Recommendations

• The number of \(n\)-queens configurations
• A dynamic programming solution to the n-queens problem
• scientific article; zbMATH DE number 2190096
• scientific article; zbMATH DE number 1743978
• scientific article; zbMATH DE number 436080

Cites work

• scientific article; zbMATH DE number 1953444 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• scientific article; zbMATH DE number 5060482 (Why is no real title available?)
• A survey of known results and research areas for \(n\)-queens
• Introduction to applied linear algebra. Vectors, matrices, and least squares
• Methods of conjugate gradients for solving linear systems
• On the threshold problem for Latin boxes
• Solution of Sparse Indefinite Systems of Linear Equations

Describes a project that uses

Uses Software

• SageMath

This page was built for publication: Computing tighter bounds on the \(n\)-queens constant via Newton's method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6097488)