#include <iostream>
using namespace std;

int main(void) {

	// generate all permutations
	int perms[2520][8], p = 0;
	for(int a = 0; a < 7; a++) {
		for(int b = a + 1; b < 8; b++) {
			for(int c = 0; c < 7; c++) {
				if (c == a || c == b) continue;
				for(int d = c + 1; d < 8; d++) {
					if (d == a || d == b) continue;
					for(int e = 0; e < 7; e++) {
						if (e == a || e == b || e == c || e == d) continue;
						for(int f = e + 1; f < 8; f++) {
							if (f == a || f == b || f == c || f == d) continue;
							for(int g = 0; g < 7; g++) {
								if (g == a || g == b || g == c || g == d || g == e || g == f) continue;
								for(int h = g + 1; h < 8; h++) {
									if (h == a || h == b || h == c || h == d || h == e || h == f) continue;
									perms[p][0] = a;
									perms[p][1] = b;
									perms[p][2] = c;
									perms[p][3] = d;
									perms[p][4] = e;
									perms[p][5] = f;
									perms[p][6] = g;
									perms[p][7] = h;
									p++;
								}
							}
						}
					}
				}
			}
		}
	}
	if (p != 2520) cout << "WHOOPS! Created " << p << " permutations" << endl;

	// initialize first shift to first permutation and second shift to null
	int perm[8], shift = 1, count = 0, max = 0; perm[0] = 0; perm[1] = -1;
	
	// loop
	do {
		// display status count
		if ((++count & 0xFFFF) == 0) cout << count << endl;
		
		// display solution (or new leader)
		if (shift > max && perm[shift] >= 0) {
			max = shift;
			if (shift == 7) {
				cout << endl << "SOLUTION:" << endl;
			} else {
				cout << endl << "NEW MAX SHIFTS = " << (shift + 1) << ":" << endl;
			}
			for(int i = 0; i <= shift; i++) {
				cout << "  ";
				for(int j = 0; j < 4; j++) {
					cout << " " << (perms[perm[i]][j*2]+1) << (perms[perm[i]][j*2+1]+1);
				}
				cout << endl;
			}
		}

		// build history of all shifts up to this one
		int which_booth[8][8];
		int which_partner[8][8];
		int which_double_shift[8][2];
		for(int i = 0; i < 8; i++) { which_double_shift[i][0] = which_double_shift[i][1] = -1; }
		for(int s = 0; s < shift; s++) {
			for(int i = 0; i < 8; i++) {
				int a = perms[perm[s]][i], b = perms[perm[s]][i^1];
				which_booth[a][s] = i >> 1;
				for(int t = (s >> 2) << 2; t < s; t++) {
					if (which_booth[a][t] == which_booth[a][s]) {
						cout << "WHOOPS! " << a << " worked booth " << which_booth[a][s] << " on shifts " << t << " and " << s << endl;
					}
				}
				which_partner[a][s] = b;
				for(int t = 0; t < s; t++) {
					if (which_partner[a][t] == which_partner[a][s]) {
						if (which_double_shift[a][0] == -1) {
							which_double_shift[a][0] = t;
							which_double_shift[a][1] = s;
						} else {
							cout << "WHOOPS! " << a << " worked with " << b << " on shifts " << t << " and " << s
								<< " after working with " << which_partner[a][which_double_shift[a][0]]
								<< " on shifts " << which_double_shift[a][0] << " and " << which_double_shift[a][1] << endl;
						}
					}
				}
			}
		}

		// find next allowable permutation for this shift
		for(perm[shift]++; perm[shift] < 2520; perm[shift]++) {
			bool allowed = true;
			for(int i = 0; allowed && i < 8; i++) {
				int a = perms[perm[shift]][i], b = perms[perm[shift]][i^1];
				for(int t = (shift >> 2) << 2; allowed && t < shift; t++) {
					if (which_booth[a][t] == (i >> 1)) allowed = false;
				}
				for(int t = 0; allowed && t < shift; t++) {
					if (which_partner[a][t] == b && which_double_shift[a][0] >= 0) allowed = false;
				}
			}
			if (allowed) break;
		}
		
		if (perm[shift] < 2520) {
			// found a valid permutation for this shift, try the next shift
			if (shift < 7) perm[++shift] = -1;
		} else {
			// no more permutations for this shift, go back and fint one for the previous shift
			shift--;
		}

	} while (perms[perm[1]][0] == 2 && (perms[perm[1]][1] == 3 || perms[perm[1]][1] == 4));

	cout << endl << "NO MORE SOLUTIONS" << endl;

	return 0;
}