About the problem

Update (2026-07-31): We have removed this problem from the benchmark because we determined that the verifier would not detect correct solutions with high enough fidelity.

The unknotting number of a knot is a classic invariant. It is defined as the smallest number of crossing changes required to change a diagram of the knot into a diagram of the unknot. This problem is to devise an algorithm that decides whether a diagram depicts a knot with unknotting number one.

This problem is one of the fundamental questions in low-dimensional topology and a solution would be a major result. The problem sits at an interesting point in terms of complexity: while there are algorithms for determining if the unknotting number of a knot is zero, the general problem of determining the unknotting number of a knot is not even known to be decidable. The problem author is optimistic that the case of unknotting number equal to one is at least decidable, and even computationally manageable for diagrams of moderate size.

Rather than attempt full theoretical verification, we test proposed algorithms on a hidden challenge set of knots with known unknotting numbers. While we hope that perfect performance on this challenge set would be indicative of a conceptual breakthrough, it is possible that an AI system will throw together many ad hoc approaches and succeed. If so, we may repair the problem by generating still more challenging examples.

Read more here.

Prompt

Produce an algorithm that takes a diagram of a knot and returns True exactly when the knot has
unknotting number 1. Submit one Python file defining:

    def solution(pd_code: list[list[int]]) -> bool

The input is a 1-indexed planar diagram (PD) code. Your function must return a built-in bool. The
submission may import packages installed in the sandbox.

The verifier imports your file once and tests 300 diagrams with at most 100 crossings. Each diagram
is a knot with unknotting number 0, 1, or 2. All 300 diagrams must be classified correctly within a
total of 1 hour.

Example input:
[[4,2,5,1],[10,6,11,5],[8,3,9,4],[2,9,3,10],[11,16,12,17],[7,15,8,14],
[15,7,16,6],[13,20,14,21],[17,22,18,1],[21,18,22,19],[19,12,20,13]]