S

safe, inferring the combination of, 54–55, 103–104

scalar value, encoding a problem configuration as, 164

scale-free networks, building, 35

Schaefer, Steve, 89

scheduling in an overloaded system, 132

scheduling puzzle, 131–132

Scheduling Tradition mind game, 34

solution to, 90

search space

attempts reducing in Winning at the Slots, 178

controlling the size of, 177–178

difficult one for simulated annealing, 167

exploring, 164

selective greed, 154

Selective Greed puzzle, 150–154

solution to, 155

selfish behavior, mathematical analysis of the consequences of, 15

selfishness, leading to social loss, 15

sensors

estimating distance to a treasure, 133–137

placement of inaccurate, 137

Shannon, Claude, 29

Simionescu, Vlad, 113

simulated annealing, 165

applying to the overloaded scheduling problem, 167–168

as a favorite technique, 165–167

skateboard, Indiana Jones on, 24–28, 84–86

Smith, Adam, 15

Social Games mind game, 15–18

solution to, 80–81

solutions, gluing the best subproblems together, 150

source string, converting to a target string, 150

spanning tree(s)

combining minimal matchings with, 161

cost of, 160

defined, 160

as the lowest cost route for TSP, 161

when symmetry and triangle inequality fail to hold, 163

speculation

given a set of constraints, 147

implied in case analysis, 122

required by hard Sudokus, 144

square pie, cutting into equal pieces, 37–39, 94–96

squares (chessboard), knight flipping the colors of, 33, 89

statistical questions, revealing personal data, 59

string edit distance, 122

string edit problem, 150

submarine, need for near-silence in, 73

subproblems, finding the lowest cost solution to, 150

Sudokill, 146

Sudoku

algorithm designed for, 143–144

as an elimination puzzle, 122

as a two-person game, 146

Sudoku puzzle, 138–145

solution to, 146

sultan’s daughters problem, variant on, 12–13

supertox liquid in Mad Mix, 63

supervertices, 93

Sweet Packs puzzle, 156–157

solution to, 158

Sweet Tooth mind game, 4–5

solution to, 74

switchboard nodes, 92–93

switching doors, 181, 184–187

symmetry

in TSP, 159

violating, 163