// Fifteen Puzzle solver #include #include #include using namespace::std; const int width = 4, height = 4, length = width * height; int squares[length]; int blank = 0; bool initializing = true; int dont_touch_list[length]; int sp = -1; void init(); void move( int number ); void display(); void print_squares_array(); string format( int number ); int find_location_of( int number ); bool not_on_dont_touch_list( int position ); void print_dont_touch_list( string preface ); void swap( int one, int two ); void move_number( int current_number ); void move_to_x( int& position, int target_x ); void move_to_y( int& position, int target_y ); void move_blank_to( int destination ); void move_blank_to_x( int& blank_x, int& blank_y, int destination_x ); void move_blank_to_y( int& blank_x, int& blank_y, int destination_y ); void do_last_square_on_row( int vertical, int horizontal ); void do_top_number_of_column( int current_number ); int main( void ) { init(); int current_number = 1; while (current_number < width * (height-2) + 1) move_number( current_number++ ); // Do the last 2 rows, from left column to right cout << "main: bottom 2 rows\n"; for (int i=1; i < width - 1; i++) { // Do the bottom number of this column current_number = width * (height - 1) + i; cout << "main: first next is " << current_number << endl; move_number( current_number ); // Do the top number of this column do_top_number_of_column( current_number - width ); } // Do the last 2 columns of the last 2 rows // Put the top-left square in place move_number( width * (height - 1) - 1 ); // Put the blank in the bottom-right corner move_blank_to( width * height - 1 ); } void move_number( int current_number ) { int location, target_x, target_y; location = find_location_of( current_number ); target_x = (current_number-1) % width; target_y = (current_number-1) / width; cout << "main: number " << current_number << ", location " << location << ", target_x " << target_x << ", target_y " << target_y << endl; dont_touch_list[++sp] = location; print_dont_touch_list( "main: next added " ); move_to_x( location, target_x ); move_to_y( location, target_y ); // this has do_last_square_on_row() call } void move_to_x( int& position, int target_x ) { int current_x = position % width; if (current_x == target_x) return; cout << "move_to_x: current_x " << current_x << ", target_x " << target_x << endl; int direction = (current_x < target_x) ? 1 : -1; while (current_x != target_x) { move_blank_to( position + direction ); swap( position, position + direction ); position = position + direction; // Update the last entry on the dont_touch_list dont_touch_list[sp] = position; current_x += direction; } } void move_to_y( int& position, int target_y ) { int current_y = position / width; if (current_y == target_y) return; cout << "move_to_y: current_y " << current_y << ", target_y " << target_y << " "; print_dont_touch_list( "" ); bool last_square_on_row = false; int direction = (current_y < target_y) ? 1 : -1; // 1 2 3 // 5 6 8 4 // 13 11 15 7 // 9 14 10 12 // It is okay to "step on" (or "through") the square that needs to be moved, because // we are putting the square where it needs to go if (current_y-1 == target_y && position-width == blank) { swap( position, blank ); dont_touch_list[sp] = position-width; return; } // Check if last on row if (position % width == width - 1) { target_y++; cout << " new target_y " << target_y << endl; last_square_on_row = true; } while (current_y != target_y) { move_blank_to( position + (direction * width) ); swap( position, position + (direction * width) ); position = position + (direction * width); // Update the last entry on the dont_touch_list dont_touch_list[sp] = position; current_y += direction; } if (last_square_on_row) { cout << "move_to_y: moving blank to " << (position + width) << endl; move_blank_to( position + width ); do_last_square_on_row( width, 1 ); } } void move_blank_to( int destination ) { int blank_x = blank % width; int blank_y = blank / width; int destination_x = destination % width; int destination_y = destination / width; cout << "move_blank_to: blank - " << blank << " " << blank_x << " " << blank_y << ", destination - " << destination << " " << destination_x << " " << destination_y << endl; // 9 3 2 11 // 1 5 15 8 // 4 10 6 // 14 13 7 12 // 1st blank_to_x() returns immediately, blank_to_y() works, 2nd blank_to_x() works int entry_sp = sp; move_blank_to_x( blank_x, blank_y, destination_x ); move_blank_to_y( blank_x, blank_y, destination_y ); move_blank_to_x( blank_x, blank_y, destination_x ); sp = entry_sp; } void move_blank_to_x( int& blank_x, int& blank_y, int destination_x ) { int direction = (blank_x < destination_x) ? 1 : -1; print_dont_touch_list( "move_blank_to_x: " ); while (blank_x != destination_x) { if (not_on_dont_touch_list(blank + direction)) { cout << "move_blank_to_x: swap " << blank << " " << (blank + direction) << '\n'; swap( blank, blank + direction ); blank_x += direction; // Try moving up and around } else if (blank_y != 0 && not_on_dont_touch_list(blank - width)) { cout << "move_blank_to_x: move up and around\n"; dont_touch_list[++sp] = blank; swap( blank, blank - width ); blank_y = blank_y - 1; dont_touch_list[++sp] = blank; swap( blank, blank + direction ); blank_x += direction; // Try moving down and around } else if (blank_y < height-1 && not_on_dont_touch_list(blank + width)) { cout << "move_blank_to_x: move down and around\n"; dont_touch_list[++sp] = blank; swap( blank, blank + width ); blank_y = blank_y + 1; dont_touch_list[++sp] = blank; swap( blank, blank + direction ); blank_x += direction; } else { cout << "move_blank_to_x: could not get out of corner\nPress \n"; string str; getline( cin, str ); } } } void move_blank_to_y( int& blank_x, int& blank_y, int destination_y ) { int direction = (blank_y < destination_y) ? 1 : -1; cout << "move_blank_to_y: blank " << blank << " " << blank_x << " " << blank_y << " dest y " << destination_y << endl; print_dont_touch_list( "move_blank_to_y: " ); while (blank_y != destination_y) { if (not_on_dont_touch_list(blank + (direction * width))) { cout << "move_blank_to_y: swap " << blank << " " << (blank + (direction * width)) << '\n'; swap( blank, blank + (direction * width) ); blank_y = blank_y + direction; // Try moving right and around } else if (blank_x < width-1 && not_on_dont_touch_list(blank + 1)) { cout << "move_blank_to_y: move right and around\n"; dont_touch_list[++sp] = blank; swap( blank, blank + 1 ); blank_x = blank_x + 1; dont_touch_list[++sp] = blank; swap( blank, blank + (direction * width) ); blank_y = blank_y + direction; // Try moving left and around } else if (blank_x != 0 && not_on_dont_touch_list(blank - 1)) { cout << "move_blank_to_y: move left and around\n"; dont_touch_list[++sp] = blank; swap( blank, blank - 1 ); blank_x = blank_x - 1; dont_touch_list[++sp] = blank; swap( blank, blank + (direction * width) ); blank_y += direction; } else { cout << "move_blank_to_y: could not get out of corner\n"; } } } void do_top_number_of_column( int current_number ) { int location = find_location_of( current_number ); cout << "main: second next is " << current_number << ", location " << location << endl; // If the next number is already in place, move on if (current_number-1 == location) return; // If the next number is almost in place, swap and move on if (current_number == location && blank == current_number-1) { dont_touch_list[++sp] = blank; swap( location, blank ); return; } dont_touch_list[++sp] = location; move_to_x( location, (current_number-1) % width + 1 ); move_to_y( location, (current_number-1) / width ); move_blank_to( location + 1 ); do_last_square_on_row( 1, -width ); } void do_last_square_on_row( int vertical, int horizontal ) { cout << "do_last_square_on_row\n"; swap( blank, blank - vertical ); swap( blank, blank - vertical ); swap( blank, blank - horizontal ); swap( blank, blank + vertical ); swap( blank, blank + horizontal ); swap( blank, blank + vertical ); swap( blank, blank - horizontal ); swap( blank, blank - vertical ); swap( blank, blank - vertical ); swap( blank, blank + horizontal ); swap( blank, blank + vertical ); dont_touch_list[sp] -= vertical; } void init() { srand( time( 0 ) ); for (int i=1; i < length; i++) squares[i-1] = i; squares[length-1] = 0; blank = length - 1; for (int i=0; i < 400; i++) move( rand() % (length-1) + 1 ); initializing = false; //display(); } void print_squares_array() { for (int i=0; i < length; i++) cout << squares[i] << ' '; cout << "--- " << blank << endl; } string format( int number ) { if (number == 0) return " "; stringstream ss; ss << (number < 10 ? " " : "") << number << " "; return ss.str(); } bool not_on_dont_touch_list( int position ) { for (int i=0; i <= sp; i++) if (dont_touch_list[i] == position) return false; return true; } void print_dont_touch_list( string preface ) { cout << preface; for (int i=0; i <= sp; i++) cout << dont_touch_list[i] << ' '; cout << endl; } int find_location_of( int number ) { for (int i=0; i < length; i++) if (squares[i] == number) return i; cout << "find_location_of: " << number << " was not found\n"; return 0; } void display() { cout << '\n'; print_squares_array(); // vlh for (int i=0; i < height; i++) { for (int j=0; j < width; j++) cout << format( squares[i * width + j] ); cout << '\n'; } string str; // vlh getline( cin, str ); // vlh } void swap( int one, int two ) { int temp = squares[one]; squares[one] = squares[two]; squares[two] = temp; if (squares[one] == 0) blank = one; else if (squares[two] == 0) blank = two; else cout << "swap: blank not here " << one << " " << two << endl; if (initializing) // vlh return; // vlh display(); // vlh } bool try_above( int pos ) { if (pos < width) return false; if (squares[pos-width] != 0 && ! try_above(pos-width)) return false; // the slot above is empty OR the move above succeeded swap( pos, pos-width ); return true; } bool try_below( int pos ) { if (pos > width*(height-1)-1) return false; if (squares[pos+width] != 0 && ! try_below(pos+width)) return false; swap( pos, pos+width ); return true; } bool try_left( int pos ) { if (pos%width == 0) return false; if (squares[pos-1] != 0 && ! try_left(pos-1)) return false; swap( pos, pos-1 ); return true; } bool try_right( int pos ) { if (pos%width == width-1) return false; if (squares[pos+1] != 0 && ! try_right(pos+1)) return false; swap( pos, pos+1 ); return true; } void move( int num ) { int i; ////// find the slot this number is in ////// for (i=0; i < length; ++i) if (squares[i] == num) break; if (try_above(i)) return; if (try_below(i)) return; if (try_left(i)) return; if (try_right(i)) return; }