Watch 25 logical GPU cores expand only feasible knight moves, discard dead ends, synchronize at each depth and discover every complete open tour on a 5×5 board.
| Depth | Frontier | Expanded | Generated | Dead ends | Duplicates |
|---|
A worker does not test all 16 board positions. It reads one state and enumerates only set bits in the precomputed legal-move mask. Core v owns board square v and its inbox contains every frontier state whose endpoint is v. It sends each legal child state directly to the destination-square core.
source = endpointCore
available = KNIGHT[source] & ~visited
while (available) {
next = popLeastBit(available)
emit(visited | bit(next), next)
}If a partial path has no feasible move before it visits all 16 squares, that branch cannot become a tour and is discarded immediately. This is exact pruning, not a heuristic guess.
if (depth < 24 && available == 0)
discard(state)
else
write(nextFrontier)PBFS completes every state at depth d before processing depth d+1. At depth 24 it enumerates every complete open tour. No closed-tour test is needed: an odd 25-vertex bipartite knight graph cannot contain a Hamiltonian cycle.
expand(frontier[d]) in parallel prefix-sum child counts barrier() frontier[d + 1] = children