0

Possible Duplicate:
How to solve the “Mastermind” guessing game?

I have to choose k items out of n choices, and my selection needs to be in the correct order (i.e. permutation, not combination). After I make a choice, I receive a hint that tells me how many of my selections were correct, and how many were in the correct order.

For example, if I'm trying to choose k=4 out of n=6 items, and the correct ordered set is 5, 3, 1, 2, then an exchange may go as follows:

0,1,2,3
(3, 0) # 3 correct, 0 in the correct position

0,1,2,5
(3, 0)

0,1,5,3
(3, 0)

0,5,2,3
(3,0)

5,1,2,3
(4,1)

5,3,1,2
(4,4)

-> correct order, the game is over

The problem is I'm only given a limited number of tries to get the order right, so if n=6, k=4, then I only get t=6 tries, if n=10,k=5 then t=5, and if n=35,k=6 then t=18.

Where do I start to write an algorithm that solves this? It almost seems like a constraint solving problem. The hard part seems to be that I only know something for sure if I only change 1 thing at once, but the upper bound on that is way more than the number of tries I get.

4

2 回答 2

1

As I can see, this a variation of mastermind board game http://en.m.wikipedia.org/wiki/Mastermind_(board_game)

Also, you can find more details about the problem in this paper

http://arxiv.org/abs/cs.CC/0512049

于 2013-02-01T06:34:34.063 回答
1

A simple strategy for an algorithm is to come up with a next guess that is consistent with all previous hints. This will eventually lead to the right solution, but most likely not in the lowest possible number of guesses.

于 2013-02-01T06:48:26.413 回答