Numerical Explorations

/*
	Author: James Pate Williams, Jr.

	Stochastic L-System to draw a plant. See "Simulating Plant Growth" by
	Marco Grubert, Crossroads, the ACM Student Magazine Issue 8.2, Winter
	2001, pages 20-27.
*/

import java.awt.*;
import java.awt.event.*;
import java.lang.*;
import java.util.*;
import javax.swing.*;

class Cursor {
	private double factor, rTheta;
	private int height, theta, width, x, x0, y, y0;

	public Cursor() {
	}

	public Cursor(int w, int h) {
		width = w;
		height = h;
		factor = Math.PI / 180.0;
		theta = 270;
		rTheta = factor * theta;
		x0 = width / 2;
		y0 = height;
		x = 0;
		y = 0;
	}

	public Cursor(int iw, int ih, int iTheta, int ix, int iy) {
		width = iw;
		height = ih;
		theta = iTheta;
		factor = Math.PI / 180.0;
		rTheta = factor * theta;
		x0 = width / 2;
		y0 = height;
		x = ix;
		y = iy;
	}

	public void F(Graphics g, int n) {
		double nX = n * Math.cos(rTheta) + x, nY = n * Math.sin(rTheta) + y;
		int X = x, Y = y;

		x = (int) nX;
		y = (int) nY;
		g.drawLine(X + x0, Y + y0, x + x0, y + y0);
	}

	public void f(Graphics g, int n) {
		double nX = n * Math.cos(rTheta) + x, nY = n * Math.sin(rTheta) + y;

		x = (int) nX;
		y = (int) nY;
		g.translate(x + x0, y + y0);
	}

	public void plus(int alpha) {
		theta = (theta - alpha) % 360;
		if (theta < 0)
			theta += 360;
		rTheta = factor * theta;
	}
	
	public void minus(int alpha) {
		theta = (theta + alpha) % 360;
		if (theta < 0)
			theta += 360;
		rTheta = factor * theta;
	}

	public void exclamation() {
		theta = (theta + 180) % 360;
		if (theta < 0)
			theta += 360;
		rTheta = factor * theta;
	}

	public int getWidth() {
		return width;
	}

	public int getHeight() {
		return height;
	}

	public int getTheta() {
		return theta;
	}

	public int getX() {
		return x;
	}

	public int getY() {
		return y;
	}

	public int getX0() {
		return x0;
	}

	public int getY0() {
		return y0;
	}
}

class PlantPanel extends JPanel {
	int depth;
	Cursor cursor = null;
	Random random = null;

	public PlantPanel(int iDepth, int iWidth, int iHeight, int seed) {
		depth = iDepth;
		cursor = new Cursor(iWidth, iHeight);
		random = new Random(seed);
	}
	
	public void lSystem1(Graphics g, int d, int depth, int n, int width, int height, 
			    int theta, int x, int y) {
		int alpha = 20;
		Cursor cursor = new Cursor(width, height, theta, x, y);
		Cursor stackCursor = null;

		if (d == depth)
			return;
		cursor.F(g, n);
		theta = cursor.getTheta();
		x = cursor.getX();
		y = cursor.getY();
		lSystem0(g, d + 1, depth, n / 2, width, height, theta, x, y);
		stackCursor = new Cursor(cursor.getWidth(), cursor.getHeight(),
			cursor.getTheta(), cursor.getX(), cursor.getY());
		stackCursor.plus(alpha);
		stackCursor.F(g, n);
		theta = stackCursor.getTheta();
		x = stackCursor.getX();
		y = stackCursor.getY();
		lSystem0(g, d + 1, depth, n / 2, width, height, theta, x, y);
		cursor.F(g, n);
		theta = cursor.getTheta();
		x = cursor.getX();
		y = cursor.getY();
		lSystem0(g, d + 1, depth, n / 2, width, height, theta, x, y);
		stackCursor = new Cursor(cursor.getWidth(), cursor.getHeight(),
			cursor.getTheta(), cursor.getX(), cursor.getY());
		stackCursor.minus(alpha);
		stackCursor.F(g, n);
		theta = stackCursor.getTheta();
		x = stackCursor.getX();
		y = stackCursor.getY();
		lSystem0(g, d + 1, depth, n / 2, width, height, theta, x, y);
		cursor.F(g, n);
		theta = cursor.getTheta();
		x = cursor.getX();
		y = cursor.getY();
		lSystem0(g, d + 1, depth, n / 2, width, height, theta, x, y);
	}

	public void lSystem2(Graphics g, int d, int depth, int n, int width, int height, 
			    int theta, int x, int y) {
		int alpha = 20;
		Cursor cursor = new Cursor(width, height, theta, x, y);
		Cursor stackCursor = null;

		if (d == depth)
			return;
		cursor.F(g, n);
		theta = cursor.getTheta();
		x = cursor.getX();
		y = cursor.getY();
		lSystem0(g, d + 1, depth, n / 2, width, height, theta, x, y);
		stackCursor = new Cursor(cursor.getWidth(), cursor.getHeight(),
			cursor.getTheta(), cursor.getX(), cursor.getY());
		stackCursor.plus(alpha);
		stackCursor.F(g, n);
		theta = stackCursor.getTheta();
		x = stackCursor.getX();
		y = stackCursor.getY();
		lSystem0(g, d + 1, depth, n / 2, width, height, theta, x, y);
		cursor.F(g, n);
		theta = cursor.getTheta();
		x = cursor.getX();
		y = cursor.getY();
		lSystem0(g, d + 1, depth, n / 2, width, height, theta, x, y);
	}

	public void lSystem3(Graphics g, int d, int depth, int n, int width, int height, 
			    int theta, int x, int y) {
		int alpha = 20;
		Cursor cursor = new Cursor(width, height, theta, x, y);
		Cursor stackCursor = null;

		if (d == depth)
			return;
		cursor.F(g, n);
		theta = cursor.getTheta();
		x = cursor.getX();
		y = cursor.getY();
		lSystem0(g, d + 1, depth, n / 2, width, height, theta, x, y);
		stackCursor = new Cursor(cursor.getWidth(), cursor.getHeight(),
			cursor.getTheta(), cursor.getX(), cursor.getY());
		stackCursor.minus(alpha);
		stackCursor.F(g, n);
		theta = stackCursor.getTheta();
		x = stackCursor.getX();
		y = stackCursor.getY();
		lSystem0(g, d + 1, depth, n / 2, width, height, theta, x, y);
	}

	public void lSystem0(Graphics g, int d, int depth, int n, int width, int height, 
			    int theta, int x, int y) {
		double r = random.nextDouble();

		if (d == depth)
			return;
		if (r <= 0.33) 
			lSystem1(g, d, depth, n, width, height, theta, x, y);
		else if (r <= 0.66)
			lSystem2(g, d, depth, n, width, height, theta, x, y);
		else
			lSystem3(g, d, depth, n, width, height, theta, x, y);
		theta = cursor.getTheta();
		x = cursor.getX();
		y = cursor.getY();
		lSystem0(g, d + 1, depth, n / 2, width, height, theta, x, y);
	}

	public void lSystem(Graphics g, int d, int depth, int n, int width, int height, 
			    int theta, int x, int y) {
		lSystem0(g, d, depth, n, width, height, theta, x, y);
	}

	public void paintComponent(Graphics g) {
		int n = 120;
		int width = cursor.getWidth(), height = cursor.getHeight();
		int theta = cursor.getTheta(), x0 = cursor.getX0(), y0 = cursor.getY0();
		
		lSystem(g, 0, depth, n, width, height, theta, 0, 0);
	}
}

class PlantFrame extends JFrame {
	int iHeight, iWidth;
	PlantPanel plantPanel;
	
	// step 3 - percentage size the window
	void setDesktopSize(JFrame frame, int wPerc, int hPerc) {
		Dimension screen = Toolkit.getDefaultToolkit().getScreenSize();
		iWidth = screen.width * wPerc / 100;
		iHeight = screen.height * hPerc / 100;
		frame.setSize(iWidth, iHeight);
	}
	
	// step 4 - center the window
	void centerOnScreen(JFrame frame) {
		Dimension screen = Toolkit.getDefaultToolkit().getScreenSize();
		Dimension window = frame.getSize();
		int iCenterX = screen.width / 2;
		int iCenterY = screen.height / 2;
		frame.setLocation(iCenterX - window.width / 2, iCenterY - window.height / 2);
	}
	
	public PlantFrame(int depth, int seed) {
		String title = "Plant by James Pate Williams, Jr. (c) 2001";

		setTitle(title);
		addWindowListener(new WindowAdapter() {
			public void windowClosing(WindowEvent event) {
				System.exit(0);
			}
		});
		setDesktopSize(this, 100, 100);
		centerOnScreen(this);
		Container contentPane = getContentPane();
		plantPanel = new PlantPanel(depth, iWidth, iHeight, seed);
		contentPane.add(plantPanel, BorderLayout.CENTER);
		this.show();
	}
}

class Plant {
	public static void main(String[] args) {
		if (args.length != 2) {
			System.out.println("usage: java Plant depth seed");
			System.out.println("where 5 <= depth <= 8 and seed >= 1");
			System.exit(0);
		}
		int depth = (new Integer(args[0])). intValue();
		if (depth < 5 || depth > 8) {
			System.out.println("depth not in range 5 <= depth <= 8!");
			System.exit(0);
		}
		int seed = (new Integer(args[1])).intValue();
		if (seed < 1) {
			System.out.println("seed must be >= 1");
			System.exit(0);
		}
		PlantFrame plantFrame = new PlantFrame(depth, seed);
	}
}

/*
	Author:	James Pate Williams, Jr. (c) 2000

	Min-conflicts hill-climbing applied to N-Queens problem.
	Wallace and Freuder's algorithm with an unbiased
	preprocessor.
*/

#include <stdlib.h>
#include <time.h>
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;

const bool Debug = true;
const int MaxRepairs = 1000000;

int conflicts(int a, int i, int n, vector<int> &Q) {
	int b, c = 0, j;

	for (j = 0; j < n; j++) {
		b = Q[j];
		if (i != j && a != - 1 && b != - 1) {
			if (a == b) c++;
			if (i - j == a - b || i - j == b - a) c++;
		}
	}
	return c;
}

int constraintsViolated(vector<int> &Q) {
	int a, b, c = 0, i, j, n;
	
	n = Q.size();
	for (i = 0; i < n; i++) {
		a = Q[i];
		for (j = 0; j < n; j++) {
			b = Q[j];
			if (i != j && a != - 1 && b != - 1) {
				if (a == b) c++;
				if (i - j == a - b || i - j == b - a) c++;
			}
		}
	}
	return c;
}

int mchcAlgorithm(int n, vector<int> &compoundLabel) {
	bool commit, firstLoop = true;
	double p = 0.1, r;
	int c, i, index, j, minConflict, v;
	int repairs = 0;
	vector<int> conflict, domain, position;

	// preprocessing
	for (i = 0; i < n; i++) {
		conflict.erase(conflict.begin(), conflict.end());
		for (j = 0; j < n; j++)
			domain.push_back(j);
		for (commit = false, j = 0; !commit && j < n; j++) {
			v = domain[rand() % domain.size()];
			vector<int>::iterator vIterator = find(domain.begin(), domain.end(), v);
			domain.erase(vIterator);
			compoundLabel[i] = v;
			c = conflicts(v, i, i, compoundLabel);
			conflict.push_back(c);
			if (c == 0) commit = true;
		}
		if (!commit) {
			minConflict = conflict[0];
			for (j = 1; j < n; j++)
				if (conflict[j] < minConflict) minConflict = conflict[j];
			position.erase(position.begin(), position.end());
			for (j = 0; j < n; j++)
				if (minConflict == conflict[j]) position.push_back(j);
			compoundLabel[i] = position[rand() % position.size()];	
		}
	}
	for (;;) {
		conflict.erase(conflict.begin(), conflict.end());
		for (i = 0, j = 0; i < n; i++) {
			c = conflicts(compoundLabel[i], i, n, compoundLabel);
			conflict.push_back(c);
			j += c;
		}
		if (firstLoop) {
			cout << "conflicts after preprocessor: " << j << endl;
			firstLoop = false;
		}
		if (j == 0) break;
		position.erase(position.begin(), position.end());
		for (i = 0; i < n; i++)
			if (conflict[i] >= 1) position.push_back(i);
		index = position[rand() % position.size()];
		r = (double) rand() / RAND_MAX;
		if (r <= p)
			compoundLabel[index] = rand() % n;
		else {
			for (i = 0; i < n; i++) {
				compoundLabel[index] = i;
				conflict[i] = conflicts(i, index, n, compoundLabel);
				repairs++;
				if (repairs == MaxRepairs) return repairs;
			}
			minConflict = conflict[0];
			for (i = 1; i < n; i++)
				if (conflict[i] < minConflict) minConflict = conflict[i];
			position.erase(position.begin(), position.end());
			for (i = 0; i < n; i++)
				if (minConflict == conflict[i]) position.push_back(i);
			compoundLabel[index] = position[rand() % position.size()];
		}
	}
	return repairs;
}

void printSolution(vector<int> &solution) {
	char hyphen[256];
	int column, i, i4, n = solution.size(), row;

	if (n <= 10) {
		for (i = 0; i < n; i++) {
			i4 = i * 4;
			hyphen[i4 + 0] = '-';
			hyphen[i4 + 1] = '-';
			hyphen[i4 + 2] = '-';
			hyphen[i4 + 3] = '-';
		}
		i4 = i * 4;
		hyphen[i4 + 0] = '-';
		hyphen[i4 + 1] = '\n';
		hyphen[i4 + 2] = '\0';
		for (row = 0; row < n; row++) {
			column = solution[row];
			cout << hyphen;
			for (i = 0; i < column; i++)
				cout << "|   ";
			cout << "| Q ";
			for (i = column + 1; i < n; i++)
				cout << "|   ";
			cout << '|' << endl;
		}
		cout << hyphen;
	}
	else
		for (row = 0; row < n; row++)
			cout << row << ' ' << solution[row] << endl;
}

int main(int argc, char *argv[]) {
	if (argc != 2) {
		cout << "usage: " << argv[0] << " numberOfQueens" << endl;
		exit(1);
	}
	int n = atoi(argv[1]), repairs;
	double seconds;
	clock_t time0, time1;
	vector<int> solution(n, - 1);
	srand(time(NULL));
	time0 = clock();
	repairs = mchcAlgorithm(n, solution);
	time1 = clock();
	time1 -= time0;
	seconds = (double) time1 / CLOCKS_PER_SEC;
	if (Debug) printSolution(solution);
	cout << "Repairs: " << repairs << endl;
	cout << "seconds: " << seconds << endl;
	return 0;
}			
		

/*
*  NQueensBruteForce.cpp
*  NQueensBruteForce
*
*	Brute force determination of the total number of
*	solutions of the n-queens constraint satisfaction
*	problem (CSP). Order n! complexity algorithm.
*
*  Created by James Pate Williams, Jr. on 12/10/07.
*  Copyright 2007. All rights reserved.
*
*/

#include "stdafx.h"
#include <stdlib.h>
#include <time.h>
#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>

int ConstraintViolations(std::vector<int> &Q, int &cvCount) {
	int a, b, cv = 0, i, j, n;

	n = Q.size();

	for (i = 0; i < n; i++) {

		a = Q[i];

		for (j = 0; j < n; j++) {
			b = Q[j];

			if (i != j && a != -1 && b != -1) {

				if (a == b)
					cv++;

				if (i - j == a - b || i - j == b - a)
					cv++;
			}
		}
	}

	cvCount++;
	return cv;
}

void PrintSolution(std::vector<int> &solution) {
	char hyphen[256];
	int column, i, i4, n = solution.size(), row;

	if (n <= 10) {
		for (i = 0; i < n; i++) {
			i4 = i * 4;
			hyphen[i4 + 0] = '-';
			hyphen[i4 + 1] = '-';
			hyphen[i4 + 2] = '-';
			hyphen[i4 + 3] = '-';
		}
		i4 = i * 4;
		hyphen[i4 + 0] = '-';
		hyphen[i4 + 1] = '\n';
		hyphen[i4 + 2] = '\0';
		for (row = 0; row < n; row++) {
			column = solution[row];
			std::cout << hyphen;
			for (i = 0; i < column; i++)
				std::cout << "|   ";
			std::cout << "| Q ";
			for (i = column + 1; i < n; i++)
				std::cout << "|   ";
			std::cout << '|' << std::endl;
		}
		std::cout << hyphen;
	}
	else
		for (row = 0; row < n; row++)
			std::cout << row << ' ' << solution[row] << std::endl;
}

int main(int argc, char * const argv[])
{
	if (argc != 3) {
		std::cout << "usage: " << argv[0] << " numberOfQueens print";
		std::cout << std::endl;
		exit(-1);
	}

	int numberOfQueens = atoi(argv[1]);

	if (numberOfQueens <= 0) {
		std::cout << "numberOfQueens must be positive" << std::endl;
		exit(-1);
	}

	int count = 0, i, cvCount = 0, print = atoi(argv[2]), space = 0;
	clock_t clock0;
	std::vector<int> queenVector;

	clock0 = clock();
	for (i = 0; i < numberOfQueens; i++)
		queenVector.push_back(i);

	do {

		int cv = ConstraintViolations(queenVector, cvCount);

		if (cv == 0) {
			count++;

			if (print == 1) {
				PrintSolution(queenVector);
				std::cout << std::endl;
			}
		}
		space++;
	} while (std::next_permutation(
		queenVector.begin(),
		queenVector.end(),
		std::less<int>()));

	double seconds = (double)(clock() - clock0) / CLOCKS_PER_SEC;

	std::cout << "search space size     = " << space << std::endl;
	std::cout << "number of con checks  = " << cvCount << std::endl;
	std::cout << "number of solutions   = " << count << std::endl;
	std::cout << "total time (seconds)  = " << seconds << std::endl;
	return 0;
}

Basic Exchange
PRNG Seed             = 1
Number of Samples     = 10000
Maximum Sample Value  = 10000
Number of Experiments = 100
Runtimes in Microseconds
Minimum Runtime       = 134039
Maximum Runtime       = 143654
Mean Runtime          = 137164
Median Runtime        = 136788

Standard Exchange
PRNG Seed             = 1
Number of Samples     = 10000
Maximum Sample Value  = 10000
Number of Experiments = 100
Runtimes in Microseconds
Minimum Runtime       = 318753
Maximum Runtime       = 389181
Mean Runtime          = 330273
Median Runtime        = 328034

Insertion Sort
PRNG Seed             = 1
Number of Samples     = 10000
Maximum Sample Value  = 10000
Number of Experiments = 100
Runtimes in Microseconds
Minimum Runtime       = 48089
Maximum Runtime       = 54204
Mean Runtime          = 49308
Median Runtime        = 49116

Selection Sort
PRNG Seed             = 1
Number of Samples     = 10000
Maximum Sample Value  = 10000
Number of Experiments = 100
Runtimes in Microseconds
Minimum Runtime       = 224979
Maximum Runtime       = 348275
Mean Runtime          = 233022
Median Runtime        = 229386

Simple Shifting
PRNG Seed             = 1
Number of Samples     = 10000
Maximum Sample Value  = 10000
Number of Experiments = 100
Runtimes in Microseconds
Minimum Runtime       = 115351
Maximum Runtime       = 131739
Mean Runtime          = 117297
Median Runtime        = 116714

Heap Sort
PRNG Seed             = 1
Number of Samples     = 10000
Maximum Sample Value  = 10000
Number of Experiments = 100
Runtimes in Microseconds
Minimum Runtime       = 2408
Maximum Runtime       = 2800
Mean Runtime          = 2477
Median Runtime        = 2454

Quick Sort
PRNG Seed             = 1
Number of Samples     = 10000
Maximum Sample Value  = 10000
Number of Experiments = 100
Runtimes in Microseconds
Minimum Runtime       =  838
Maximum Runtime       = 1011
Mean Runtime          =  900
Median Runtime        =  893

Singleton's Sort
PRNG Seed             = 1
Number of Samples     = 10000
Maximum Sample Value  = 10000
Number of Experiments = 100
Runtimes in Microseconds
Minimum Runtime       =  727
Maximum Runtime       =  849
Mean Runtime          =  761
Median Runtime        =  747

Counting Sort
PRNG Seed             = 1
Number of Samples     = 10000
Maximum Sample Value  = 10000
Number of Experiments = 100
Runtimes in Microseconds
Minimum Runtime       =   97
Maximum Runtime       =  122
Mean Runtime          =  103
Median Runtime        =  103

Menu
1 N-Queens Problem (Backtracking)
2 Knight's Tour Problem (Backtracking)
3 Warnsdorff Heuristic Solution
4 Print Knight Move Count Matrix
5 Exit
Option (1 - 5): 2
n = 6
seed = 1
starting row = 1
starting col = 3
ending row = 1
ending col = 3
length = 36
maximum runtime per instance in seconds = 60
Chessboard Rows and Columns = 6
Pseudo-random Number Generator Seed = 1
Row = 1
Col = 3
Sequence Length = 36
18 29 26  9 12 35
27  8 19  0 25 10
30 17 28 11 34 13
 7 20  1 32  3 24
16 31 22  5 14 33
21  6 15  2 23  4
Current Runtime in Seconds = 50.747000
Menu
1 N-Queens Problem (Backtracking)
2 Knight's Tour Problem (Backtracking)
3 Warnsdorff Heuristic Solution
4 Print Knight Move Count Matrix
5 Exit
Option (1 - 5):

Menu
1 N-Queens Problem (Backtracking)
2 Knight's Tour Problem (Backtracking)
3 Warnsdorff Heuristic Solution
4 Print Knight Move Count Matrix
5 Exit
Option (1 - 5): 3
n = 6
seed = 1
starting row = 1
starting col = 3
ending row = 1
ending col = 3
length = 36
maximum runtime per instance in seconds = 60
Chessboard Rows and Columns = 6
Pseudo-random Number Generator Seed = 1
Row = 1
Col = 3
Sequence Length = 36
18 29 26  9 12 35
27  8 19  0 25 10
30 17 28 11 34 13
 7 20  1 32  3 24
16 31 22  5 14 33
21  6 15  2 23  4
Current Runtime in Seconds = 46.983000
Menu
1 N-Queens Problem (Backtracking)
2 Knight's Tour Problem (Backtracking)
3 Warnsdorff Heuristic Solution
4 Print Knight Move Count Matrix
5 Exit
Option (1 - 5):

// KnightsTourCPP.cpp : Defines the entry point for the console application.
//
/*
Author:	James Pate Williams, Jr. (c) 2000 - 2022
Backtracking algorithm applied to the N-Queens CSP.
Algorithm from _Foundations of Constraint Satisfaction_
by E. P. K. Tsang Chapter 2 page 37.
Warnsdorff's solution by James Pate Williams, Jr.
*/

#include "stdafx.h"
#include <windows.h>
#include <limits.h>
#include <stdlib.h>
#include <synchapi.h>
#include <time.h>
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <ostream>
#include <string>
#include <vector>
#include <chrono>
using namespace std::chrono;
using namespace std;

// https://www.geeksforgeeks.org/measure-execution-time-function-cpp/

const int lBufferLength = 8192;

class Pair {
public:
	int row, col;
	static int n;
	Pair() { row = col = -1; };
	Pair(int row, int col) {
		this->row = row;
		this->col = col;
	};
	inline friend bool operator ==(
		const Pair lt,
		const Pair rt) {
		return
			lt.row == rt.row &&
			lt.col == rt.col;
	};
	inline friend bool operator <(
		const Pair lt,
		const Pair rt) {
		int lval = lt.row * n + lt.col;
		int rval = rt.row * n + rt.col;
		return lval < rval;
	};
	inline friend bool operator >(
		const Pair lt,
		const Pair rt) {
		int lval = lt.row * n + lt.col;
		int rval = rt.row * n + rt.col;
		return lval > rval;
	};
	inline static int BinarySearch(
		vector<Pair> arr, int p, int r, Pair num) {
		if (r >= p) {
			int mid = p + (r - p) / 2;
			if (arr[mid] == num)
				return mid;
			if (arr[mid] > num)
				return BinarySearch(arr, p, mid - 1, num);
			if (arr[mid] < num)
				return BinarySearch(arr, mid + 1, r, num);
		}
		return -1;
	};
	inline static bool BinarySearchSTL(vector<Pair> solution, Pair test) {
		return binary_search(solution.begin(), solution.end(), test);
	};
	inline static bool LinearSearch(vector<Pair> solution, Pair test, int& index) {
		for (int i = 0; i < (int)solution.size(); i++) {
			if (test == solution[i]) {
				index = i;
				return true;
			}
		}
		index = -1;
		return false;
	};
	inline static bool FindSTL(vector<Pair> solution, Pair test, int& index)
	{
		vector<Pair>::iterator sit = find(solution.begin(), solution.end(), test);
		index = sit - solution.begin();
		return sit != solution.end();
	};
};

int Pair::n = 6;

class Board {
public:
	ofstream file;
	bool warnsdorff, writeToFile;
	char* buffer;
	double currentRuntime, cumulativeRuntime;
	int bufferLength;
	int cumulativeCount, length, n;
	int startingRow, startingCol;
	int endingRow, endingCol;
	int maxRuntimeSeconds;
	unsigned int seed;
	bool** marked;
	int** legalMoveCount;
	vector<int> unlabeled;
	vector<Pair> compoundLabel;
	vector<Pair> Dx;
	vector<Pair> solution;
	Board(
		bool warnsdorff, 
		bool writeToFile,
		char* buffer,
		int bufferLength,
		int n,
		int startingRow, 
		int startingCol,
		int endingRow,
		int endingCol,
		int length,
		int maxRuntimeSeconds,
		unsigned int seed) {
		this->warnsdorff = warnsdorff;
		this->writeToFile = writeToFile;
		this->buffer = buffer;
		this->bufferLength = bufferLength;
		this->n = n;
		this->startingRow = startingRow;
		this->startingCol = startingCol;
		this->endingRow = endingRow;
		this->endingCol = endingCol;
		this->length = length;
		this->maxRuntimeSeconds = maxRuntimeSeconds;
		this->seed = seed;
		Initialization();
		currentRuntime = 0;
		cumulativeCount = 0;
		cumulativeRuntime = 0;
	}
	~Board() {
		if (marked != NULL) {
			for (int i = 0; i < n; i++)
				delete[] marked[i];
			delete[] marked;
		}
		if (legalMoveCount != NULL) {
			for (int i = 0; i < n; i++)
				delete[] legalMoveCount[i];
			delete[] legalMoveCount;
		}
	}
	vector<Pair> GetLegalKnightMoves(
		int i, int j);
	void Initialization();
	int KTconstraintsViolated(Pair pair);
	bool KTBacktrackingSolution(
		int count, int prevx, int prevy,
		vector<int> unlabeled,
		vector<Pair>& compounLabel,
		vector<Pair> Dx,
		vector<Pair>& solution);
	void DoBTSolution(
		int row, int col,
		HANDLE hBTMutex);
	void Board::GetPossibleMoveCountMatrix();
	void PrintPossibleMoveCountMatrix();
	bool WarnsdorffSolution(
		int count, int prevx, int prevy,
		vector<int> unlabeled,
		vector<Pair>& compoundLabel,
		vector<Pair> Dx,
		vector<Pair>& solution);
	void DoWarnsdorffSolution(
		int row, int col,
		HANDLE hWDMutex);
	void PrintPairVector();
	bool WriteBoardDataToFile(
		bool writeSolution, int row, int col);
};

vector<Pair> Board::GetLegalKnightMoves(int i, int j)
{
	int count = 0;
	Pair pair;
	vector<Pair> legal;
	// quadrant 1
	if (i + 1 < n && j + 2 < n)
	{
		if (!marked[i + 1][j + 2])
		{
			pair.row = i + 1;
			pair.col = j + 2;
			legal.push_back(pair);
		}
	}
	if (i + 2 < n && j + 1 < n)
	{
		if (!marked[i + 2][j + 1])
		{
			pair.row = i + 2;
			pair.col = j + 1;
			legal.push_back(pair);
		}
	}
	// quadrant 2
	if (i - 1 >= 0 && j + 2 < n)
	{
		if (!marked[i - 1][j + 2])
		{
			pair.row = i - 1;
			pair.col = j + 2;
			legal.push_back(pair);
		}
	}
	if (i - 2 >= 0 && j + 1 < n)
	{
		if (!marked[i - 2][j + 1])
		{
			pair.row = i - 2;
			pair.col = j + 1;
			legal.push_back(pair);
		}
	}
	// quadrant 3
	if (i - 1 >= 0 && j - 2 >= 0)
	{
		if (!marked[i - 1][j - 2])
		{
			pair.row = i - 1;
			pair.col = j - 2;
			legal.push_back(pair);
		}
	}
	if (i - 2 >= 0 && j - 1 >= 0)
	{
		if (!marked[i - 2][j - 1])
		{
			pair.row = i - 2;
			pair.col = j - 1;
			legal.push_back(pair);
		}
	}
	// quadrant 4
	if (i + 1 < n && j - 2 >= 0)
	{
		if (!marked[i + 1][j - 2])
		{
			pair.row = i + 1;
			pair.col = j - 2;
			legal.push_back(pair);
		}
	}
	if (i + 2 < n && j - 1 >= 0)
	{
		if (!marked[i + 2][j - 1])
		{
			pair.row = i + 2;
			pair.col = j - 1;
			legal.push_back(pair);
		}
	}
	return legal;
}

void Board::Initialization() {
	if (marked == NULL) {
		marked = new bool* [n];
		for (int i = 0; i < n; i++) {
			marked[i] = new bool[n];
		}
	}
	if (legalMoveCount == NULL) {
		legalMoveCount = new int* [n];
		for (int i = 0; i < n; i++) {
			legalMoveCount[i] = new int[n];
		}
	}
	if (warnsdorff)
		GetPossibleMoveCountMatrix();
	srand(seed);
	unlabeled.clear();
	compoundLabel.clear();
	Dx.clear();
	solution.clear();
	for (int i = 0; i < n * n; i++)
		unlabeled.push_back(i);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			Pair move;
			move.row = i;
			move.col = j;
			marked[i][j] = false;
			Dx.push_back(move);
		}
	}
}

int Board::KTconstraintsViolated(Pair pair) {
	int cv = 0;
	int row = pair.row;
	int col = pair.col;
	int xi = row, yi = col;

	for (int i = 0; i < (int)compoundLabel.size(); i++)
	{
		int x = compoundLabel[i].row;
		int y = compoundLabel[i].col;
		int r1 = x + 1, r2 = x + 2, r3 = x - 1, r4 = x - 2;
		int c1 = y + 1, c2 = y + 2, c3 = y - 1, c4 = y - 2;
		if (r1 < n && xi == r1 && c1 < n && yi == c1 ||
			r1 < n && xi == r1 && c2 < n && yi == c2 ||
			r1 < n && xi == r1 && c3 >= 0 && yi == c3 ||
			r1 < n && xi == r1 && c4 >= 0 && yi == c4 ||
			r2 < n && xi == r2 && c1 < n && yi == c1 ||
			r2 < n && xi == r2 && c2 < n && yi == c2 ||
			r2 < n && xi == r2 && c3 >= 0 && yi == c3 ||
			r2 < n && xi == r2 && c4 >= 0 && yi == c4 ||
			r3 >= 0 && xi == r3 && c1 < n && yi == c1 ||
			r3 >= 0 && xi == r3 && c2 < n && yi == c2 ||
			r3 >= 0 && xi == r3 && c3 >= 0 && yi == c3 ||
			r3 >= 0 && xi == r3 && c4 >= 0 && yi == c4 ||
			r4 >= 0 && xi == r4 && c1 < n && yi == c1 ||
			r4 >= 0 && xi == r4 && c2 < n && yi == c2 ||
			r4 >= 0 && xi == r4 && c3 >= 0 && yi == c3 ||
			r4 >= 0 && xi == r4 && c4 >= 0 && yi == c4)
		{
			if (marked[xi][yi])
				cv++;
		}
	}
	return cv;
}

bool Board::KTBacktrackingSolution(
	int count, int prevx, int prevy,
	vector<int> unlabeled,
	vector<Pair>& compounLabel,
	vector<Pair> Dx,
	vector<Pair>& solution)
{
	bool done, found, result;
	int i, x, y;
	Pair v;
	vector<Pair> legal;

	if (count == 0)
	{
		v.row = prevx;
		v.col = prevy;
		marked[prevx][prevy] = true;
		if (!Dx.empty()) {
			vector<Pair>::iterator dit = find(
				Dx.begin(), Dx.end(), v);
			if (dit != Dx.end())
				Dx.erase(dit);
		}
		if (!unlabeled.empty()) {
			vector<int>::iterator uit = find(
				unlabeled.begin(), unlabeled.end(), 0);
			if (uit != unlabeled.end())
				unlabeled.erase(uit);
		}
		compoundLabel.push_back(v);
		count++;
	}
	legal = GetLegalKnightMoves(
		prevx, prevy);
	while (!legal.empty())
	{
		x = rand() % legal.size();
		for (i = 0; i < (int)unlabeled.size(); i++)
		{
			if (x == unlabeled[i])
			{
				y = i;
				break;
			}
		}
		vector<int>::iterator uit = find(
			unlabeled.begin(), unlabeled.end(), y);
		if (uit != unlabeled.end()) {
			unlabeled.erase(uit);
		}
		done = false;
		do {
			v = legal[x];
			if (!marked[v.row][v.col]) {
				marked[v.row][v.col] = true;
			}
			int cv = KTconstraintsViolated(v);
			if (cv > 0) {
				found = binary_search(compoundLabel.begin(), compoundLabel.end(), v);
				if (!found) {
					vector<Pair>::iterator cit = find(
						compoundLabel.begin(), compoundLabel.end(), v);
					if (cit == compoundLabel.end())
						compoundLabel.push_back(v);
					vector<Pair>::iterator lit = find(
						legal.begin(), legal.end(), v);
					if (lit != legal.end()) {
						legal.erase(lit);
					}
					vector<Pair>::iterator dit = find(
						Dx.begin(), Dx.end(), v);
					if (dit != Dx.end())
						Dx.erase(dit);
					marked[v.row][v.col] = true;
					prevx = v.row;
					prevy = v.col;
					done = true;
				}
				if (compoundLabel.size() == length)
				{
					for (i = 0; i < (int)compoundLabel.size(); i++)
						solution.push_back(compoundLabel[i]);
					return true;
				}
				result = KTBacktrackingSolution(
					count, prevx, prevy,
					unlabeled, compoundLabel, Dx, solution);
				if (result)
					return result;
			}
		} while (!Dx.empty() && !legal.empty() && !done);
	}
	Pair move;
	prevx = compoundLabel[compoundLabel.size() - 1].row;
	prevy = compoundLabel[compoundLabel.size() - 1].col;
	move.row = prevx;
	move.col = prevy;
	marked[prevx][prevy] = false;
	vector<Pair>::iterator cit = find(
		compoundLabel.begin(), compoundLabel.end(), move);
	if (cit != compoundLabel.end()) {
		compoundLabel.erase(cit);
	}
	return false;
}

void Board::DoBTSolution(
	int row, int col,
	HANDLE hBTMutex) {
	int count = 0;
	int prevx = row;
	int prevy = col;
	startingRow = row;
	startingCol = col;
	bool io = false, bt = false;
	auto start = high_resolution_clock::now();
	bt = KTBacktrackingSolution(
		count, prevx, prevy,
		unlabeled, compoundLabel,
		Dx, solution);
	auto stop = high_resolution_clock::now();
	auto duration = duration_cast<milliseconds>(stop - start);
	currentRuntime = (double)duration.count() / 1.0e3;
	if (bt)
		io = WriteBoardDataToFile(true, row, col);
	else
		io = WriteBoardDataToFile(false, row, col);
	cumulativeCount++;
	cumulativeRuntime += currentRuntime;
	ReleaseMutex(hBTMutex);
}

void Board::GetPossibleMoveCountMatrix() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			vector<Pair> possible = GetLegalKnightMoves(
				i, j);
			legalMoveCount[i][j] = possible.size();
		}
	}
}

void Board::PrintPossibleMoveCountMatrix()
{
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			std::cout << legalMoveCount[i][j] << " ";
		}
		std::cout << endl;
	}
}

void Board::PrintPairVector() {
	int** matrix = new int* [n];
	for (int i = 0; i < n; i++)
		matrix[i] = new int[n];
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
			matrix[i][j] = -1;
	}
	bool done = (int)solution.size() == n * n;
	if (done) {
		for (int i = 0, count = 0; i < (int)solution.size(); count++, i++)
		{
			Pair pair = solution[i];
			std::cout << "(" << setw(2) << pair.row << ", ";
			std::cout << setw(2) << pair.col << ")" << " ";
			if ((count + 1) % n == 0)
				std::cout << endl;
			matrix[pair.row][pair.col] = count;
		}
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
				std::cout << setw(2) << matrix[i][j] << " ";
			std::cout << endl;
		}
	}
	else {
		for (int i = 0, count = 0; i < (int)compoundLabel.size(); count++, i++)
		{
			Pair pair = compoundLabel[i];
			std::cout << "(" << setw(2) << pair.row << ", ";
			std::cout << setw(2) << pair.col << ")" << " ";
			if ((i + 1) % n == 0)
				std::cout << endl;
		}
		std::cout << endl;
	}
	if (matrix != NULL) {
		for (int i = 0; i < n; i++)
			delete[] matrix[i];
		delete[] matrix;
	}
}

bool Board::WarnsdorffSolution(
	int count, int prevx, int prevy,
	vector<int> unlabeled,
	vector<Pair>& compoundLabel,
	vector<Pair> Dx,
	vector<Pair>& solution) {
	bool done, found, result;
	int i;
	Pair v;
	vector<Pair> legalMove, nextMoveVector, nextMove;

	if (count == 0)
	{
		prevx = startingRow;
		prevy = startingCol;
		v.row = prevx;
		v.col = prevy;
		marked[v.row][v.col] = true;
		if (!Dx.empty()) {
			vector<Pair>::iterator dit = find(
				Dx.begin(), Dx.end(), v);
			if (dit != Dx.end())
				Dx.erase(dit);
		}
		if (!unlabeled.empty()) {
			vector<int>::iterator uit = find(
				unlabeled.begin(), unlabeled.end(), 0);
			if (uit != unlabeled.end())
				unlabeled.erase(uit);
		}
		compoundLabel.push_back(v);
		count++;
	}
	legalMove = GetLegalKnightMoves(
		prevx, prevy);
	while (!legalMove.empty())
	{
		int min = INT_MAX;
		nextMoveVector.clear();
		for (int k = 0; k < (int)legalMove.size(); k++) {
			if (legalMoveCount[legalMove[k].row][legalMove[k].col] < min) {
				min = legalMoveCount[legalMove[k].row][legalMove[k].col];
				nextMoveVector.push_back(legalMove[k]);
			}
		}
		vector<int> index;
		index.clear();
		for (int k = 0; k < (int)nextMoveVector.size(); k++) {
			int number = legalMoveCount[nextMoveVector[k].row][nextMoveVector[k].col];
			if (number == min) {
				index.push_back(k);
			}
		}
		int r = rand() % index.size();
		v = nextMoveVector[r];
		done = false;
		do {
			if (!marked[v.row][v.col]) {
				marked[v.row][v.col] = true;
				nextMove.push_back(v);
			}
			int sum = 0;
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (marked[i][j])
						sum++;
				}
			}
			int cv = KTconstraintsViolated(v);
			if (cv > 0) {
				found = binary_search(compoundLabel.begin(), compoundLabel.end(), v);
				if (!found) {
					vector<Pair>::iterator cit = find(
						compoundLabel.begin(), compoundLabel.end(), v);
					if (cit == compoundLabel.end())
						compoundLabel.push_back(v);
					vector<Pair>::iterator lit = find(
						legalMove.begin(), legalMove.end(), v);
					if (lit != legalMove.end()) {
						legalMove.erase(lit);
					}
					vector<Pair>::iterator dit = find(
						Dx.begin(), Dx.end(), v);
					if (dit != Dx.end())
						Dx.erase(dit);
					marked[v.row][v.col] = true;
					prevx = v.row;
					prevy = v.col;
					done = true;
				}
				if (compoundLabel.size() == length)
				{
					for (i = 0; i < (int)compoundLabel.size(); i++)
						solution.push_back(compoundLabel[i]);
					return true;
				}
				result = WarnsdorffSolution(
					count, prevx, prevy, unlabeled,
					compoundLabel, Dx, solution);
				if (result)
					return result;
			}
		} while (!Dx.empty() && !legalMove.empty() && !done);
	}
	Pair move;
	prevx = compoundLabel[compoundLabel.size() - 1].row;
	prevy = compoundLabel[compoundLabel.size() - 1].col;
	move.row = prevx;
	move.col = prevy;
	marked[prevx][prevy] = false;
	vector<Pair>::iterator cit = find(
		compoundLabel.begin(), compoundLabel.end(), move);
	if (cit != compoundLabel.end()) {
		compoundLabel.erase(cit);
	}
	return false;
}

void Board::DoWarnsdorffSolution(
	int row, int col,
	HANDLE hWDMutex) {
	int count = 0;
	int prevx = row;
	int prevy = col;
	startingRow = row;
	startingCol = col;
	bool io = false, ws = false;
	auto start = high_resolution_clock::now();
	Initialization();
	ws = WarnsdorffSolution(
		count, prevx, prevy,
		unlabeled, compoundLabel,
		Dx, solution);
	auto stop = high_resolution_clock::now();
	auto duration = duration_cast<milliseconds>(stop - start);
	currentRuntime = (double)duration.count() / 1.0e3;
	if (ws)
		io = WriteBoardDataToFile(true, row, col);
	else
		io = WriteBoardDataToFile(false, row, col);
	cumulativeCount++;
	cumulativeRuntime += currentRuntime;
	ReleaseMutex(hWDMutex);
}

bool Board::WriteBoardDataToFile(
	bool writeSolution, int row, int col) {
	char newLine[2] = { '\n', '\0' };
	errno_t err;
	if (strlen(buffer) == 0)
		strcpy_s(buffer, bufferLength, "Chessboard Rows and Columns = ");
	else
		strcat_s(buffer, bufferLength, "Chessboard Rows and Columns = ");
	char nBuf[64] = { '\0' };
	err = _itoa_s(n, nBuf, 10);
	strcat_s(buffer, bufferLength, nBuf);
	strcat_s(buffer, bufferLength, newLine);
	strcat_s(buffer, bufferLength, "Pseudo-random Number Generator Seed = ");
	err = _itoa_s((int)seed, nBuf, 10);
	strcat_s(buffer, bufferLength, nBuf);
	strcat_s(buffer, bufferLength, newLine);
	strcat_s(buffer, bufferLength, "Row = ");
	err = _itoa_s(row, nBuf, 10);
	strcat_s(buffer, bufferLength, nBuf);
	strcat_s(buffer, bufferLength, newLine);
	strcat_s(buffer, bufferLength, "Col = ");
	err = _itoa_s(col, nBuf, 10);
	strcat_s(buffer, bufferLength, nBuf);
	strcat_s(buffer, bufferLength, newLine);
	strcat_s(buffer, bufferLength, "Sequence Length = ");
	err = _itoa_s(length, nBuf, 10);
	strcat_s(buffer, bufferLength, nBuf);
	strcat_s(buffer, bufferLength, newLine);
	if (writeSolution && solution.size() == n * n)
	{
		int** matrix = new int* [n];
		for (int i = 0; i < n; i++)
			matrix[i] = new int[n];
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
				matrix[i][j] = -1;
		}
		for (int i = 0, count = 0; i < (int)solution.size(); count++, i++)
		{
			Pair pair = solution[i];
			int r = pair.row;
			int c = pair.col;
			matrix[pair.row][pair.col] = count;
		}
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++) {
				string space = " ";
				if (matrix[i][j] < 10)
					err = strcat_s(buffer, bufferLength, space.c_str());
				err = _itoa_s(matrix[i][j], nBuf, 10);
				err = strcat_s(buffer, bufferLength, nBuf);
				err = strcat_s(buffer, bufferLength, space.c_str());
			}
			strcat_s(buffer, bufferLength, newLine);
		}
		strcat_s(buffer, bufferLength, "Current Runtime in Seconds = ");
		string cr = to_string(currentRuntime);
		strcat_s(buffer, bufferLength, cr.c_str());
		strcat_s(buffer, bufferLength, newLine);
		if (matrix != NULL) {
			for (int i = 0; i < n; i++)
				delete[] matrix[i];
			delete[] matrix;
		}
	}
	return true;
}

typedef struct Data
{
	int row, col;
	Board* board;
	DWORD dwWaitMS;
} DATA, * PDATA;

DWORD WINAPI BTThreadCode(LPVOID lpParam)
{
	Data* pData = (Data*)lpParam;
	HANDLE hBTMutex = CreateMutex(NULL, FALSE, NULL);

	if (hBTMutex != NULL)
	{
		pData->board->DoBTSolution(
			pData->row,
			pData->col,
			hBTMutex);
		DWORD err = WaitForSingleObject(hBTMutex, pData->dwWaitMS);
		CloseHandle(hBTMutex);
	}
	return 0;
}

DWORD WINAPI WDThreadCode(LPVOID lpParam)
{
	Data* pData = (Data*)lpParam;
	HANDLE hWDMutex = CreateMutex(NULL, FALSE, NULL);

	if (hWDMutex != NULL)
	{
		pData->board->DoBTSolution(
			pData->row,
			pData->col,
			hWDMutex);
		DWORD err = WaitForSingleObject(
			hWDMutex, pData->dwWaitMS);
		CloseHandle(hWDMutex);
	}
	return 0;
}

int NQconstraintsViolated(vector<int>& Q) {
	int a, b, c = 0, i, j, n;

	n = Q.size();
	for (i = 0; i < n; i++) {
		a = Q[i];
		for (j = 0; j < n; j++) {
			b = Q[j];
			if (i != j && a != -1 && b != -1) {
				if (a == b) c++;
				if (i - j == a - b || i - j == b - a) c++;
			}
		}
	}
	return c;
}

bool NQBacktrack(
	vector<int> unlabeled,
	vector<int> compoundLabel,
	vector<int>& solution) {
	bool result;
	int i, j, v, x;
	vector<int> Dx(compoundLabel.size());

	if (unlabeled.empty()) {
		for (i = 0; i < (int)compoundLabel.size(); i++)
			solution[i] = compoundLabel[i];
		return true;
	}
	for (i = 0; i < (int)compoundLabel.size(); i++)
		Dx[i] = i;
	// pick a random variable from unlabeled array
	i = rand() % unlabeled.size();
	x = unlabeled[i];
	do {
		// pick a random value from domain of x
		j = rand() % Dx.size();
		v = Dx[j];
		vector<int>::iterator vIterator = find(Dx.begin(), Dx.end(), v);
		Dx.erase(vIterator);
		compoundLabel[x] = v;
		if (NQconstraintsViolated(compoundLabel) == 0) {
			vIterator = find(unlabeled.begin(), unlabeled.end(), x);
			unlabeled.erase(vIterator);
			result = NQBacktrack(unlabeled, compoundLabel, solution);
			if (result) return result;
			unlabeled.push_back(x);
		}
		else
			compoundLabel[x] = -1;
	} while (!Dx.empty());
	return false;
}

void PrintNQSolution(vector<int>& solution) {
	char hyphen[256] = { 0 };
	int column, i, i4, n = solution.size(), row;

	if (n <= 10) {
		for (i = 0; i < n; i++) {
			i4 = i * 4;
			hyphen[i4 + 0] = '-';
			hyphen[i4 + 1] = '-';
			hyphen[i4 + 2] = '-';
			hyphen[i4 + 3] = '-';
		}
		i4 = i * 4;
		hyphen[i4 + 0] = '-';
		hyphen[i4 + 1] = '\n';
		hyphen[i4 + 2] = '\0';
		for (row = 0; row < n; row++) {
			column = solution[row];
			std::cout << hyphen;
			for (i = 0; i < column; i++)
				std::cout << "|   ";
			std::cout << "| Q ";
			for (i = column + 1; i < n; i++)
				std::cout << "|   ";
			std::cout << '|' << endl;
		}
		std::cout << hyphen;
	}
	else
		for (row = 0; row < n; row++)
			std::cout << row << ' ' << solution[row] << endl;
	std::cout << endl;
}

int main(int argc, char* argv[]) {
	std::cout.setf(ios::fixed, ios::floatfield);
	std::cout.setf(ios::showpoint);
	while (true) {
		bool valid;
		int i, length, n, option;
		int srow = 0, scol = 0;
		int erow = 0, ecol = 0;
		int maxRuntimeSeconds = 0;
		unsigned int seed;
		std::cout << "Menu" << endl;
		std::cout << "1 N-Queens Problem (Backtracking)" << endl;
		std::cout << "2 Knight's Tour Problem (Backtracking)" << endl;
		std::cout << "3 Warnsdorff Heuristic Solution" << endl;
		std::cout << "4 Print Knight Move Count Matrix" << endl;
		std::cout << "5 Exit" << endl;
		std::cout << "Option (1 - 5): ";
		cin >> option;
		if (option >= 5)
			return 0;
		valid = false;
		while (!valid) {
			valid = true;
			std::cout << "n = ";
			cin >> n;
			while (n < 5 || n > 8) {
				std::cout << "n must be >= 5 and <= 8" << endl;
				std::cout << "n = ";
				cin >> n;
			}
			if (option != 4) {
				std::cout << "seed = ";
				cin >> seed;
				while (seed < 1) {
					std::cout << "seed must be >= 1" << endl;
					std::cout << "seed = ";
					cin >> seed;
				}
			}
			if (option == 2 || option == 3) {
				std::cout << "starting row = ";
				cin >> srow;
				while (srow < 0 || srow > 7) {
					std::cout << "starting row must be >= 0 and <= 9" << endl;
					std::cout << "starting row = ";
					cin >> srow;
				}
				std::cout << "starting col = ";
				cin >> scol;
				while (scol < 0 || scol > 7) {
					std::cout << "starting col must be >= 0 and <= 9" << endl;
					std::cout << "starting col = ";
					cin >> scol;
				}
				std::cout << "ending row = ";
				cin >> erow;
				while (erow < 0 || erow > 7) {
					std::cout << "starting row must be >= 0 and <= 7" << endl;
					std::cout << "starting row = ";
					cin >> erow;
				}
				std::cout << "ending col = ";
				cin >> ecol;
				while (ecol < 0 || ecol > 7) {
					std::cout << "ending col must be >= 0 and <= 7" << endl;
					std::cout << "ending col = ";
					cin >> ecol;
				}
			}
			if (option == 2 || option == 3) {
				std::cout << "length = ";
				cin >> length;
				while (length < 25 || length > 64)
				{
					std::cout << "length must be >= 25 and <= 64" << endl;
					std::cout << "length = ";
					cin >> length;
				}
				if (n == 5 && length < 25) {
					std::cout << "Invalid length value for given n" << endl;
					std::cout << "length  must be <= 25" << endl;
					valid = false;
				}
				else if (n == 6) {
					if (length > 36) {
						std::cout << "Invalid length value for given n" << endl;
						std::cout << "length must be <= 36" << endl;
						valid = false;
					}
				}
				else if (n == 7) {
					if (length > 49) {
						std::cout << "Invalid length value for given n" << endl;
						std::cout << "length must be <= 49" << endl;
						valid = false;
					}
				}
				else if (n == 8) {
					if (length > 64) {
						std::cout << "Invalid length value for given n" << endl;
						std::cout << "length must be <= 64" << endl;
						valid = false;
					}
				}
				std::cout << "maximum runtime per instance in seconds = ";
				cin >> maxRuntimeSeconds;
				while (maxRuntimeSeconds <= 0) {
					std::cout << "maximum runtime > 0" << endl;
					std::cout << "maximum runtime per instance in seconds = ";
					cin >> maxRuntimeSeconds;
				}
			}
		}
		if (option == 1) {
			auto start = high_resolution_clock::now();
			vector<int> compoundLabel(n, -1), solution(n, -1), unlabeled(n);
			for (i = 0; i < n; i++)
				unlabeled[i] = i;
			if (NQBacktrack(unlabeled, compoundLabel, solution))
				PrintNQSolution(solution);
			else
				std::cout << "Problem has no solution" << endl;
			auto stop = high_resolution_clock::now();
			auto duration = duration_cast<microseconds>(stop - start);
			std::cout << "Runtime: " << setprecision(6)
				<< (double)duration.count() / 1.0e6 << " seconds" << endl;
		}
		else if (option == 2) {
			string filename = "Chronological Backtracking Results.txt";
			ofstream file;
			file.open(filename.c_str(), ios::ate);
			Pair::n = n;
			for (int i = srow; i <= erow; i++) {
				for (int j = scol; j <= ecol; j++) {
					char lBuffer[lBufferLength] = { 0 };
					Board* board = new Board(
						true,
						true,
						lBuffer,
						lBufferLength,
						n,
						srow,
						scol,
						erow,
						ecol,
						length,
						maxRuntimeSeconds,
						seed);
					Data* pBTData = new Data();
					DWORD dwThreadId;
					pBTData->row = i;
					pBTData->col = j;
					pBTData->board = board;
					pBTData->dwWaitMS = maxRuntimeSeconds * 1000;
					HANDLE hBTThread = CreateThread(
						NULL,			    // default security attributes
						0,					// use default stack size  
						BTThreadCode,		// thread function name
						pBTData,			// argument to thread function 
						0,			        // use default creation flags 
						&dwThreadId);		// returns the thread identifier
					if (hBTThread != NULL)
					{
						WaitForSingleObject(
							hBTThread, maxRuntimeSeconds * 1000);
						CloseHandle(hBTThread);
					}
					file << lBuffer;
					std::cout << lBuffer;
				}
			}
		}
		else if (option == 3) {
			string filename = "Warnsdorff Heuristic Results.txt";
			ofstream file;
			file.open(filename.c_str(), ios::ate);
			Pair::n = n;
			for (int i = srow; i <= erow; i++) {
				for (int j = scol; j <= ecol; j++) {
					char lBuffer[lBufferLength] = { 0 };
					Board* board = new Board(
						true,
						true,
						lBuffer,
						lBufferLength,
						n,
						srow,
						scol,
						erow,
						ecol,
						length,
						maxRuntimeSeconds,
						seed);
					Data* pWDData = new Data();
					DWORD dwThreadId;
					pWDData->row = i;
					pWDData->col = j;
					pWDData->board = board;
					pWDData->dwWaitMS = maxRuntimeSeconds * 1000;
					HANDLE hWDThread = CreateThread(
						NULL,			    // default security attributes
						0,					// use default stack size  
						WDThreadCode,		// thread function name
						pWDData,			// argument to thread function 
						0,			        // use default creation flags 
						&dwThreadId);		// returns the thread identifier
					if (hWDThread != NULL)
					{
						WaitForSingleObject(
							hWDThread, maxRuntimeSeconds * 1000);
						CloseHandle(hWDThread);
					}
					file << lBuffer;
					std::cout << lBuffer;
				}
			}
		}
		else if (option == 4) {
			Board board(
				true,
				true,
				NULL,
				0,
				n,
				0,
				0,
				0,
				0,
				0,
				0,
				1);
			board.GetPossibleMoveCountMatrix();
			board.PrintPossibleMoveCountMatrix();
		}
	}
	return 0;
}