// 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;
}
Numerical Explorations 