Help modifying recursive function

Question

Given a canvas, let's say 10x10, and given 3 rectangles/squares.

Canvas = 10x10

Rectangle 1 = 2x2 Rectangle 2 = 3x3 Rectangle 3 = 2x4

I've created a recursive function that loops every position of every rectangle on the canvas, and it works fine. (I've included the function below incase anyone wants to see it but I don't think it's necessary).

We can see that rectangle 1 and 2 are non rotatable, IE, if you rotate either of them 90 degrees essentially they are the same shape. However rectangle 3 is rotatable.

How do I change/construct the loop/recurisve function so that it loops every position of every rectangle, along with every possible rotation?

The aim is to loop through every possible fitting of the shapes on the canvas.

Thanks for any help!

Sub recurse(ByVal startPoint As Integer)

    Dim x As Integer
    Dim y As Integer
    Dim validSolution As Boolean = isSolutionValid()
    Dim loopXTo As Integer
    Dim loopYTo As Integer
    Dim solutionRating As Integer

    'If parent nodes create invalid solution, we can skip (375 iterations from 1,600 iterations saving)
    If validSolution = True Then

        If (startPoint = 0) Then
            loopXTo = Math.Floor((canvasCols - squareObjects(startPoint).sqRows()) / 2)    '576 iterations from 1,680 iterations
            loopYTo = Math.Floor((canvasRows - squareObjects(startPoint).sqCols) / 2)       '31,104 iterations from 90,720 iterations
        Else
            loopXTo = canvasCols - squareObjects(startPoint).sqRows
            loopYTo = canvasRows - squareObjects(startPoint).sqCols

        End If

        'Loop all positions on canvas
        For x = 0 To loopXTo
            For y = 0 To loopYTo

                'Set coords of square
                squareObjects(startPoint).setSquareCords(x, y)

                'Phyiscally place it in canvas
                placeSquareOnCanvas(x, y, squareObjects(startPoint).sqRows, squareObjects(startPoint).sqCols)

                'Recursive, get next square
                If (startPoint + 1 < totalSquares) Then
                    recurse(startPoint + 1)
                Else
                    validSolution = isSolutionValid()

                    'Is solution valud
                    If (validSolution = True) Then
                        solutions = solutions + 1
                    End If

                    iterations = iterations + 1

                    'Response.Write("<br /><b>Iteration " & iterations & "</b>")
                    If (validSolution) Then

                        'Rate solution, record if best
                        solutionRating = rateSolution()
                        If solutionRating > bestCellSaving Then
                            bestCellSaving = solutionRating
                            copySolution()
                        End If
                        'Response.Write(" <span style='color:green'> <B>VALID SOLUTION</B></span> (" & rateSolution() & ")")
                    End If
                    'printCanvas(canvas)

                End If

                squareObjects(startPoint).removeSquare(canvas)

            Next
        Next
    End If

End Sub

Answer 1

If the canvas is always a square then you don't need to change much. The result for the rotated rectangle 3 is the same as for the unrotated, except the origin of the Canvas is different. Imagine leaving the Rectangle 3 unrotated and rotating the canvas 90 degrees in the other direction. This means that you should be able to use some maths on the same results to get your answer.

Answer 2

Put your (x,y) coordinate loop in its own function. Then call the (x,y) coordinate loop on a rectangle of WxH, and then call it again on the rotated rectangle HxW.

Alternatively you can put the branching on the two rotations of your rectangle inside the (x,y) loop, after both coordinates have been picked, but before you make the recursive call.

In both cases you will need to be careful about whether your rotation causes the rectangle to exceed the height or width of your bounding box.

Answer 3

Can't you simply scan the list of shapes and for those that are rectangles (SizeX != SizeY) add a cloned rectangle with { SizeX = source.SizeY, SizeY = source.SizeX } (eg.: rotated rectangle)?

That would of course mean to do the loops twice (one for the unrotated list of shapes and one for the rotated one).

=> doing something like

squareObjects(startPoint) = squareObjects(startPoint).Rotate();
recurse(startPoint);

Answer 4

If you extract the loops in a separate routine the solution emerges relatively easily.

I have changed the validSolution logic a bit to make the code shorter - now we don't call recurse if the solution is invalid and we don't need to check for isSolutionValid() at the beginning of recurse(). These changes make counting the iterations harder so I removed that code, but it should be possible to add it later.

The recurse() routine without the last "If" statement should behave exactly as your code. The last "If" statement essentially performs the loops for a rotated rectangle.

I am not sure how removeSquare() is implemented, but it may need to know the orientation to be able to work correctly.

Sub recurse(ByVal startPoint As Integer)
    Dim loopXTo As Integer
    Dim loopYTo As Integer
    If (startPoint = 0) Then
        loopXTo = Math.Floor((canvasCols - squareObjects(startPoint).sqRows) / 2)
        loopYTo = Math.Floor((canvasRows - squareObjects(startPoint).sqCols) / 2)
    Else
        loopXTo = canvasCols - squareObjects(startPoint).sqRows
        loopYTo = canvasRows - squareObjects(startPoint).sqCols
    End If
    fitSqare(loopXTo, loopYTo, False)
    If (squareObjects(startPoint).sqCols <> squareObjects(startPoint).sqRows) Then
        fitSqare(loopYTo, loopXTo, True)
    End If
End Sub

Sub fitSquare(ByVal loopXTo As Integer, ByVal loopYTo As Integer, ByVal rotate As Boolean)
    Dim x As Integer
    Dim y As Integer
    Dim solutionRating As Integer
    Dim validSolution As Boolean

    'Loop all positions on canvas
    For x = 0 To loopXTo
        For y = 0 To loopYTo
            'Set coords of square
            squareObjects(startPoint).setSquareCords(x, y)

            'Phyiscally place it in canvas
            If (rotate) Then
                placeSquareOnCanvas(x, y, squareObjects(startPoint).sqCols, squareObjects(startPoint).sqRows)
            Else
                placeSquareOnCanvas(x, y, squareObjects(startPoint).sqRows, squareObjects(startPoint).sqCols)
            End If

            validSolution = isSolutionValid()
            'Is solution valud
            If (validSolution) Then
                'Recursive, get next square
                If (startPoint + 1 < totalSquares) Then
                    recurse(startPoint + 1)
                Else
                    solutions = solutions + 1
                    'Rate solution, record if best
                    solutionRating = rateSolution()
                    If solutionRating > bestCellSaving Then
                        bestCellSaving = solutionRating
                        copySolution()
                    End If
                End If
            End If
            squareObjects(startPoint).removeSquare(canvas) 'removeSquare may require additional work to handle rotated state
        Next
    Next
End Sub