An efficient SAT encoding for solving The Social Golfer Problem

VNU University of Engineering and Technology, Hanoi, Vietnam

^* Corresponding author: This email address is being protected from spambots. You need JavaScript enabled to view it.

Received: 5 April 2025
Accepted: 28 November 2025

Abstract

The Social Golfer Problem (SGP), a classic NP-complete combinatorial optimization chal- lenge, poses significant scalability issues for automated solvers. To address these limitations, this paper introduces a novel and efficient SAT encoding, the New SAT Encoding (NSE). NSE employs a com- pact three-index variable representation and integrates the New Sequential Counter (NSC) encoding, the proposed technique for Exactly K cardinality constraints, specifically for the SGP’s Group Size constraint. Rigorous experimental evaluation against established encodings, including Triska–Musliu Encoding and Set Constraint Encoding, demonstrates NSE’s superior robustness and performance. Notably, NSE solves a larger number of SGP instances, including the previously intractable 6–3–8 benchmark, outperforming existing SAT-based approaches. While NSE may exhibit a slightly larger clause count in certain configurations, its significantly reduced variable count and solver-friendly CNF structure, enabled by NSC, facilitate enhanced constraint propagation and search efficiency. These results highlight the effectiveness of the NSE encoding and the NSC technique, advancing the state-of- the-art SAT-based solutions for complex combinatorial problems like the Social Golfer Problem.