Recursion Warm Ups: Exercise 3, Dominosa

dominosaScreenforweb

Unexpectedly epic. Probably has post Christmas flab on it. I like the way the Stanford exercises are always hooked up to a graphics window and carefully thought out to make the whole thing very visual. Recursive backtracking is quite tricky but amazingly satisfying to get it going. The process is definitely becoming like building. Not that I’ve ever built anything, except for some plastic models when I was a kid. Which I promptly set fire to, nine times out of ten.

/**
 * File: dominosa.cpp
 * ------------------
 * This animates the brute-force discovery of a solution
 * to a 2 x n dominosa board.
 */

#include <iostream>
#include <cmath>
using namespace std;

#include "simpio.h"
#include "grid.h"
#include "random.h"
#include "set.h"
#include "map.h"
#include "dominosa-graphics.h"

static void welcome();
static int getIntegerInRange(string prompt, int low, int high);
static void populateBoard(Grid<int>& board, int low, int high);
static bool canSolveBoard(DominosaDisplay& display, Grid<int>& board, Map<coord, int>& numbers, Set<pair<int, int> >& pairings, int numColumns);
static void certifyPairings(DominosaDisplay& display, Grid<int>& board, Map<coord, int>& numbers, Set<pair<int, int> >& pairings, Vector<int>& orientation, int numColumns);
static bool findPairs(DominosaDisplay& display, Grid<int>& board, Map<coord, int>& numbers, Set<pair<int, int> >& pairings, Vector<int>& orientation, int numColumns, int rewind);
int tryPairing1(DominosaDisplay& display, Grid<int>& board, Map<coord, int>& numbers, Set<pair<int, int> >& pairings, Vector<int>& orientation, int numColumns);
int tryPairing2(DominosaDisplay& display, Grid<int>& board, Map<coord, int>& numbers, Set<pair<int, int> >& pairings, Vector<int>& orientation, int numColumns);
static void deletePairings(DominosaDisplay& display, Map<coord, int>& numbers, Set<pair<int, int> >& pairings, Vector<int>& orientation, int numColumn);
static void buildNumbers( Grid<int>& board, Map<coord, int>& numbers, int numColumns);

int main() {
	DominosaDisplay display;
	welcome();
	while (true) {
		int numColumns = getIntegerInRange("How many columns? [0 to exit]: ", 9, 25);
		if (numColumns == 0) break;
		Grid<int> board(2, numColumns);// grid from the starter file of the exercise- hardly used it
        Set<pair<int, int> > pairings;// Set of pairs to keep track of the pairings
		populateBoard(board, 1, ceil(2 * sqrt(numColumns)));
        Map<coord, int> numbers;// key of tile coordinates and a map of the numbers
        buildNumbers(board, numbers, numColumns);
		display.drawBoard(board);
		if (canSolveBoard(display, board, numbers, pairings, numColumns)) {
			cout << "The board can be solved, and one such solution is drawn above." << endl;
		} else {
			cout << "This board you see can't be solved." << endl;
		}
	}
	
	cout << "Okay, thanks for watching, and come back soon." << endl;
    cout << "Click the mouse anywhere in the window to exit." << endl;
	return 0;
}

static void welcome() {
	cout << "Here we'll illustrate the use of recursive backtracking to" << endl;
	cout << "discover a solution to various 2 x n Dominosa boards.  In some" << endl;
	cout << "cases there won't be any solutions, and in the cases where there are" << endl;
	cout << "multiple solutions, we'll just find one of them." << endl;
	cout << endl;
}

static int getIntegerInRange(string prompt, int low, int high) {
	while (true) {
		int response = getInteger(prompt);
		if (response == 0 || (response >= low && response <= high)) return response;
		cout << "Sorry, but I can't use that number." << endl;
	}
}

static void populateBoard(Grid<int>& board, int low, int high) {
	for (int row = 0; row < board.numRows(); row++) {
		for (int col = 0; col < board.numCols(); col++) {
			board[row][col] = randomInteger(low, high);
		}
	}
}

static bool canSolveBoard(DominosaDisplay& display, Grid<int>& board, Map<coord, int>& numbers, Set<pair<int, int> >& pairings, int numColumns) {
    
    Vector<int> orientation;// to keep track of the direction that the numbers are paired in- 1 for vertial, 2 and 3 for horizontal
    if (findPairs(display, board, numbers, pairings, orientation, numColumns, 0)) {
        certifyPairings(display, board, numbers, pairings, orientation, numColumns);
        return true;
    }
    
    else {
        
        return false;
    }
}

static void certifyPairings(DominosaDisplay& display, Grid<int>& board, Map<coord, int>& numbers, Set<pair<int, int> >& pairings, Vector<int>& orientation, int col) {
    
    int check = col;
    for (int i = check - 1; i > -1; i--) {
        int direction = orientation.get(i);
        if (direction == 1) {
            int one = board.get(0, i);
            int two = board.get(1, i);
            coord coord1, coord2;
            coord1.row = 0;
            coord1.col = i;
            coord2.row = 1;
            coord2.col = i;
            pair<int, int> pair;
                if (one <= two) {
                    pair = make_pair(one, two);
                }
                else if(two < one) {
                    pair = make_pair(two, one);
                }
            if (pairings.contains(pair)) {
                display.certifyPairing(coord1, coord2);
            }
        }
        else if (direction == 2) {
            coord coordthree, coordfour, coordfive, coordsix;
            coordthree.row = 0;
            coordthree.col = i;
            coordfour.row = 0;
            coordfour.col = i - 1;
            coordfive.row = 1;
            coordfive.col = i;
            coordsix.row = 1;
            coordsix.col = i - 1;
            int oneupper = numbers.get(coordthree);
            int twoupper = numbers.get(coordfour);
            int onelower = numbers.get(coordfive);
            int twolower = numbers.get(coordsix);
            
            pair<int, int> pair1, pair2;
                if (oneupper <= twoupper) {
                    pair1 = make_pair(oneupper, twoupper);
                }
                else if (twoupper < oneupper) {
                    pair1 = make_pair(twoupper, oneupper);
                }
                if (onelower <= twolower) {
                    pair2 = make_pair(onelower, twolower);
                }
                else if (twolower < onelower) {
                    pair2 = make_pair(twolower, onelower);
                }
            if (pairings.contains(pair1) && pairings.contains(pair2) ) {
                display.certifyPairing(coordthree, coordfour);
                display.certifyPairing(coordfive, coordsix);
            }
        }
    }
}

static void buildNumbers( Grid<int>& board, Map<coord, int>& numbers, int numColumns) {
    for (int row = 0; row < 2; row++) {
        for (int column = 0; column < numColumns; column++) {
            int number = board[row][column];
            coord location;
            location.row = row;
            location.col = column;
            numbers.put(location, number);
        }
    }
}

static bool findPairs(DominosaDisplay& display, Grid<int>& board, Map<coord, int>& numbers, Set<pair<int, int> >& pairings, Vector<int>& orientation, int numColumns, int rewind) {
    
    int numcolumn = pairings.size();
    
    if (numcolumn == numColumns) return true; // base case, if the set of pairs has reached the size of numColumns, it's done
    
    if (numcolumn < numColumns) {
        
        for (int i = 1; i < 3; i++) {
            
            if (i == 1) {// Do vertical pairing on loop 1, and horizontal second loop
                rewind = tryPairing1(display, board, numbers, pairings, orientation, numColumns);
            }
            
            else if (i == 2) {// try pairing 2 horizintally
                rewind = tryPairing2(display, board, numbers, pairings, orientation, numColumns);
            }
                     
            if (rewind != 1) {// the result from tryPairing determines if it skips the recursion and rewinds
                if (findPairs(display, board, numbers, pairings, orientation, numColumns, rewind)) return true;
            }
        }
        
        deletePairings(display, numbers, pairings, orientation, numColumns);// rewind to an earlier decision

    }
	return false;
}

int tryPairing1(DominosaDisplay& display, Grid<int>& board, Map<coord, int>& numbers, Set<pair<int, int> >& pairings, Vector<int>& orientation, int numColumns) {
    int col = pairings.size();
        coord coordone, coordtwo;
        coordone.row = 0;
        coordone.col = col;
        coordtwo.row = 1;
        coordtwo.col = col;
        int one = numbers.get(coordone);
        int two = numbers.get(coordtwo);
        
        pair<int, int> pair;
        
        if (one <= two) {
            pair = make_pair(one, two);
        }
        else if (two < one) {
            pair = make_pair(two, one);
        }
        
        if (pairings.contains(pair) == false) {
            pairings.add(pair);
            display.provisonallyPair(coordone, coordtwo);
            orientation.add(1);
            return 0;
        }
        else if (pairings.contains(pair) == true) {
            display.vetoProvisionalPairing(coordone, coordtwo);
            display.eraseProvisionalPairing(coordone, coordtwo);
            return 1;
        }
    return 1;
}

            
int tryPairing2(DominosaDisplay& display, Grid<int>& board, Map<coord, int>& numbers, Set<pair<int, int> >& pairings, Vector<int>& orientation, int numColumns) {
    int col = pairings.size();
    if (col < numColumns) {
        coord coordthree, coordfour, coordfive, coordsix;
            coordthree.row = 0;
            coordthree.col = col;
            coordfour.row = 0;
            coordfour.col = col + 1;
            coordfive.row = 1;
            coordfive.col = col;
            coordsix.row = 1;
            coordsix.col = col + 1;
            int oneupper = numbers.get(coordthree);
            int twoupper = numbers.get(coordfour);
            int onelower = numbers.get(coordfive);
            int twolower = numbers.get(coordsix);
    
        pair<int, int> pair1, pair2;
    
            if (oneupper <= twoupper) {
                pair1 = make_pair(oneupper, twoupper);
            }
            else if (twoupper < oneupper) {
                pair1 = make_pair(twoupper, oneupper);
            }
            if (onelower <= twolower) {
                pair2 = make_pair(onelower, twolower);
            }
            else if (twolower < onelower) {
                pair2 = make_pair(twolower, onelower);
            }
            
            if (col == numColumns - 1) {// stops it going out of bounds
                
                return 1;
            }
        
            if (pair1 == pair2) {// if the pairs are the same only one will get insterted into the set and everything will go out of sync
                display.vetoProvisionalPairing(coordthree, coordfour);
                display.vetoProvisionalPairing(coordfive, coordsix);
                display.eraseProvisionalPairing(coordthree, coordfour);
                display.eraseProvisionalPairing(coordfive, coordsix);
                return 1;
            }
            else if (pairings.contains(pair1) == false && pairings.contains(pair2) == false) {
                pairings.add(pair1);
                pairings.add(pair2);
                orientation.add(3);// add numbers to orientation- has to be two different numbers otherwise it'll repeat the delete when rewinding
                orientation.add(2);
                display.provisonallyPair(coordthree, coordfour);
                display.provisonallyPair(coordfive, coordsix);
                return 0;
            }
            else if (pairings.contains(pair1) == false && pairings.contains(pair2) == true) {
                display.provisonallyPair(coordthree, coordfour);
                display.vetoProvisionalPairing(coordfive, coordsix);
                display.eraseProvisionalPairing(coordthree, coordfour);
                display.eraseProvisionalPairing(coordfive, coordsix);
                return 1;
            }
            else if (pairings.contains(pair1) == true && pairings.contains(pair2) == false) {
                display.vetoProvisionalPairing(coordthree, coordfour);
                display.provisonallyPair(coordfive, coordsix);
                display.eraseProvisionalPairing(coordthree, coordfour);
                display.eraseProvisionalPairing(coordfive, coordsix);
                return 1;
            }
            else {
                display.vetoProvisionalPairing(coordthree, coordfour);
                display.vetoProvisionalPairing(coordfive, coordsix);
                display.eraseProvisionalPairing(coordthree, coordfour);
                display.eraseProvisionalPairing(coordfive, coordsix);
                return 1;
                }
            }
    return 0;
}

static void deletePairings(DominosaDisplay& display, Map<coord, int>& numbers, Set<pair<int, int> >& pairings, Vector<int>& orientation, int numColumn) {
    int col = pairings.size() - 1;
    
    if (orientation.size() > 0 && col > -1) {
        int erasor = orientation.get(orientation.size() - 1);
            if (erasor == 1) {
            
            coord coord1, coord2;
            coord1.row = 0;
            coord1.col = col;
            coord2.row = 1;
            coord2.col = col;
            int one = numbers.get(coord1);
            int two = numbers.get(coord2);
            pair<int, int> pair;
        if (one <= two) {
            pair = make_pair(one, two);
        }
        else if (two < one) {
            pair = make_pair(two, one);
        }
            pairings.remove(pair);
            orientation.remove(orientation.size() - 1);
            display.eraseProvisionalPairing(coord1, coord2);
        
    
}
        else if (erasor == 2) {
    
            coord coord3, coord4, coord5, coord6;
            coord3.row = 0;
            coord3.col = col;
            coord4.row = 0;
            coord4.col = col - 1;
            coord5.row = 1;
            coord5.col = col;
            coord6.row = 1;
            coord6.col = col - 1;
            int oneupper = numbers.get(coord3);
            int twoupper = numbers.get(coord4);
            int onelower = numbers.get(coord5);
            int twolower = numbers.get(coord6);
        
            pair <int, int> pair1, pair2;
        
        if (oneupper <= twoupper) {
                pair1 = make_pair(oneupper, twoupper);
        }
        else if (twoupper < oneupper) {
                pair1 = make_pair(twoupper, oneupper);
        }
        if (onelower <= twolower) {
                pair2 = make_pair(onelower, twolower);
        }
        else if (twolower < onelower) {
                pair2 = make_pair(twolower, onelower);
        }
            pairings.remove(pair1);
            pairings.remove(pair2);
            orientation.remove(orientation.size() - 1);
            orientation.remove(orientation.size() - 1);
            display.eraseProvisionalPairing(coord3, coord4);
            display.eraseProvisionalPairing(coord5, coord6);
        }
    }
}