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

DOI10.1007/S11590-022-01933-2zbMATH Open1519.90208arXiv2112.03336MaRDI QIDQ6097488FDOQ6097488

Authors: Parth Nobel, Akshay Agrawal, Stephen Boyd 

Publication date: 5 June 2023

Published in: Optimization Letters (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Methods of conjugate gradients for solving linear systems
• Title not available (Why is that?)
• Solution of Sparse Indefinite Systems of Linear Equations
• A survey of known results and research areas for \(n\)-queens
• Introduction to applied linear algebra. Vectors, matrices, and least squares
• On the threshold problem for Latin boxes

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)