  The quantum backtracking algorithm proposed by Ashley Montanaro raised
considerable interest, as it provides a quantum speed-up for a large class of
classical optimization algorithms. It does not suffer from Barren-Plateaus and
transfers well into the fault-tolerant era, as it requires only a limited
number of arbitrary angle gates. Despite its potential, the algorithm has seen
limited implementation efforts, presumably due to its abstract formulation. In
this work, we provide a detailed instruction on implementing the quantum step
operator for arbitrary backtracking instances. For a single controlled diffuser
of a binary backtracking tree with depth n, our implementation requires only
$6n+14$ CX gates. We detail the process of constructing accept and reject
oracles for Sudoku problems using our interface to quantum backtracking. The
presented code is written using Qrisp, a high-level quantum programming
language, making it executable on most current physical backends and
simulators. Subsequently, we perform several simulator based experiments and
demonstrate solving 4x4 Sudoku instances with up to 9 empty fields. This is, to
the best of our knowledge, the first instance of a compilable implementation of
this generality, marking a significant and exciting step forward in quantum
software engineering.
