Beyond N-Queens: Simple Problems That Remain Difficult to Solve

[hariz91]

TL;DR

N-Queens is simple to state but difficult to solve. Are there similar problems? Does difficulty mean failure? Is a shortcut possible? What about P vs NP? Complexity grows with each added detail.

Is there any other problem as simple as placing queens on an N×N board?. Does admitting to difficulties in finding a solution count as failure? Is the idea of a shortcut dismissed by the majority, or is it still considered possible? If there is no shortcut, why does it involve calculations at all? Is it true that an efficient solution to N-Queens would affect global security systems — or is that only if P = NP is proven? Or is it merely a variation of patterns?

Consider these situations — which seems easier?

1. A pile of hay.
2. A pile of hay with a bead inside.
3. A pile of hay with a golden bead inside.
4. A pile of hay with a golden bead inside, at the very bottom.

Each added detail increases complexity — much like increasing N in N-Queens. This is not just about numbers; it also appears in how we describe problems.

 

[jedishrfu]

There are some problems that if you discover the insight then the problem is easy to solve or enumerate.

The most famous to my mind is the sum of numbers from 1 to 100. It was a problem given to Gauss’s elementary class. Gauss saw the insight and solved it far faster than anyone else in class.

Many math olympiad problems also have this same insight feature that only someone with that special skill of seeing patterns will spot.

 

[hariz91]

There are some problems that if you discover the insight then the problem is easy to solve or enumerate.

The most famous to my mind is the sum of numbers from 1 to 100. It was a problem given to Gauss’s elementary class. Gauss saw the insight and solved it far faster than anyone else in class.

Many math olympiad problems also have this same insight feature that only someone with that special skill of seeing patterns will spot.

Insight can make a problem look easy—yet N-Queens continues to test the limits of algorithmic optimization. If someone finds an elegant shortcut, it could fundamentally reshape how we approach NP-hard constraints.

 

[pbuk]

There are some problems that if you discover the insight then the problem is easy to solve or enumerate.

But the enumeration of n-Queens solutions is not one of them. It has been shown that there are approximately $(0.143 n)^n$ solutions, a number which clearly increases exponentially. If the length of time required to enumerate a solution is not zero, the length of time required to enumerate an exponentially increasing number of solutions increases exponentially.

N-Queens is simple to state but difficult to solve.

It is important to be clear about what you mean by "N-Queens". If you mean finding a single arrangement of queens that are non-attacking, this is simple (linear time) using the "staircase" approach. Finding a single solution belongs to a class of problems known as decision problems.

Enumerating all solutions belongs to a class of problems known as counting problems.

Are there similar problems?

There are many counting problems (finding all solutions) which are much harder to solve than the equivalent decision problem (finding one solution). Many of these come from graph theory; an example which is easy for the layman to understand is:

• Decision problem: "Given a map of countries and $k$ distinct colours, find a way to colour the map so that no colours share a border"
• Counting problem "Given a map of countries and $k$ distinct colours, how many different ways can the map be coloured so that no colours share a border"

Does difficulty mean failure?

No. Climbing Everest can only be achieved with difficulty, but if you reach the summit then you have not failed.

Is a shortcut possible?

For the decision problem, yes as above; for the counting problem, no.

What about P vs NP?

The decision problem is in P (as above). The terms 'P' and 'NP' do not apply to counting problems, instead we have the term '#P' (usually pronounced 'sharp p').

Is there any other problem as simple as placing queens on an N×N board?. Does admitting to difficulties in finding a solution count as failure? Is the idea of a shortcut dismissed by the majority, or is it still considered possible? If there is no shortcut, why does it involve calculations at all?

Answered above.

Is it true that an efficient solution to N-Queens would affect global security systems — or is that only if P = NP is proven? Or is it merely a variation of patterns?

No.

As described above:
Efficient solutions to the n-queens decision problem already exist: the security equivalent would be "is this the correct password?"
P = NP is not relevant (the enumeration problem is not in P or NP).

There is a class of problems related to n-queens called "n-queens completion" problems. These have been shown to be NP-complete and so if a polynomial time solution could be found this would prove P = NP which would have big implications.

I don't know anybody that believes that P = NP, however I do know a lot of people that believe that it is unlikely that P ≠ NP will be proved in their lifetime.

Consider these situations — which seems easier?

1. A pile of hay.
2. A pile of hay with a bead inside.
3. A pile of hay with a golden bead inside.
4. A pile of hay with a golden bead inside, at the very bottom.

Each added detail increases complexity

No it doesn't: it is no harder to find a golden bead than a bead of unspecified material. And finding a bead that you know is at the bottom of the pile is easier ($O(n^2)$) than searching the whole volume ($O(n^3)$).

much like increasing N in N-Queens

No, changing the nature of the problem is not like changing the value of $n$. A better analogy for piles of hay would be "a bigger pile of hay".

This is not just about numbers; it also appears in how we describe problems.

What do you mean by this?

 

[hariz91]

Thanks @pbuk for the detailed breakdown! That clearly separates the confusion between finding a single solution vs enumerating all solutions.

I see where my analogy fell short regarding the haystack example—scaling N is indeed more about expanding the search space itself rather than adding constraints to the target. Appreciate the clarification on P vs NP and how N-Queens Completion fits into NP-completeness as well!