《算法的乐趣》第二十三节

本节继续探讨爱因斯坦谜题的求解，重点是数据结构优化、线索建模与算法设计。

本节继续探讨爱因斯坦谜题的求解，重点是数据结构优化、线索建模与算法设计。

首先改进GROUP的结构：把每种属性（房子颜色、国籍等）在组中的位置固定，用数组下标直接代表属性类型，只存值即可，同时让枚举类型与下标绑定。这样既简化实现，又提高访问效率。

接着把15条线索分为三类并分别建模：属性间固定绑定的线索（如丹麦人喝茶）存入binds数组；描述相邻组关系的线索（如养马者与抽Dunhill者相邻）存入relations数组；无法统一建模的线索（如绿房紧挨白房、中间房喝牛奶）直接在枚举过程中过滤。

算法设计分两步：穷举时按房子颜色、国籍、饮料、宠物、香烟的顺序逐层枚举，每层内嵌处理特殊线索（如绿白房绑定、挪威人住首房），层层组合后共产生约1.99亿个结果；判定时只需遍历binds和relations数组检查，避免冗长的if…else分支，快速筛出满足全部线索的正确答案。