// Peg Game Advisor #include #include #include using std::cout; using std::cin; using std::string; using std::deque; int jump_table[][3] = { {1,4,2}, {1,6,3}, {2,7,4}, {2,9,5}, /* {a,b,c} */ {3,8,5}, {3,10,6}, /* a = "from" position */ {4,6,5}, {4,1,2}, {4,11,7}, {4,13,8}, /* b = "to" position */ {5,14,9}, {5,12,8}, /* c = "jumped" position */ {6,4,5}, {6,13,9}, {6,15,10}, {6,1,3}, {7,2,4}, {7,9,8}, {8,3,5}, {8,10,9}, {9,2,5}, {9,7,8}, {10,8,9}, {10,3,6}, {11,13,12}, {11,4,7}, {12,5,8}, {12,14,13}, {13,11,12}, {13,15,14}, {13,6,9}, {13,4,8}, {14,12,13}, {14,5,9}, {15,13,14}, {15,6,10} }; bool pegs_present[15]; int peg_count = 15; deque deferred_move_stack; bool possible_move( int n ) { if (pegs_present[ jump_table[n][0]-1 ] // if sourcePeg is present && pegs_present[ jump_table[n][2]-1 ] // if jumpedPeg is present && ( ! pegs_present[ jump_table[n][1]-1 ])) // if destination is empty return true; return false; } int push_possible_moves_on_deferred_move_stack() { int num_pushed = 0; for (int i=0; i < 36; i++) if (possible_move( i )) { deferred_move_stack.push_front( i ); num_pushed++; } return num_pushed; } int legal_move( int one, int two ) { one++; two++; for (int i=0; i < 36; ++i) if (one == jump_table[i][0] && two == jump_table[i][1] && pegs_present[ jump_table[i][0]-1 ] // if sourcePeg is present && pegs_present[ jump_table[i][2]-1 ] // if jumpedPeg is present && ( ! pegs_present[ jump_table[i][1]-1 ])) // if destination is empty return i; return -1; } void do_move( int n ) { pegs_present[ jump_table[n][0]-1 ] = false; // sourcePeg pegs_present[ jump_table[n][2]-1 ] = false; // jumpedPeg pegs_present[ jump_table[n][1]-1 ] = true; // destination peg_count--; } void undo_move( int n ) { pegs_present[ jump_table[n][0]-1 ] = true; pegs_present[ jump_table[n][2]-1 ] = true; pegs_present[ jump_table[n][1]-1 ] = false; peg_count++; } bool depth_first_search() { int i = deferred_move_stack.front(); deferred_move_stack.pop_front(); do_move( i ); if (peg_count == 1) { undo_move( i ); return true; } int num_pushed = push_possible_moves_on_deferred_move_stack(); for (int j=0; j < num_pushed; j++) if (depth_first_search()) { undo_move( i ); return true; } undo_move( i ); return false; } string attempt_move( int from, int to ) { int i; if ((i = legal_move( from, to )) == -1) return "NOT A LEGAL MOVE"; deferred_move_stack.push_front( i ); if (depth_first_search()) { do_move( i ); return string(); } deferred_move_stack.clear(); return "NOT A GOOD IDEA - TRY A BETTER MOVE"; } void display() { static string blanks = " "; cout << '\n'; for (int i=0, row=0; row < 5; row++) { cout << blanks.substr( row*3 ); for (int col=0; col <= row; col++, i++) if (pegs_present[i]) cout << '<' << (char)('A'+i) << "> "; else cout << ' ' << (char)('a'+i) << " "; cout << "\n\n"; } } int main( void ) { for (int i=0; i < 15; ++i) pegs_present[i] = true; string input, message; int from, to; display(); cout << "Select initial hole: "; getline( cin, input ); if (input.empty()) return 0; from = (int) input[0] - 'a'; pegs_present[from] = false; peg_count--; while (true) { if ( ! message.empty()) cout << '\n' << message << '\n'; display(); if (peg_count == 1) break; cout << "Move (from to): "; getline( cin, input ); if (input == "") break; from = input[0] - 'a'; to = input[2] - 'a'; message = attempt_move( from, to ); } } #if 0 a b c e g j m n o Move (from to): h j NOT A GOOD IDEA - TRY A BETTER MOVE a b c e g j m n o Move (from to): d m a b c d e g h j n o Move (from to): l n a b c d e g h j l m o Move (from to): f m a b c d e f g h i j l o Move (from to): m h NOT A LEGAL MOVE a b c d e f g h i j l o Move (from to): n l a b c d e f g h i j m n o Move (from to): k m a b c d e f g h i j k l n o #endif