The game of bulls and cows is played by two players. One of them thinks of a 4-digit cipher (digits from 0 to 9) and then, the other player comes up with a suggestion. The first player responds with the number of properly placed numbers (bulls) and with the number of correct, but in the wrong place, numbers (cows).
I want to write a program which guesses the secret code and then reads the number of bulls and cows and makes another guess. I want this process to end relatively quickly.
1. Create a 4-dimensional boolean array 10 x 10 x 10 x 10
2. Set all elements of this array to true, bulls = 0, cows = 0
3. While bulls != 4
3.1. Find the first element of the array which is set to true
3.2. Make a guess with this number
3.3. Read the number of bulls and cows
3.4. If bulls = 0 and cows = 0
set all codes containing any of the digits from the last code to false
This is where I got with this algorithm. I am not sure how to proceed. The most obvious way for me is to analyze all possible numbers of bulls and cows manually, but this will simply take too long and too much space. Could you give me a hint if there is a universal way to cater for all possible scenarios?
This game reminds me of the game Jotto, where two players pick words and in turn try to guess each other's word, only being told how many letters from their guess is in the actual word (a big difference being in Jotto only actual words can be used).
My first step would be to identify 4 cows/bulls. This way we have all 4 digits, then we can worry about getting the order correct.
To identify 4 cows/bulls, we would first guess 4 random numbers. If we get lucky and cows + bulls = 0, then we could eliminate all 4 of these numbers. Otherwise, we would alter our guess one number at a time. Let's say we guessed with a, b, c, d, then we guess with a, b, c, e.
If cows + bulls goes down by 1 after the next guess, we can conclude that the number we removed (d) was a cow or bull and the new number (e) is not a cow or bull.
If cows + bulls doesn't change, then either both d and e are cows/bulls, or neither d nor e are cows/bulls. We can try another number (f) until we see a change, and draw a conclusion from there.
If cows + bulls goes up by 1 then we can conclude that e is a cow/bull and d is neither a cow nor bull.
We would continue this until we have all 4 numbers. Then we could try different arrangements, again one change at a time, to determine if we are getting closer or farther.