#if 0 My Mastermind strategy is: pick 2 numbers for the first guess, pick 2 different numbers for the second guess, and then make subsequent guesses that are not at odds with previous feedback. A silicon-based solver could do the same thing. Rule 1. When the "totally correct" and "partially correct" responses are both 0, all the numbers in the guess cannot be in the answer, and should be eliminated from consideration for every slot (or position). Rule 2. When the "totally correct" response is 0, each number in the guess cannot be in the answer at the slot where that number appears in the guess. An array of 4 "slot" abstractions would allow the feedback from rules 1 and 2 to be captured, and then a "guess generator" abstraction could sequentially enumerate all combinations of the remaining numbers. As each combination is generated, it can be validated against all previ- ous feedback. If it contradicts a previous response, it is eliminated. If not, it is the next guess. Here is an example that exercises rule 1............................... Input: help 4 4 5 5 1 1 Input: help 0 0 1 1 eliminating 0 eliminating 0 eliminating 1 eliminating 1 0 0 Input: help possible guesses eliminated were 11 5 4 2 2 2 0 Input: help possible guesses eliminated were 41 3 4 4 2 4 0 Here is an example that exercises rule 2 twice......................... Input: help 0 0 1 1 removing 0 from position 1 removing 0 from position 2 removing 1 from position 3 removing 1 from position 4 0 1 Input: help 2 2 3 3 removing 2 from position 1 removing 2 from position 2 removing 3 from position 3 removing 3 from position 4 0 2 Input: help possible guesses eliminated were 22 4 3 2 0 2 1 Input: help possible guesses eliminated were 29 3 5 2 0 4 0 Here is an example that exercises rule 2, and generates and discards 1300 guesses........................................................... Input: help 1 1 2 2 1 1 Input: help 3 3 4 4 2 0 Input: help possible guesses eliminated were 309 3 3 2 1 1 1 Input: help possible guesses eliminated were 591 3 2 4 2 removing 3 from position 1 removing 2 from position 2 removing 4 from position 3 removing 2 from position 4 0 2 Input: help possible guesses eliminated were 411 1 3 1 4 4 0 Here is a demo of a Guess_Generator class that employs a slots[NUM_SLOTS] array................................................. const int NUM_SLOTS = 3; const int NUM_CHOICES = 6; Guess_Generator guess_gen; guess_gen.eliminate( 0 ); guess_gen.eliminate( 4 ); guess_gen.eliminate( 5 ); int guess[NUM_SLOTS]; guess_gen.first_count_array( guess ); do { for (int i=0; i < NUM_SLOTS; ++i) cout << guess[i]; cout << ' '; } while (guess_gen.next_count_array( guess )); 111 211 311 121 221 321 131 231 331 112 212 312 122 222 322 132 232 332 113 213 313 123 223 323 133 233 333 const int NUM_SLOTS = 4; const int NUM_CHOICES = 6; guess_gen.remove( 0, 0 ); guess_gen.remove( 1, 0 ); guess_gen.remove( 2, 0 ); => 3,4,5 guess_gen.remove( 1, 1 ); guess_gen.remove( 2, 1 ); guess_gen.remove( 3, 1 ); => 0,4,5 guess_gen.remove( 2, 2 ); guess_gen.remove( 3, 2 ); guess_gen.remove( 4, 2 ); => 0,1,5 guess_gen.remove( 3, 3 ); guess_gen.remove( 4, 3 ); guess_gen.remove( 5, 3 ); => 0,1,2 3000 4000 5000 3400 4400 5400 3500 4500 5500 3010 4010 5010 3410 4410 5410 3510 4510 5510 3050 4050 5050 3450 4450 5450 3550 4550 5550 3001 4001 5001 3401 4401 5401 3501 4501 5501 3011 4011 5011 3411 4411 5411 3511 4511 5511 3051 4051 5051 3451 4451 5451 3551 4551 5551 3002 4002 5002 3402 4402 5402 3502 4502 5502 3012 4012 5012 3412 4412 5412 3512 4512 5512 3052 4052 5052 3452 4452 5452 3552 4552 5552 #endif // The entire solver application ...................................... #include #include #include #include using std::cout; using std::cin; using std::string; using std::stringstream; using std::vector; const int NUM_CHOICES = 6; const int NUM_SLOTS = 4; struct Next_Struct { int next; bool carry; }; class Slot { public: Slot(); int reset() { return choices[next = 0]; } int get() { return choices[next]; } void get_next( Next_Struct& s ); void remove( int num ); private: int choices[NUM_CHOICES]; int length; int next; }; class Guess_Generator { public: void first_count_array( int arr[] ); void next_count_array( int arr[] ); void eliminate( int gone ); void remove( int gone, int slot ); private: Slot slots[NUM_SLOTS]; }; struct Guess_Struct { int one, two, thr, fou, tot, par; Guess_Struct( int g[], int resp[] ) { one = g[0]; two = g[1]; thr = g[2]; fou = g[3]; tot = resp[0]; par = resp[1]; } }; class Mastermind_Solver { public: Mastermind_Solver( class Mastermind_Engine* engine ); void register_guess( int guess[], int response[] ); void generate_guess( int guess[] ); private: Mastermind_Engine* mm_engine; Guess_Generator guess_gen; vector history; int not_consistent_count; bool rule_one( Guess_Struct guess ); void rule_two( Guess_Struct guess ); bool is_consistent( int answer[] ); }; class Mastermind_Engine { public: Mastermind_Engine(); void evaluate_guess( int guess[], int response[] ); void evaluate_guess( int answer[], int answer_nums[], int guess[], int response[] ); void generate_guess( int guess[] ) { mm_solver.generate_guess( guess ); } void get_answer( int ans[] ) { for (int i=0; i < 4; i = i + 1) ans[i] = answer[i]; } private: int answer[4]; int answer_nums[6]; Mastermind_Solver mm_solver; int min( int one, int two ); }; int main() { Mastermind_Engine mm_engine; string input_string; int guess[4], response[2]; while (true) { cout << "Input: "; getline( cin, input_string ); if (input_string == "quit") break; if (input_string == "answer") { mm_engine.get_answer( guess ); cout << " "; for (int i=0; i < 4; ++i) cout << guess[i]; cout << '\n'; continue; } if (input_string == "help") { mm_engine.generate_guess( guess ); cout << " "; for (int i=0; i < 4; ++i) cout << ' ' << guess[i]; cout << '\n'; } else { stringstream ss; ss << input_string; for (int i=0; i < 4; i = i + 1) ss >> guess[i]; } mm_engine.evaluate_guess( guess, response ); cout << " " << response[0] << " " << response[1] << '\n'; if (response[0] == 4) break; } } Mastermind_Engine::Mastermind_Engine() : mm_solver( this ) { srand( time( 0 ) ); for (int i=0; i < 4; i = i + 1) answer[i] = rand() % 6; for (int i=0; i < 7; i = i + 1) answer_nums[i] = 0; for (int i=0; i < 4; i = i + 1) answer_nums[ answer[i] ]++; } void Mastermind_Engine::evaluate_guess( int guess[], int response[] ) { evaluate_guess( answer, answer_nums, guess, response ); mm_solver.register_guess( guess, response ); } void Mastermind_Engine::evaluate_guess( int answer[], int answer_nums[], int guess[], int response[] ) { int guess_nums[7] = { 0 }; response[0] = response[1] = 0; for (int i=0; i < 4; i = i + 1) guess_nums[ guess[i] ]++; // Over-compute the partially_correct value for (int i=0; i < 6; i = i + 1) response[1] = response[1] + min( guess_nums[i], answer_nums[i] ); // Compute the totally_correct value for (int i=0; i < 4; i = i + 1) if (guess[i] == answer[i]) response[0]++; // Remove the totally_correct value from the partially_correct value response[1] = response[1] - response[0]; } int Mastermind_Engine::min( int one, int two ) { if (one < two) return one; else return two; } Mastermind_Solver::Mastermind_Solver( Mastermind_Engine* engine ) : mm_engine( engine ) { not_consistent_count = 0; } void Mastermind_Solver::generate_guess( int guess[] ) { if (history.size() == 0) { int first = rand() % NUM_CHOICES; int second = (first+1) % NUM_CHOICES; guess[0] = first; guess[1] = first; guess[2] = second; guess[3] = second; } else if (history.size() == 1) { int first = (history[0].fou + 1) % NUM_CHOICES; int second = (first+1) % NUM_CHOICES; guess[0] = first; guess[1] = first; guess[2] = second; guess[3] = second; } else { guess_gen.first_count_array( guess ); while ( ! is_consistent( guess )) guess_gen.next_count_array( guess ); cout << " possible guesses eliminated were " << not_consistent_count << '\n'; not_consistent_count = 0; } } bool Mastermind_Solver::is_consistent( int answer[] ) { int answer_nums[NUM_CHOICES] = { 0 }; for (int j=0; j < 4; j++) answer_nums[ answer[j] ]++; int guess[NUM_SLOTS], response[2]; for (int i=0; i < history.size(); ++i) { guess[0] = history[i].one; guess[1] = history[i].two; guess[2] = history[i].thr; guess[3] = history[i].fou; mm_engine->evaluate_guess( answer, answer_nums, guess, response ); if (response[0] != history[i].tot || response[1] != history[i].par) { not_consistent_count++; return false; } } return true; } void Mastermind_Solver::register_guess( int guess[], int response[] ) { Guess_Struct gs( guess, response ); if ( ! rule_one( gs )) rule_two( gs ); history.push_back( gs ); } bool Mastermind_Solver::rule_one( Guess_Struct guess ) { if (guess.tot + guess.par == 0) { guess_gen.eliminate( guess.one ); guess_gen.eliminate( guess.two ); guess_gen.eliminate( guess.thr ); guess_gen.eliminate( guess.fou ); return true; } else return false; } void Mastermind_Solver::rule_two( Guess_Struct guess ) { if (guess.tot == 0) { guess_gen.remove( guess.one, 0 ); guess_gen.remove( guess.two, 1 ); guess_gen.remove( guess.thr, 2 ); guess_gen.remove( guess.fou, 3 ); } } void Guess_Generator::eliminate( int gone ) { cout << " eliminating " << gone << '\n'; for (int j=0; j < NUM_SLOTS; j++) slots[j].remove( gone ); } void Guess_Generator::remove( int gone, int slot ) { cout << " removing " << gone << " from position " << (slot+1) << '\n'; slots[slot].remove( gone ); } void Guess_Generator::first_count_array( int arr[] ) { for (int i=0; i < NUM_SLOTS; i++) arr[i] = slots[i].reset(); } void Guess_Generator::next_count_array( int arr[] ) { Next_Struct s; int x = 0; do { slots[x].get_next( s ); arr[x++] = s.next; } while (s.carry); } Slot::Slot() { length = NUM_CHOICES; for (int i=0; i < NUM_CHOICES; ++i) choices[i] = i; next = 0; } void Slot::get_next( Next_Struct& s ) { s.carry = false; if (++next == length) { next = 0; s.carry = true; } s.next = choices[next]; } void Slot::remove( int num ) { for (int i=0; i < length; i++) if (choices[i] == num) { for (int end = length-1; i < end; i++) choices[i] = choices[i+1]; length -= 1; } }