# A Solution Algorithm for Dudley’s Hat Problem

> An algorithmic experiment for Dudley's Hat that dynamically tracks subset-sum constraints to reduce search work; the historical project record reached a value of 27.

- Author: Muhammet Ali Köker
- Language: en
- Canonical: https://alikoker.com.tr/en/dudleys-hat-solution-algorithm
- Translation: https://alikoker.com.tr/dudleys-hat
- Published: 2014-03-02T14:25:10+03:00
- Modified: 2026-08-29T18:07:00+03:00
- Type: project

This project explored an alternative search strategy for the combinatorial problem I recorded as Dudley's Hat.

Under the surviving project definition, integers are placed in three increasing arrays. A new value can be added only when it does not conflict with subset sums already possible in that array and when it is larger than the previously added value.

## The Expensive Part: Subset Sums

Testing a candidate requires knowledge of sums that can already be formed from earlier elements. Recomputing those combinations from scratch for every candidate quickly increases the search cost.

The approach I implemented tried to reuse the current state and validate candidates dynamically, reducing repeated work compared with a straightforward exhaustive search.

## Experimental Result

The archived project record reports a largest value of `21` for the manual/comparison approaches and `27` for my implementation.

The surviving project record states that the implementation reached 27 instead of 21. Because the complete historical experiment specification is unavailable, the supported statement is narrower: **the implementation reached 27 under the problem definition and conditions used in the project**.

## Search-Space Reduction vs Parallelism

Splitting a search across more threads and reducing the number of states that need to be searched are different optimizations. Parallelism can evaluate the same state space faster, while a better state representation or pruning rule can remove work entirely.

That distinction became one of the useful lessons of this project.

A related exponential-search experiment appears in my [Subset Sum Optimization](/en/subset-sum-optimization-and-parallelization) project, while [Data Structures and Algorithm Analysis](/en/data-structures-and-algorithm-analysis) provides the broader complexity context.

## Cite This Work

Köker, M. A. (2014). A Solution Algorithm for Dudley’s Hat Problem. alikoker.com.tr. https://alikoker.com.tr/en/dudleys-hat-solution-algorithm

- BibTeX: https://alikoker.com.tr/en/dudleys-hat-solution-algorithm.bib
- RIS: https://alikoker.com.tr/en/dudleys-hat-solution-algorithm.ris
- CSL-JSON: https://alikoker.com.tr/en/dudleys-hat-solution-algorithm.csl.json