Can you make the code below to work as n-puzzle game by using A* algorithm? ****
ID: 3876855 • Letter: C
Question
Can you make the code below to work as n-puzzle game by using A* algorithm?
****************************************************
<!DOCTYPE html>
<head>
<title>n-Puzzle Game</title>
<script src="http://cs.tru.ca/~mlee/comp3710/Software/board_game.min.js"></script>
</head>
<body>
<h1><i>n</i>-Puzzle Game</h1>
<div id='output'></div>
</body>
<script>
var SIZE = 3; // 3 x 3 game board
var EMPTY_CELL = 0;
var MAX_NO_BOARDS = factorial(SIZE*SIZE);
var expanded_queue = new Queue(); // Queue can be used
var visited_queue = new Queue();
var initial_board = make_initial_board(SIZE); // make the initial board
print_message('Initial board = ' + initial_board);
var initial_node = create_node(initial_board, 0, null); // See below for utility functions
// create_node(board, gvalue, node)
visited_queue.push(get_id_of_node(initial_node), get_fvalue_of_node(initial_node), initial_node); // fvalue is the priority
// push(id, priority, node)
// boards are 1D arrays of tile numbers, and nodes are objects that include board, g-value, and parent node.
var board, current_board, goal_board, parent_board;
var node, current_node, goal_node, parent_node;
current_board = initial_board;
current_node = initial_node;
goal_board = [1, 2, 3, 4, 5, 6, 7, 8, 0];
var count = 0;
// While the current board is not the goal board
while (count++ <= MAX_NO_BOARDS && !is_the_goal_board(current_board))
{
/*
* Expansion
*/
// neighbor nodes
var board_0 = []; // empty array
var board_1 = [];
var board_2 = [];
var board_3 = [];
get_next_boards(current_board, board_0, board_1, board_2, board_3); // get_next_boards(): an utility function
// update expanded queue
parent_board = current_board;
parent_node = current_node;
if (board_0.length != 0 && !visited_queue.isIn(get_id_of_board(board_0))) {
node = create_node(board_0, get_gvalue_of_node(parent_node) + 1, parent_node); // current_node is the parent of the new node.
put_node_into_expanded_queue(node); // put_node_into_expanded_queue(): an utility function
}
if (board_1.length != 0 && !visited_queue.isIn(get_id_of_board(board_1))) {
node = create_node(board_1, get_gvalue_of_node(parent_node) + 1, parent_node);
put_node_into_expanded_queue(node);
}
if (board_2.length != 0 && !visited_queue.isIn(get_id_of_board(board_2))) {
node = create_node(board_2, get_gvalue_of_node(parent_node) + 1, parent_node);
put_node_into_expanded_queue(node);
}
if (board_3.length != 0 && !visited_queue.isIn(get_id_of_board(board_3))) {
node = create_node(board_3, get_gvalue_of_node(parent_node) + 1, parent_node);
put_node_into_expanded_queue(node);
}
/*
* Select next node to visit
*/
current_node = expanded_queue.getTheHighestPriorityOne();
current_board = get_board_of_node(current_node);
/*
* Visit the node
*/
visited_queue.push(get_id_of_node(node), get_fvalue_of_node(node) ,node);
}
print_message('Found the goal');
print_message('Number of visited nodes = ' + count);
print_message("");
// goal_node: found in the above while loop
goal_node = current_node;
/*
* Put the boards on the solution path into a queue
*/
var path = []; // an empty array; path: a stack to keep boards
path.push(get_board_of_node(goal_node));
node = goal_node;
while (get_parent_node_of_node(node) != null) {
node = get_parent_node_of_node(node);
path.push(get_board_of_node(node)); // push the board, not node
}
/*
* Print the boards from the initial board to the goal board
*/
print_message("Here is an optimal path from the initial board to the goal board:");
print_message('');
for (var i = path.length-1; i >= 0; i--) {
board = path.pop(); // Need to pop a board and print
for (var j = 0; j < SIZE; j++) {
var msg = '';
for (var k = 0; k < SIZE; k++)
msg += ' ' + board[j * SIZE + k];
print_message(msg);
}
print_message("");
}
/*
* End of A* algorithm
*/
/*
* Utility functions that you SHOULD to complete/implement
*/
// Create a node from a board
function create_node(board, g_value, parent_node)
{
var node = {
id: get_id_of_board(board),
board: board,
gvalue: g_value,
hvalue: get_heuristic_value(board),
fvalue: g_value + get_heuristic_value(board),
parent: parent_node // to keep the track of path from the initial board to the goal board
};
return node;
}
// The number of missed tiles
function get_heuristic_value(board)
{
var hvalue = 0;
if(current_board != null)
{
for(var i = 0; i<current_board.length; i++)
{
if(current_board[i] != 0)
if(current_board[i] != i+1)
hvalue++;
}
}
return hvalue;
}
// Check if a board is the goal board, and return true or false
function is_the_goal_board(board)
{
for(var i=0;i<board.length;i++)
{
if(board[i] != i+1)
return false;
}
return true;
}
// If the node is not in the queue, put a node into the expanded queue.
// If the node is already in the queue, you may need to update the gvalue.
function put_node_into_expanded_queue(node)
{
if (expanded_queue.get(get_id_of_node(node))) { // if it is in the queue
var node_another = expanded_queue.get(get_id_of_node(node)); // get, not pop, the node from the queue
if (get_gvalue_of_node(node) != get_gvalue_of_node(node_another)) {
expanded_queue.pop(get_id_of_node(node)); // pop
expanded_queue.push(get_id_of_node(node),get_gvalue_of_node(node), node); // push
}
}
else
expanded_queue.push(get_id_of_node(node),get_fvalue_of_node(node), node); // push
}
// Expansion from a board
// There can be two, or three, or four neighbor boards depending on the position of the empty tile.
// Find them all and save them into board_0, board_1, board_2, board_3.
function get_next_boards(board, board_0, board_1, board_2, board_3)
{
if (index_of_empty_cell(board) == 0) {
copy_board(board, board_0);
copy_board(board, board_1);
switch_two_in_board(board_0, 0, 0+1);
switch_two_in_board(board_1, 0, 0+SIZE);
}
else if (index_of_empty_cell(board) == 1) {
copy_board(board, board_0);
copy_board(board, board_1);
copy_board(board, board_2);
switch_two_in_board(board_0, 1, 1-1);
switch_two_in_board(board_1, 1, 1+1);
switch_two_in_board(board_2, 1, 1+SIZE);
}
else if (index_of_empty_cell(board) == 2) {
copy_board(board, board_0);
copy_board(board, board_1);
switch_two_in_board(board_0, 2, 2-1);
switch_two_in_board(board_1, 2, 2+SIZE);
}
else if (index_of_empty_cell(board) == 3) {
copy_board(board, board_0);
copy_board(board, board_1);
copy_board(board, board_2);
switch_two_in_board(board_0, 3, 3-SIZE);
switch_two_in_board(board_1, 3, 3+1);
switch_two_in_board(board_2, 3, 3+SIZE);
}
else if (index_of_empty_cell(board) == 4) {
copy_board(board, board_0);
copy_board(board, board_1);
copy_board(board, board_2);
copy_board(board, board_3);
switch_two_in_board(board_0, 4, 4-SIZE);
switch_two_in_board(board_1, 4, 4-1);
switch_two_in_board(board_2, 4, 4+1);
switch_two_in_board(board_3, 4, 4+SIZE);
}
else if (index_of_empty_cell(board) == 5) {
copy_board(board, board_0);
copy_board(board, board_1);
copy_board(board, board_2);
switch_two_in_board(board_0, 5, 5-SIZE);
switch_two_in_board(board_1, 5, 5-1);
switch_two_in_board(board_2, 5, 5+SIZE);
}
else if (index_of_empty_cell(board) == 6) {
copy_board(board, board_0);
copy_board(board, board_1);
switch_two_in_board(board_1, 6, 6-SIZE);
switch_two_in_board(board_0, 6, 6+1);
}
else if (index_of_empty_cell(board) == 7) {
copy_board(board, board_0);
copy_board(board, board_1);
copy_board(board, board_2);
switch_two_in_board(board_0, 7, 7-1);
switch_two_in_board(board_1, 7, 7-SIZE);
switch_two_in_board(board_2, 7, 7+1);
}
else if (index_of_empty_cell(board) == 8) {
copy_board(board, board_0);
copy_board(board, board_1);
switch_two_in_board(board_0, 8, 8-1);
switch_two_in_board(board_1, 8, 8-SIZE);
}
}
/*
* Utility functions that you can use
*/
function print_message(m)
{
document.getElementById('output').innerHTML += m + '<br>';
}
function get_id_of_board(board)
{
return board.join('');
}
function get_id_of_node(node)
{
return node.id;
}
function get_board_of_node(node)
{
return node.board;
}
function get_gvalue_of_node(node)
{
return node.gvalue;
}
function get_hvalue_of_node(node)
{
return node.hvalue;
}
function get_fvalue_of_node(node)
{
return node.fvalue;
}
function get_parent_node_of_node(node)
{
return node.parent;
}
function switch_two_in_board(board, i, j)
{
var tmp;
tmp = board[i];
board[i] = board[j];
board[j] = tmp;
}
function copy_board(board_from, board_to)
{ var i;
for (i = 0; i < board_from.length; i++)
board_to[i] = board_from[i];
}
function factorial(x)
{
if (x == 0)
return 1;
return x * factorial(x-1);
}
</script>
Explanation / Answer
// Program to print path from root node to destination node
// for N*N -1 puzzle algorithm using Branch and Bound
// The solution assumes that instance of puzzle is solvable
#include <bits/stdc++.h>
using namespace std;
#define N 3
// state space tree nodes
struct Node
{
// stores parent node of current node
// helps in tracing path when answer is found
Node* parent;
// stores matrix
int mat[N][N];
// stores blank tile cordinates
int x, y;
// stores the number of misplaced tiles
int cost;
// stores the number of moves so far
int level;
};
// Function to print N x N matrix
int printMatrix(int mat[N][N])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
printf("%d ", mat[i][j]);
printf(" ");
}
}
// Function to allocate a new node
Node* newNode(int mat[N][N], int x, int y, int newX,
int newY, int level, Node* parent)
{
Node* node = new Node;
// set pointer for path to root
node->parent = parent;
// copy data from parent node to current node
memcpy(node->mat, mat, sizeof node->mat);
// move tile by 1 postion
swap(node->mat[x][y], node->mat[newX][newY]);
// set number of misplaced tiles
node->cost = INT_MAX;
// set number of moves so far
node->level = level;
// update new blank tile cordinates
node->x = newX;
node->y = newY;
return node;
}
// botton, left, top, right
int row[] = { 1, 0, -1, 0 };
int col[] = { 0, -1, 0, 1 };
// Function to calculate the the number of misplaced tiles
// ie. number of non-blank tiles not in their goal position
int calculateCost(int initial[N][N], int final[N][N])
{
int count = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
if (initial[i][j] && initial[i][j] != final[i][j])
count++;
return count;
}
// Function to check if (x, y) is a valid matrix cordinate
int isSafe(int x, int y)
{
return (x >= 0 && x < N && y >= 0 && y < N);
}
// print path from root node to destination node
void printPath(Node* root)
{
if (root == NULL)
return;
printPath(root->parent);
printMatrix(root->mat);
printf(" ");
}
// Comparison object to be used to order the heap
struct comp
{
bool operator()(const Node* lhs, const Node* rhs) const
{
return (lhs->cost + lhs->level) > (rhs->cost + rhs->level);
}
};
// Function to solve N*N - 1 puzzle algorithm using
// Branch and Bound. x and y are blank tile coordinates
// in initial state
void solve(int initial[N][N], int x, int y,
int final[N][N])
{
// Create a priority queue to store live nodes of
// search tree;
priority_queue<Node*, std::vector<Node*>, comp> pq;
// create a root node and calculate its cost
Node* root = newNode(initial, x, y, x, y, 0, NULL);
root->cost = calculateCost(initial, final);
// Add root to list of live nodes;
pq.push(root);
// Finds a live node with least cost,
// add its childrens to list of live nodes and
// finally deletes it from the list.
while (!pq.empty())
{
// Find a live node with least estimated cost
Node* min = pq.top();
// The found node is deleted from the list of
// live nodes
pq.pop();
// if min is an answer node
if (min->cost == 0)
{
// print the path from root to destination;
printPath(min);
return;
}
// do for each child of min
// max 4 children for a node
for (int i = 0; i < 4; i++)
{
if (isSafe(min->x + row[i], min->y + col[i]))
{
// create a child node and calculate
// its cost
Node* child = newNode(min->mat, min->x,
min->y, min->x + row[i],
min->y + col[i],
min->level + 1, min);
child->cost = calculateCost(child->mat, final);
// Add child to list of live nodes
pq.push(child);
}
}
}
}
// Driver code
int main()
{
// Initial configuration
// Value 0 is used for empty space
int initial[N][N] =
{
{1, 2, 3},
{5, 6, 0},
{7, 8, 4}
};
// Solvable Final configuration
// Value 0 is used for empty space
int final[N][N] =
{
{1, 2, 3},
{5, 8, 6},
{0, 7, 4}
};
// Blank tile coordinates in initial
// configuration
int x = 1, y = 2;
solve(initial, x, y, final);
return 0;
}