Q:

Find the minimum number of guesses

Your friend will pick a 4-letter word and you will make guesses in order to find it. 
-A word can contain only the letters A, B, C, and D, and they can be used more than once. (AAAA-DDDD). 
-In your guess if at least three letters are in their correct places you will win a prize. 
What is the minimum number of guesses in order to guarantee to win the prize?
Edit: The question is compared to other question by many: Mastermind 
But I assure you that they are not the same! Mine is harder. Only feedback you will have is whether your guess is true(at least 3 letters in the right places)
or not. Have fun!

A:

Edit: I think I can back up Oray's solution with a proof and confirm that the answer is indeed 

 $24$

His algorithm suffices to give the upper bound so it only remains to show that it is also a lower bound.
Lower bound

 Call a pair of words 'neighbours' if they differ by one letter e.g, $ABCD$ and $ABAD$ are neighbours.  Let us consider the map $A \rightarrow 0, B \rightarrow 1, C \rightarrow 2, D \rightarrow 3$ so that each word maps to a point in 4-dimensional space, e.g, $BACD \rightarrow (1, 0, 2, 3)$. Then the set of words is a finite hypercube lattice (of side length 3) and the set of neighbours of a given word, $W$, is the set of points which lie on some axis-parallel line passing through the point corresponding to $W$.  The set of words beginning with a given letter is a finite cubic lattice in this space.  Key Observation: Each guess eliminates $10$ possible answers from the cube containing the guess and $1$ possible answer from each of the other cubes.  Now, suppose that the number of guesses we make is less than $24$. Then there is at least one cube which contains at most $5$ guesses.  We may ask the following question: what is the maximum number of words we can eliminate from a single cube with $5$ guesses?  I propose that the answer is $45$. To show this, notice that each cube further subdivides into four planes corresponding to fixing the second letter of the word. With $5$ guesses, there is at least one of these planes which contains at least two guesses. This pair of guesses will share at least two neighbours (call them intersections of the guesses). Alternatively, we can subdivide the cube lattice into planes in the other two directions (defined by fixing the third or fourth letter) and use the same logic to show that there exists a plane, in each of these directions, which contains at least two guesses with at least a pair of intersections. On face value this seems to constitute six intersections but really there are three possible scenarios to consider.  (i) These intersections may be distinct, in which case there are a total of six intersections.  (ii) One or more of these intersections may appear twice, in which case any double intersection counts twice (as it prevents two guesses from eliminating an additional possible answer). So again there are essentially a total of six intersections.  (iii) One intersection may appear three times. This is a special case as the triple intersection may only count twice (it prevents two guesses from eliminating a possible answer but if these two guesses also intersect here it is to neither one's detriment). Hence, in this case there are essentially five intersections.  The point is that the maximum number of words in a given cube that can be eliminated as possible answers by $5$ guesses in that cube is $5 \times 10 - 5 = 45$. The maximum number of words in a given cube that can be covered by $18$ guesses in other cubes is $18$. Hence, if we are limited to at most $23$ guesses, then there is some cube with at most $45 + 18 = 63$ out of $64$ words eliminated as possible answers. Hence, the number of guesses we must make is at least $24$.  Note 1: If the above logic does not convince you, it does not take very much computing power to show that, in a given cube of words with $5$ guesses, we can eliminate at most $45$ possible answers since  ${{64}\choose{5}} = 7,624,512$ which is not terribly big.  Note 2: It should be fairly clear that it's not worth having less than five guesses in a given cube if we are limited to $23$ overall since we make up only one guess by guessing in a different cube and lose at least that by not guessing in the given cube.  Note 3: One thing that falls out from this analysis is that it may be possible, with $23$ guesses, to guarantee that either you win the prize or you definitely know your friend's word. I don't know if this is achievable but would be very interesting to see if so.

A:

I have a set of size

 30

The set:

 BACB, CABC, ABDA, ACDA, BBCA, CADD, CBBA, DAAA, CCDA, ABAD, ADAB, BDBD, CDAB, ADCC, CCCD, BDBA, ABCB, DCBB, DDDC, AACB, BBDB, CCCA, BADD, DADD, BCAC, ACDD, DBAD, CBBC, AABC, DDCC

I found this using the weighted A* algorithm with an epsilon of 5...meaning it is not guaranteed to be finding the optimal solution.  I'm trying to balance runtime demands with optimality; I'll gradually reduce the epsilon to 0 and see if anything beats the above solution.

A:

I have found the minimum set of

24

which are

AAAA AAAB ABBC ACCDACDD ADBC BABD BBCABBDB BCAC BDCB BDDACACC CADC CBAD CCBACCBB CDAD DABD DBCBDBDA DCAC DDCA DDDB

This is the optimal solution (actually there are 4 solutions but they are mirrors so I share with AAAA version with you: BBBB CCCC and DDDD versions are possible too), found by using computer programming with my own algorithm that I had mentioned on my deleted post: 

Take a word (from the table all possible 256 words), find the maximum number of matches with 13 possible words by changing one letter from A to D from each digit.
Try to find matches in the Word Pool and count how many matches there are with all words,
Choose a word randomly which has the highest amount of matches,
Remove those matched words from the word pool with the word you chose randomly,
Go back to the beginning and go on until you do not have any word left in your word pool and count your tries.

I wish I wanted to share the code, but it is too messy, but the algorithm is something like this.
As a result, I got

24

which is found after 8 hours of running my coding... I wanted to explain the result but this is purely found by computer.

