I've picked up Programming Challenges and found a Yahtzee! problem which I will simplify:

• There are 13 scoring categories
• There are 13 rolls by a player (comprising a play)
• Each roll must fit in a distinct category
• The goal is to find the maximum score for a play (the optimal placement of rolls in categories); score(play) returns the score for a play

Brute-forcing to find the maximum play score requires 13! (= 6,227,020,800) score() calls.

I choose simulated annealing to find something close to the highest score, faster. Though not deterministic, it's good enough. I have a list of 13 rolls of 5 die, like:

((1,2,3,4,5) #1
 (1,2,6,3,4),#2
    ...
 (1,4,3,2,2) #13
)

And a play (1,5,6,7,2,3,4,8,9,10,13,12,11) passed into score() returns a score for that play's permutation.

How do I choose a good "neighboring state"? For random-restart, I can simply choose a random permutation of nos. 1-13, put them in a vector, and score them. In the traveling salesman problem, here's an example of a good neighboring state:

"The neighbours of some particular permutation are the permutations that are produced for example by interchanging a pair of adjacent cities."

I have a bad feeling about simply swapping two random vector positions, like so:

(1,5,6,7, 2 , 3,4,8,9,10, 13, 12,11) # switch 2 and 13
(1,5,6,7, 13, 3,4,8,9,10, 2 , 12,11) # now score this one

But I have no evidence and don't know how to select a good neighboring state. Anyone have any ideas on how to pick good neighboring states?