Name of Allah, Most Gracious, Most Merciful

E Mail : [email protected]

Hosein fereidooni

Solve Maze Problem

(tortuous game)

E-Mail : Hosein Fereidooni

To My father and my mother

E Mail : [email protected]

Introduction
One of the problems of artificial intelligence problem solve tortuous games
(MAZE) is. It defines the state space has to solve a variety of ways. To solve
this problem and to explain the rules of the game 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 a unique path from the beginning to the end boards
have.
5) Just move forward and down is allowed.
6) A starting point 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.

E Mail : [email protected]

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
Algorithms for solving tortuous path is provided. This algorithm is one of the
simplest algorithms ensure that if 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.
Algorithm based on all the issues presented in this article. The program
flowchart is presented.

E Mail : [email protected]

start

Select the first row

and column array.
Add the amount
row of

Yes

The next
row is it
zero?
No
Add column value to
the current one.

My next
column is
zero?

Yes

No

The final
element is
whether the
rows and
columns?

Yes

The
route is
finished.

No
There is
no way
final.

E Mail : [email protected]

tortuous path algorithm

flowchart

Analysis Code:
It is composed of two layers:
1) Presentation layer
2) the Business
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 hide 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. Homerange 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

E Mail : [email protected]

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++)

E Mail : [email protected]

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;

E Mail : [email protected]

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);

E Mail : [email protected]

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?

E Mail : [email protected]

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.
E Mail : [email protected]

// 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 and 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 was 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();

E Mail : [email protected]

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.

E Mail : [email protected]