Solve Maze Problem (Tortuous Game)

• Download English article project - 745.56 KB
• Download Persian article project - 635.33 KB
• Download source - 27.09 KB

Introduction

One of the problems of artificial intelligence is to solve tortuous games (MAZE). It defines the state space has to solve in a variety of ways. To solve this problem and to explain the rules of the game, I will explain the solution.

Rules of the Problem

1. This game can be defined in a finite space so that a space is used for the main board.
2. In this paper, we consider the N * N array of boards.
3. The array of rows and columns to rows and columns around the board to be considered.
4. The board can only have a unique path from the beginning to the end boards.
5. Just move forward and down is allowed.
6. A starting point has to be considered.
7. A point-to-end path is considered.
8. Back on track in this algorithm is not allowed.
9. In each case, only one of two moves are allowed.
10. The output rows and columns are allowed to be displayed in the path traveled.

Algorithmic Problem Solving

1. In this algorithm, before the first row and the column next will be checked.
2. If not, depending on the amount of rows and columns are added to the stack.
3. If the row was closed, the column is checked.
4. If the route was closed in the design of this board game has not been met and wrong. So no solution.
5. If the path was open to the current row and column stored in the stack and the algorithm examines the first level.
6. With each repeat the entire course of the algorithm is checked.
7. The output is stored in the stack are shown.

In this method, the breadth first search (BFS) is used to traverse the route. Due to the nature of the problem space of this algorithm is informed. Pseudo code solution is as follows:

Do
If next row is 0 add row
      Else
		If next column is 0 add column
        Else
If row and col is final element  Return true
Else
Return not solve

Algorithm for solving tortuous path is provided. This algorithm is one of the simplest algorithms to ensure if there is any output. In the later stages of the algorithm to return the issues that raised a few out there. To find the shortest path algorithm can also be raised.

The algorithm is based on all the issues presented in this article. The program flowchart is presented.

Analysis of Code

It is composed of two layers:

1. Presentation layer
2. Business layer

Most orders are delivered in the output layer. To observe the rules as a single Business object, layer data (Abstraction) has been created. The program for keeping track of a stack data structure is used. The rule also hides the data from the user perspective is fully respected. To access individual elements of the array access (accessor) is used.

The definition of a project and define a class called Mazebusiness. The following code defines variables needed by the stack is maintained. The row and column maintenance variable and is defined as the top of each stack. Home-range storage array is also defined.

//stack size
int SIZE = 20;

//max row and column
int max = 6;

//min row and column
int min = 0;

// int array stack row
int[] stack1 = new int[20];

//int array stack column
int[] stack2 = new int[20];

// int top of stacks and keep value col and row
int tos1, tos2, col, row;

// main board array
int[,] array = new int[6, 6];

Constructor

This class defines the initial value of zero in the constructor for the main board. Later with another method to define the elements to a desired result. The values of both arrays keep the stack is zero. Each stack is too high a value of zero. The rows and columns are defined as zero.

//constructor
// put zero in all element of main array
// set zero in stacks
//set zero top of stacks and row and column
public MazeBusiness()
{
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++)
            array[i, j] = 0;
    for (int i = 0; i <= SIZE - 1; i++)
    {
        stack1[i] = 0;
        stack2[i] = 0;
    }
    tos1 = 0;
    tos2 = 0;
    col = 0;
    row = 0;
}

CreateBoard()

The function of the elements that are not a major route changes. This path can be easily detected.

//initialize main board array
//at first set 1 around board
//set board by default values
public void CreateBoard()
{
    for (int i = 0; i < 5; i++)
    {
        array[0, i] = 1;
        array[i, 0] = 1;
        array[5, i] = 1;
        array[i, 5] = 1;
    }
    //set 1 , 2..5 element to 1
    for (int i = 2; i < 5; i++)
        array[1, i] = 1;
    //set 2 , 2..5 element to 1
    for (int i = 2; i < 5; i++)
        array[2, i] = 1;
    //set 4 , 2..5 element to 1
    for (int i = 1; i < 4; i++)
        array[4, i] = 1;
}

PrintBoard()

This function displays the original array. The output is a function of the original array to display the presentation layer can be prepared.

//return print able board at string
public string PrintBoard()
{
    string Temp = string.Empty;

    for (int i = 1; i < 5; i++)
    {
        for (int j = 1; j < 5; j++)
        Temp += "  " + array[i, j];
        Temp += "\r\n";
    }

    return Temp;
}

Pushr()

This function takes a numeric value of the input and the value stored in the stack holding the row.

//push cha in row stack
public void pushr(int cha)
{
    if (tos1 == SIZE)
    {
        return;
    }

    stack1[tos1] = cha;
  
    tos1++;
}

popr()

This function returns the value stored in stack row.

//pop from row stack
public int popr()
{
    if (tos1 == 0)
    {
        return -1;
    }
    tos1--;
    return stack1[tos1];
}

Pushc()

This function takes a numeric value and the value gained in the stack will store the holder.

//push cha in column stack
public void pushc(int chb)
{
    if (tos2 == SIZE)
    {
        return;
    }
    stack2[tos2] = chb;
    tos2++;
}

popc()

This function returns the value stored in stack row.

//pop from column stack
public int popc()
{
    if (tos2 == 0)
    {
        return -1;
    }
    tos2--;
    return stack2[tos2];
}

cpopr()

This function returns the first row stack.

//return top of row stack
public int cpopr()
{
    return stack1[tos1];
}

cpopc()

This function returns the first column stack.

//return top of column stack
public int cpopc()
{
    return stack2[tos2];
}

set()

The function of the row and column array is initialized to the starting point.

//initialize 1,1 for start
public void set()
{
    row = 1;
    col = 1;
    pushr(row);
    pushc(col);
}

Addr()

This function increases the value of the row.

// add row pointer
public void addr()
{
    row++;
}

Addc()

This function increases the value of the column.

//add column pointer
public void addc()
{
    col++;
}

minr()

This function reduces the amount of the row.

// reduce row value
public void minr()
{
    row--;
}

minc()

This function reduces the amount of the column.

//reduce column value
public void minc()
{
    col--;
}

checker()

This function checks the value of the next row. If the value was zero, then there is a path. The main board is also much lower than the marginal row columns.

// check next row element is 0?
public int checkar()
{
    int a = 0;
    a = row;
    a++;
    if ((array[a, col] == 0) && (a < max))
        return 1;
    else
        return 0;
}

checkac()

This function checks the next column. If the value was zero, then there is a path. It should also be much less than the row and column margins of the main board.

// check next column element is 0?
public int checkac()
{
    int a = 0;
    a = col;
    a++;
    if ((array[row, a] == 0) && (a < max))
        return 1;
    else
        return 0;
}

retr()

This function returns the row.

//get row value
public int retr()
{
    return row;
}

retc()

This function returns the column value.

//get column value
public int retc()
{
    return col;
}

printoutput()

This function returns the stack as the path traveled by the algorithm.

 // Print value in stack row and column
public string printOutPut()
{
    string Temp = string.Empty;
    
    for (int i = 0; tos1 != 0; i++)
        Temp += popr() + "     ,     " + popc() + "\r\n";
        
    return Temp;
}

Presentation Layer

This layer of rows and columns in the program decide the appropriate type of output data table is provided. In the first example of a Business and build on this prototype implements all operations. The variables are defined as needed.

The method CreateBoard() and set() for the main board and the amount of rows and columns is called. Two variables to keep track of the movements come in and out of the flag were created.

//create instance
MazeBusiness maze = new MazeBusiness();

//create default board
// we can change value of this method for change maze way.
maze.CreateBoard();

//print board
lblOutPut3.Text = maze.PrintBoard();

//initialize pointer
maze.set();

//define flag and  move counter
int exit = 0, counter = 0;

In the next section a while - do we have to traverse the route. In this Loop according to the requirements stated in the first article examines the way there or not? Continue to stack rows and columns in the holder route and the route was not an appropriate message displays.

//Each time a row and the column was closed and had reached the end of the array
//output is displayed
//check next row.
//check next column.
//if true add to stack.
// else return no slution.
do
{
    counter++;
    //check next row
    if (maze.checkar() == 1)
    {
        maze.addr();
        maze.pushr(maze.retr());
        maze.pushc(maze.retc());
    }
    else
        //check next column
        if (maze.checkac() == 1)
        {
            maze.addc();
            maze.pushr(maze.retr());
            maze.pushc(maze.retc());
        }
        else
            //check end of array?
            if (maze.retr() == 4 && maze.retc() == 4)
            {
                exit = 1;
                lblIsSolution.Text = "Resolved";
            }
            else
            {
                exit = 1;
                
                lblIsSolution.Text = "Not resolved";
            }
    //while() check end of array and exit flag
} while (maze.retr() != 5 && maze.retc() != 5 && exit == 0);

//print stacks value. the way of maze
lblOutPut.Text = maze.printOutPut();

//display count maze movement
lblOutPut2.Text = counter.ToString();

Output at the end of the path traveled by the first display. Also traveled in the direction of motion can be solved and whether the route is displayed. The output is as shown below: