2
$\begingroup$

I'm new to this forum, but I'm hoping this community can help me with some guidance on sharing and improving a mathematical solution that I've developed for the $n$-queens problem and $n$-queens completion problem. https://en.wikipedia.org/wiki/Eight_queens_puzzle

Historically, these two problems are considered complex, and there are two key aspects to the problem. First, there is no calculation for the number of correct solutions to the board. Second, the search algorithms currently employed tend to suffer a factorial time growth as the size of the board increases.

The algorithm I've created is able to perform the calculation directly. Additionally, the algorithm is able to search for individual board configurations and the time to find all valid solutions appears to be linearly dependent upon the number of solutions; it is not directly dependent upon the board size.

Edit: One of the comments rightly points out that the claims here might be met with some skepticism. To address that, I'm happy to run a known n-Queens Completion problem through my algorithm to see if it matches previously generated results. I can also offer the results from a randomly generated board I tested recently: N=28, Q1=221, Q2=78, Q3=594, Q4=227, Q5=1, Q6=493, Q7=528, Q8=160, Q9=686, has 2094852 non-attacking configurations and this calculation can be completed in 383 seconds. Note: since I approached this from a purely mathematical perspective, I did not attempt to use chess notation. Q5=1 represents the bottom left corner of the board. Square 28 is the top left, bottom right is 757 and 784 is top right.

I'm interested in sharing the algorithm and getting independent verification that it is functioning as well as I believe it is. What is the best way to start such a collaboration? Any guidance or advice you can share is greatly appreciated. Thanks.

Improve this question
$\endgroup$
4
  • 5
    $\begingroup$ This question is more suitable for cs.stackexchange.com $\endgroup$
    – Max Alekseyev
    Commented Apr 13, 2023 at 20:39
  • 1
    $\begingroup$ "the time to find all valid solutions appears to be linearly dependent upon the number of solutions"... Isn't the number of solutions of the order $n^n$? This depends on size of the board, and is worse than factorial in the size, isn't it? $\endgroup$
    – Nick S
    Commented Apr 14, 2023 at 17:19
  • $\begingroup$ Good question @NickS. The total number of combinations to check is generally N^2!/((N^2-N)!*N!) (4,426,165,368 when N=8). Standard mathematical techniques usually render the number of combinations to check down to N! (40320 for N=8). The number of "correct" non-attacking solutions is much smaller (92 when N=8). The performance of this algorithm appears to be linearly related to the number of correct solutions, and not directly dependent on the board size N. $\endgroup$
    – Dan S
    Commented Apr 15, 2023 at 0:13
  • 2
    $\begingroup$ The number of non-attacking configurations grows like $(n/c)^n$ for some constant $c$; see arxiv.org/abs/2107.13460. So any algorithm for finding (not counting) all solutions will not much faster than the naive one. Also, the completion problem is NP-hard (jair.org/index.php/jair/article/view/11079), so you shouldn't expect an efficient algorithm. $\endgroup$
    – Kevin
    Commented Apr 15, 2023 at 2:17

2 Answers 2

Reset to default
1
$\begingroup$

Since this is a well-studied problem, people will be a bit skeptical that you have found a significant improvement that is correct. I would try to look for someone you can contact via email and ask to share your solution and get feedback or discuss further. I would look for someone who is enthusiastic, has some time to spare, and doesn't mind if you might be wrong. A Ph.D. student who works in related algorithms problems and/or is interested in the study of games would be a good try. You can look at universities geographically near you (although that's not necessary), look for their CS or math algorithms and combinatorics research groups' webpages, and go from there.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I agree with all of your points, @Usul. I've been reaching out to various researchers individually, but I've not had much luck in making a connection. I thought it might be more effective to cast my net wider and see if anyone in one of these forums is interested in collaborating on the problem. If it helps to address the skepticism aspect, I'm more than happy to share some of my results. I'll add a line to the original post with the results of a random run. $\endgroup$
    – Dan S
    Commented Apr 14, 2023 at 23:41
0
$\begingroup$

Well, two pieces of advice.

First, about correctness: Anyone claiming a new and interesting algorithm to a nontrivial and well-studied problem is well advised to do a considerable amount of "homework" in the sense of checking and double-checking the new algorithm against any older results and algorithms that he/she can access, to see that it at least appears to be producing correct results. (Of course this is still not a proof that it is correct.) Doing an extensive amount of this "homework", and being able to demonstrate the results, increases the chances that other people might get interested.

Secondly, about speed (which is presumably the selling point of the algorithm): It is very well to say, from some first experiments, that the speed "appears" e.g. linear to the number of solutions. Where this gets interesting is when there are very few solutions and they are difficult to find. There are n-Queens Completion problems that have no solutions. Can your algorithm consistently solve them (i.e. report "no solutions") in time "linear to zero" (I guess this means constant time)? And if there are some solutions, it will still find them? That would be news indeed -- noting that the Completion problem is known to be NP-hard and #P-hard as noted in the Wikipedia article. Do study the existing literature, find what are the hard instances and see how your algorithm fares with them. Solving a few small "easy" or "random" instances in "apparently" linear time might not convince people enough to get interested.

After that general advice, I concur with usul's suggestions.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .