#include #include #include #include #include #include using namespace std; // nodes expanded by UCS without B&B int Nodes_Expanded = 0; // nodes expnded by UCS with B&B // This is set to 1 as we do not look increment the count immediately for the head node int Nodes_Expanded2 = 1; struct Cell { // Holds information for a single cell of the chess board bool Q; int C; }; bool operator == (const Cell& lhs, const Cell& rhs) { // Operator to compare two cells and evaluate which is less than the other. if (lhs.Q == rhs.Q && lhs.C == rhs.C) return true; return false; } struct Coord{ // Structure holding row and column information on a board int r; int c; }; class Node { // Node class to store information on a board in the tree public: vector> board; vector successors; Node* parent; int cost; }; // forward declarations bool CheckGoal(vector> b); int determineScore(vector> board, int r, int c); vector AvailSpaces(vector> b); struct node_comp { // comparator to compare two nodes. used to create a minheap out of priority queue bool operator()(const Node* n1, const Node* n2) const { return n1->cost > n2->cost; } }; vector> BuildBoard(){ // builds board into a default board with no queens and no costs vector> board; vector bools; Cell cell; for (int i = 0; i < 8; i++){ for (int j = 0; j < 8; j++){ cell.Q = false; cell.C = 0; bools.push_back(cell); } board.push_back(bools); bools.clear(); } return board; } Node* UniformCostSearch(vector> b) { // UCS without Branch and Bound. // priority queue with a min comparator is nearly equivelant to a minheap priority_queue, node_comp> O; // closed vector vector closed; // start node Node * start = new Node(); start->board = b; start->cost = 0; // vector containing current node's successors vector succ1; // if no goal is found Node * k; k = new Node(); k->cost = 9999999; // push start node onto the heap O.push(start); // begin popping off heap while (O.empty() == false){ // increment nodes expanded Nodes_Expanded++; // create node n, which is the min value from the minheap Node * n; n = O.top(); // if a goal is found, return if (CheckGoal(n->board) == true && n->cost <= k->cost) return n; // remove head O.pop(); // place on closed closed.push_back(n); // find coordinates of available spaces in the next row vector availables = AvailSpaces(n->board); // for each possible successor, place this into a node and place that node into the minheap for (int i = 0; i < availables.size(); i++){ Node * next = new Node(); vector> newBoard; int row = availables[i].r; int col = availables[i].c; newBoard = n->board; newBoard[row][col].Q = true; // successor's data next->board = newBoard; next->parent = n; next->cost = n->cost+newBoard[row][col].C; // push successor onto vector of successors succ1.push_back(next); // place into heap O.push(next); } // point to successors n->successors = succ1; // clear succ1 for reuse succ1.clear(); } // return if no goal is found return k; } Node* UCSBAndB(vector> b){ // create node k to store current optimal cost Node * k = new Node(); int nodeCostBound = 999999; // see UCS priority_queue, node_comp> O; // see UCS vector>> closed; Node * start = new Node(); start->board = b; start->cost = 0; start->parent = NULL; // see UCS vector succ1; k = start; O.push(start); while (O.empty() == false) { // if the top node is greater than the costbound, we have already found the best solution. pop all remaining items off O. if (O.top()->cost > nodeCostBound) { O.pop(); } else{ Nodes_Expanded2++; Node * n; n = O.top(); O.pop(); closed.push_back(n->board); vector availables = AvailSpaces(n->board); for (int i = 0; i < availables.size(); i++){ // set row and col to corresponding available spaces' row/col values int row = availables[i].r; int col = availables[i].c; // if score of the parent plus the score of move's cost is less than the upper bound, continue to expand node. if (n->cost + n->board[row][col].C < nodeCostBound) { // create new board to store old board vector> newBoard; newBoard = n->board; // set a queen at location [row][col] newBoard[row][col].Q = true; // if the value is in the closed set, do nothing. if (find(closed.begin(), closed.end(), newBoard) != closed.end()){} // else, expand and check the node else{ // see UCS Node * next = new Node(); next->board = newBoard; next->parent = n; next->cost = n->cost + next->board[row][col].C; succ1.push_back(next); // check here if the node is a goal node if (CheckGoal(next->board) == true){ // check if the cost is below the costbound if (next->cost < nodeCostBound){ // if the cost is below the costbound, you have your target. set the optimal node to the return node, k, // and the upper bound to the optimal node's cost k = next; nodeCostBound = next->cost; } } else{ // otherwise, push this node to minheap O.push(next); } } // bunch of braces :( } } n->successors = succ1; succ1.clear(); } } return k; } bool CheckAvail(vector> board, int r, int c) { // checks availabiily of a cell on the board int countH = 1; int countV = 1; int countd1 = 1; int countd2 = 1; if (board[0][c].Q == true) countH++; if (board[1][c].Q == true) countH++; if (board[2][c].Q == true) countH++; if (board[3][c].Q == true) countH++; if (board[4][c].Q == true) countH++; if (board[5][c].Q == true) countH++; if (board[6][c].Q == true) countH++; if (board[7][c].Q == true) countH++; if (countH >= 2) return false; if (board[r][0].Q == true) countV++; if (board[r][1].Q == true) countV++; if (board[r][2].Q == true) countV++; if (board[r][3].Q == true) countV++; if (board[r][4].Q == true) countV++; if (board[r][5].Q == true) countV++; if (board[r][6].Q == true) countV++; if (board[r][7].Q == true) countV++; if (countV >= 2) return false; int pp = c; for (int ll = r; ll < 8; ll++){ if (pp < 8 && board[ll][pp].Q == true){ countd1++; } pp++; } pp = c; for (int ll = r; ll < 8; ll++){ if (pp >= 0 && board[ll][pp].Q == true){ countd2++; } pp--; } pp = c; for (int ll = r; ll >= 0; ll--){ if (pp < 8 && board[ll][pp].Q == true){ countd2++; } pp++; } pp = c; for (int ll = r; ll >= 0; ll--){ if (pp >= 0 && board[ll][pp].Q == true){ countd1++; } pp--; } if (countd1 >= 2 || countd2 >= 2 || countH > 1 || countV > 1) return false; return true; } vector AvailSpaces(vector> b){ // returns a vector containing available spaces in next row vector available; int numQueens = 0; for (int i = 0; i < 8; i++){ for (int j = 0; j < 8; j++){ if (b[i][j].Q == true) numQueens++; } } for (int k = 0; k < 8; k++){ if (CheckAvail(b, numQueens, k) == true){ Coord crd; crd.r = numQueens; crd.c = k; available.push_back(crd); } } return available; } bool CheckGoal(vector> b){ // checks if this board is a goal int Queens = 0; for (int i = 0; i < 8; i++){ for (int j = 0; j < 8; j++){ if (b[i][j].Q == true) Queens++; } } if (Queens == 8){ return true; } else{ return false; } } int main(){ vector> b1; int B = 0; b1 = BuildBoard(); /*b1[0][0].C = 2885; b1[0][1].C = 3391; b1[0][2].C = 1494; b1[0][3].C = 2404; b1[0][4].C = 981; b1[0][5].C = 1554; b1[0][6].C = 2512; b1[0][7].C = 3399; b1[1][0].C = 3208; b1[1][1].C = 3417; b1[1][2].C = 3243; b1[1][3].C = 2684; b1[1][4].C = 164; b1[1][5].C = 1352; b1[1][6].C = 2673; b1[1][7].C = 1206; b1[2][0].C = 450; b1[2][1].C = 559; b1[2][2].C = 2806; b1[2][3].C = 2632; b1[2][4].C = 344; b1[2][5].C = 2711; b1[2][6].C = 978; b1[2][7].C = 2073; b1[3][0].C = 3235; b1[3][1].C = 3437; b1[3][2].C = 3398; b1[3][3].C = 1389; b1[3][4].C = 2916; b1[3][5].C = 2816; b1[3][6].C = 2407; b1[3][7].C = 793; b1[4][0].C = 2240; b1[4][1].C = 3390; b1[4][2].C = 2322; b1[4][3].C = 2322; b1[4][4].C = 2461; b1[4][5].C = 662; b1[4][6].C = 2320; b1[4][7].C = 2661; b1[5][0].C = 346; b1[5][1].C = 1719; b1[5][2].C = 127; b1[5][3].C = 607; b1[5][4].C = 1123; b1[5][5].C = 1735; b1[5][6].C = 576; b1[5][7].C = 904; b1[6][0].C = 987; b1[6][1].C = 2834; b1[6][2].C = 3007; b1[6][3].C = 2501; b1[6][4].C = 3365; b1[6][5].C = 1578; b1[6][6].C = 422; b1[6][7].C = 1792; b1[7][0].C = 1937; b1[7][1].C = 503; b1[7][2].C = 3308; b1[7][3].C = 113; b1[7][4].C = 122; b1[7][5].C = 2289; b1[7][6].C = 1765; b1[7][7].C = 2476;*/ b1[0][0].C = 4693; b1[0][1].C = 4289; b1[0][2].C = 1853; b1[0][3].C = 2004; b1[0][4].C = 2996; b1[0][5].C = 873; b1[0][6].C = 1207; b1[0][7].C = 562; b1[1][0].C = 5053; b1[1][1].C = 1283; b1[1][2].C = 4376; b1[1][3].C = 2991; b1[1][4].C = 2473; b1[1][5].C = 3171; b1[1][6].C = 4811; b1[1][7].C = 5067; b1[2][0].C = 2883; b1[2][1].C = 4895; b1[2][2].C = 3083; b1[2][3].C = 400; b1[2][4].C = 63; b1[2][5].C = 1386; b1[2][6].C = 803; b1[2][7].C = 25; b1[3][0].C = 731; b1[3][1].C = 1844; b1[3][2].C = 2896; b1[3][3].C = 285; b1[3][4].C = 1776; b1[3][5].C = 3446; b1[3][6].C = 4350; b1[3][7].C = 4082; b1[4][0].C = 787; b1[4][1].C = 1036; b1[4][2].C = 4831; b1[4][3].C = 2796; b1[4][4].C = 855; b1[4][5].C = 3631; b1[4][6].C = 2836; b1[4][7].C = 4305; b1[5][0].C = 1357; b1[5][1].C = 1323; b1[5][2].C = 1506; b1[5][3].C = 4104; b1[5][4].C = 4184; b1[5][5].C = 3941; b1[5][6].C = 5247; b1[5][7].C = 4576; b1[6][0].C = 4429; b1[6][1].C = 3245; b1[6][2].C = 3989; b1[6][3].C = 4920; b1[6][4].C = 1640; b1[6][5].C = 2374; b1[6][6].C = 412; b1[6][7].C = 445; b1[7][0].C = 1340; b1[7][1].C = 2493; b1[7][2].C = 3970; b1[7][3].C = 685; b1[7][4].C = 2784; b1[7][5].C = 442; b1[7][6].C = 2332; b1[7][7].C = 2106; /* 2885 3391 1494 2404 981 1554 2512 3399 3208 3417 3243 2684 164 1352 2673 1206 450 559 2806 2632 344 2711 978 2073 3235 3437 3398 1389 2916 2816 2407 793 2240 3390 2322 2322 2461 662 2320 2661 346 1719 127 607 1123 1735 576 904 987 2834 3007 2501 3365 1578 422 1792 1937 503 3308 113 122 2289 1765 2476 */ cout << "Beginning Uniform Cost Search without Branch and Bound..." << endl; Node * N1 = UniformCostSearch(b1); vector> complete = N1->board; cout << "Solution: " << endl; for (int i = 0; i < 8; i++){ for (int j = 0; j < 8; j++){ if (complete[i][j].Q == true) cout << "x "; else cout << "o "; } cout << endl; } cout << "Complete: < "; for (int h = 0; h < 8; h++){ for (int u = 0; u < 8; u++){ if (complete[h][u].Q == true) cout << u + 1 << " "; } } cout << ">" << endl; cout << "Nodes Expanded: " << Nodes_Expanded << endl; cout << "Cost: " << N1->cost << endl; cout << endl; cout << "Beginning Uniform Cost Search with Branch and Bound..." << endl; Node * N2 = UCSBAndB(b1); vector> complete2 = N2->board; cout << "Solution: " << endl; for (int i = 0; i < 8; i++){ for (int j = 0; j < 8; j++){ if (complete2[i][j].Q == true) cout << "x "; else cout << "o "; } cout << endl; } cout << "Complete: < "; for (int h = 0; h < 8; h++){ for (int u = 0; u < 8; u++){ if (complete2[h][u].Q == true) cout << u+1 << " "; } } cout << ">" << endl; cout << "Nodes Expanded: " << Nodes_Expanded2 << endl; cout << "Cost: " << N2->cost << endl; return 0; }