Solving problems with others not only reduces the time required to complete a challenge but may also enable the discovery of novel strategies that qualitatively change how a problem is approached. At the dyadic level, the laboratory-based ‘shepherding task’ demonstrated that, when tasked to contain evasive agents to a centralized location, some participants discover a non-obvious but optimal strategy to solve the task. This paper quantified the interactions between participants engaged in the task using Multidimensional Cross-Recurrence Quantification Analysis (MdCRQA), applied to each participant’s gaze and hand movements. The results demonstrated that strategy discoverers exhibited greater amounts of incidental coupling than non-discoverers prior to discovery. Once discovered, the strategy reduced the strength of coupling between participants, indicating that the strategy also reduced coordination demands. Future work will investigate whether differences in problem-solving can be attributable to differences in the perceptual features participants use which scaffold the discovery of task-optimal solutions.