locked
robot path .. out of magic square RRS feed

  • 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

Answers

  •  

    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

     

            path.Add(move)

     

            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

     

            path.Add(move)

     

            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