# robot path .. out of magic square • ### Question

• I would like to know if there is a robot algorithm that I can adapt . that will let my robot find its way to the outside world from a interior cell in a magic square with the least obstruction on its way out....

Example :    Order 5 magic square

1     7   18    14    25

13   24    5      6    17

10   16   12    23     4

22    3     9     20    11

19   15   21      2     8

For the robot placed in the cell with value three ... the pathway to the outside world traveling only on the x/y axis ( no diagonal travel) would be  3 > 9  > 12  > 5  > 6  > 14

*** there are 275 million order 5 magic square.  I would like a algortihm that would work for any order of square , and for any given interior cell

Thanks

Craig

Friday, April 25, 2008 7:53 PM

• It would help me if you could define "with the least obstruction on its way out..." further.  I’m assuming you want the robot to choose the route that gives it the smallest incline to go up.  This seems consistent with not going from 3 to 15, only 18 total to get out compared to the 49 total of your example.

A greedy algorithm would be exactly what you want if I am correct about what you are thinking.  It is very easy to program.  For your first move you just need to choose the smallest value from the cells above, below, and to the left and right of your current cell.  If the value is null then you have reached the outside already.  You next move is a little trickier because you don’t want to go back to where you came from.  To avoid this you need to have an array keeping track of where you have been. Then your next move is to the smallest of the three values(or less eventually) .

Here is VB .Net code that will solve your problem.

Code Snippet

Public Class Form1

Dim magicSquares(,) As Integer = New Integer(4, 4) {{"1", "13", "10", "22", "19"}, {"7", "24", "16", "3", "15"}, {"18", "5", "12", "9", "21"}, {"14", "6", "23", "20", "2"}, {"25", "17", "4", "11", "8"}}

Dim path As ArrayList = New ArrayList

Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click

Dim start As Integer() = {1, 3}

moveRobot(start)

End Sub

Private Sub moveRobot(ByVal move() As Integer)

Dim xLocation As Integer = move(0)

Dim yLocation As Integer = move(1)

Dim min As Integer

Dim minSet As Boolean = False

Dim nextMove(1) As Integer

Dim check(1) As Integer

If isInside(xLocation - 1, yLocation) Then

check(0) = xLocation - 1

check(1) = yLocation

If pathContains(check) = False Then

minSet = True

min = magicSquares(xLocation - 1, yLocation)

nextMove = check

End If

Else

robotOut()

Exit Sub

End If

If isInside(xLocation + 1, yLocation) Then

If minSet = False OrElse min > magicSquares(xLocation + 1, yLocation) Then

check(0) = xLocation + 1

check(1) = yLocation

If pathContains(check) = False Then

minSet = True

min = magicSquares(xLocation + 1, yLocation)

nextMove = check

End If

End If

Else

robotOut()

Exit Sub

End If

If isInside(xLocation, yLocation - 1) Then

If minSet = False OrElse min > magicSquares(xLocation, yLocation - 1) Then

check(0) = xLocation

check(1) = yLocation - 1

If pathContains(check) = False Then

minSet = True

min = magicSquares(xLocation, yLocation - 1)

nextMove = check

End If

End If

Else

robotOut()

Exit Sub

End If

If isInside(xLocation, yLocation + 1) Then

If minSet = False OrElse min > magicSquares(xLocation, yLocation + 1) Then

check(0) = xLocation

check(1) = yLocation + 1

If pathContains(check) = False Then

min = magicSquares(xLocation, yLocation + 1)

nextMove = check

End If

If minSet = False Then

'infinte loop

Exit Sub

End If

End If

Else

robotOut()

Exit Sub

End If

moveRobot(nextMove)

End Sub

Private Function isInside(ByVal xValue As Integer, ByVal yValue As Integer) As Boolean

Dim xMax As Integer = magicSquares.GetUpperBound(0)

Dim yMax As Integer = magicSquares.GetUpperBound(1)

If xValue >= 0 And xValue <= xMax Then

If yValue >= 0 And yValue <= yMax Then

Return True

End If

End If

Return False

End Function

Private Sub robotOut()

Dim finalPath As String = ""

For i As Integer = 0 To path.Count - 1

finalPath &= magicSquares(path(i)(0), path(i)(1)) & "->"

Next

MsgBox(finalPath & "outside")

End Sub

Private Function pathContains(ByVal val As Integer()) As Boolean

For i As Integer = 0 To path.Count - 1

If path(i)(0) = val(0) And path(i)(1) = val(1) Then

Return True

End If

Next

Return False

End Function

End Class

Sorry for no comments in the code explaining what it does.  If you have any questions let me know.

This code can easily be changed to get the values from your database and solve for them.  Just populate the magicSquare array from your database and select a start value.

Hope this helps.

-       Andrew

Sunday, April 27, 2008 6:00 AM

### All replies

• I would look into the standard A* search algorithm.  However, i think it requires that you define a goal cell.

What you describe seem pretty easy to code yourself.  It is a greedy search because you only look at the 4 connected cells, then pic the minimum, then move and recur.

What a more advanced planning algorithm will do for you is help you avoid local minima.  I don't know the motivation for your algorithm, but I assume you want to get out of the magic square with the least sum of the cells you visit.  For example, if this were a real magic square, and you started at 3, a planning algorithm would probably tell you to go: 3 > 10 > 1 > 1.  because the cost of that trip is only 15, where as with your greedy search, your trip cost would be: 49.  Do you see how looking ahead helps you get over that hump of 10 instead of 9?

1    1   18    14    25

13   1    5      6    17

10   10  12    23     4

22    3     9     20    11

19   15   21      2     8

-Ben
Saturday, April 26, 2008 1:02 PM
• It would help me if you could define "with the least obstruction on its way out..." further.  I’m assuming you want the robot to choose the route that gives it the smallest incline to go up.  This seems consistent with not going from 3 to 15, only 18 total to get out compared to the 49 total of your example.

A greedy algorithm would be exactly what you want if I am correct about what you are thinking.  It is very easy to program.  For your first move you just need to choose the smallest value from the cells above, below, and to the left and right of your current cell.  If the value is null then you have reached the outside already.  You next move is a little trickier because you don’t want to go back to where you came from.  To avoid this you need to have an array keeping track of where you have been. Then your next move is to the smallest of the three values(or less eventually) .

Here is VB .Net code that will solve your problem.

Code Snippet

Public Class Form1

Dim magicSquares(,) As Integer = New Integer(4, 4) {{"1", "13", "10", "22", "19"}, {"7", "24", "16", "3", "15"}, {"18", "5", "12", "9", "21"}, {"14", "6", "23", "20", "2"}, {"25", "17", "4", "11", "8"}}

Dim path As ArrayList = New ArrayList

Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click

Dim start As Integer() = {1, 3}

moveRobot(start)

End Sub

Private Sub moveRobot(ByVal move() As Integer)

Dim xLocation As Integer = move(0)

Dim yLocation As Integer = move(1)

Dim min As Integer

Dim minSet As Boolean = False

Dim nextMove(1) As Integer

Dim check(1) As Integer

If isInside(xLocation - 1, yLocation) Then

check(0) = xLocation - 1

check(1) = yLocation

If pathContains(check) = False Then

minSet = True

min = magicSquares(xLocation - 1, yLocation)

nextMove = check

End If

Else

robotOut()

Exit Sub

End If

If isInside(xLocation + 1, yLocation) Then

If minSet = False OrElse min > magicSquares(xLocation + 1, yLocation) Then

check(0) = xLocation + 1

check(1) = yLocation

If pathContains(check) = False Then

minSet = True

min = magicSquares(xLocation + 1, yLocation)

nextMove = check

End If

End If

Else

robotOut()

Exit Sub

End If

If isInside(xLocation, yLocation - 1) Then

If minSet = False OrElse min > magicSquares(xLocation, yLocation - 1) Then

check(0) = xLocation

check(1) = yLocation - 1

If pathContains(check) = False Then

minSet = True

min = magicSquares(xLocation, yLocation - 1)

nextMove = check

End If

End If

Else

robotOut()

Exit Sub

End If

If isInside(xLocation, yLocation + 1) Then

If minSet = False OrElse min > magicSquares(xLocation, yLocation + 1) Then

check(0) = xLocation

check(1) = yLocation + 1

If pathContains(check) = False Then

min = magicSquares(xLocation, yLocation + 1)

nextMove = check

End If

If minSet = False Then

'infinte loop

Exit Sub

End If

End If

Else

robotOut()

Exit Sub

End If

moveRobot(nextMove)

End Sub

Private Function isInside(ByVal xValue As Integer, ByVal yValue As Integer) As Boolean

Dim xMax As Integer = magicSquares.GetUpperBound(0)

Dim yMax As Integer = magicSquares.GetUpperBound(1)

If xValue >= 0 And xValue <= xMax Then

If yValue >= 0 And yValue <= yMax Then

Return True

End If

End If

Return False

End Function

Private Sub robotOut()

Dim finalPath As String = ""

For i As Integer = 0 To path.Count - 1

finalPath &= magicSquares(path(i)(0), path(i)(1)) & "->"

Next

MsgBox(finalPath & "outside")

End Sub

Private Function pathContains(ByVal val As Integer()) As Boolean

For i As Integer = 0 To path.Count - 1

If path(i)(0) = val(0) And path(i)(1) = val(1) Then

Return True

End If

Next

Return False

End Function

End Class

Sorry for no comments in the code explaining what it does.  If you have any questions let me know.

This code can easily be changed to get the values from your database and solve for them.  Just populate the magicSquare array from your database and select a start value.

Hope this helps.

-       Andrew

Sunday, April 27, 2008 6:00 AM
• Well that is the best birthday present I ever had .... I don't know what your education cost ... but it was well worth it.

Thanks a million ... I will try and apply the code and see if it works.

Sunday, April 27, 2008 8:58 PM