MrExcel Consulting
Your One Stop for Excel Tips & Solutions

Brute Force Solving in Excel


November 22, 2017 - by Bill Jelen

Brute Force Solving in Excel

Using Excel to Solve Any Complex Model

Watch the Video!

Topics covered in the video below.

Lev is commissioner of a competitive swim league. He writes: "I am the commissioner of a swim league. There are eight teams this year. Each team hosts one meet and is the home team. A meet will have 4 or 5 teams. How to arrange the schedule so every team swims against every other team twice? In the past, when we had 5, 6, or 7 teams, I could solve it by pressing F9 until close. But this year, with 8 teams, it is not coming out."

One of the constraints is that some pools only offer 4 lanes, so you can only have 4 teams when that pool hosts the gala. For other pools, they might have 5, 6, or more lanes, but the ideal meet will have the home team plus four others.

My suggestion: Press F9 faster! To help with that: develop a "measure of closeness" in your model. That way, when you press F9, you can keep your eye on one number. When you find a "better" solution than the best you've found, save that as the intermediate best solution.


Steps Specific to the Swim Problem

  • List the 8 home teams across the top.
  • How many ways to fill the other 4 lanes?
  • List all of the ways.
  • How many ways to fill the other 3 lanes (for small venues?). List all of the ways.
  • Use RANDBETWEEN(1,35) to choose teams for each match.

Note that there are 35^8 possible ways to arrange the season (2.2 trillion). It would be "impossible" to do them all with a home PC. If there were only 4000 possibilities, you could do them all, and that is a video for another day. But with 2.2 trillion possibilities, randomly guessing is more likely to find solutions.

Develop a Measure of Closeness

In the swim scenario, the most important thing is Does every team swim against every other team twice?

Take the current 8 random numbers and use formulas to plot out all of the match-ups. List the 28 possible match ups. Use COUNTIF to see how many times each match-up is happening with the current random numbers. Count how many are 2 or greater. The goal is to get this number to 28.

Secondary Goal: There are 28 matchups. Each needs to happen twice. That is 56 matchups that have to happen. With 8 pools and 6 with five lanes, you will have 68 matchups occur. That means some teams will swim against other teams 3 times and possibly 4 times. Secondary goal: Make sure as few teams as possible have 4 match-ups. Tertiary goal: Minimize the Max.

Slow Way to Solve This

Press F9. Look at the result. Press F9 a few times to see what results you are getting. When you get a high result, save the 8 inputs and the three output variables. Keep pressing F9 until you get a better result. Save that one by recording the 8 input cells and the 3 result cells.

Macro to Save the Current Result

This macro saves the results to the next row.

Sub SaveThis()
    NR = Range("Z1048576").End(xlUp).Row + 1
    Cells(NR, 26).Resize(1, 11).Value = Array(Range("c8").Value, _
      Range("D8").Value, Range("E8").Value, Range("F8").Value, _
      Range("G8").Value, Range("H8").Value, Range("I8").Value, _
      Range("J8").Value, Range("O1").Value, Range("P1").Value, _
      Range("Q1").Value)
End Sub

Macro to Press F9 Repeatedly and Check the Results

Write a macro to press F9 repeatedly, logging only "better" solutions. Have the macro stop when you get to the desired results of 28 & 0.

Sub TrySome()
    NR = Range("Z1048576").End(xlUp).Row + 1
    Ctr = Range("T1").Value
    Application.ScreenUpdating = Range("AH2").Value
    SolutionFound = False
GoAgain:
    ActiveSheet.Calculate
    Ctr = Ctr + 1
    UseIt = 0
    If Range("O1").Value > Range("AK1").Value Then
        UseIt = 1
    ElseIf Range("O1").Value = Range("AK1").Value Then
        If Range("P1").Value <= Range("AL1").Value Then
            UseIt = 1
        End If
    End If
    If UseIt = 1 Then
        If Range("O1") = 28 And Range("P1") = 0 Then
            SolutionFound = True
        End If
        Cells(NR, 26).Resize(1, 11).Value = Array(Range("c8").Value, Range("D8").Value, Range("E8").Value, Range("F8").Value, Range("G8").Value, Range("H8").Value, Range("I8").Value, Range("J8").Value, Range("O1").Value, Range("P1").Value, Range("Q1").Value)
        Range("T1").Value = Ctr
        Application.ScreenUpdating = True
        If Selection.Address = "$T$1" Then
            Cells(NR, 34).Select
        Else
            Range("T1").Select
        End If
        Application.ScreenUpdating = Range("AH2").Value
        ActiveWorkbook.Save
        NR = NR + 1
    End If
    If NR > 300 Then
        Application.ScreenUpdating = True
        Exit Sub
    End If
    If SolutionFound = True Then
        Application.ScreenUpdating = True
        Exit Sub
    End If
    If Ctr Mod 1000 = 0 Then
        Range("T1").Value = Ctr
        Application.ScreenUpdating = True
        If Selection.Address = "$T$1" Then
            Cells(NR, 34).Select
        Else
            Range("T1").Select
        End If
        Application.ScreenUpdating = Range("AH2").Value
    End If
    GoTo GoAgain
End Sub

Sidebar about ScreenUpdating

Sidebar: At first, it is "fun" to watch the iterations roll by. But you eventually realize that you might have to test millions of possibilities. Having Excel re-draw the screen slows the macro down. Use Application.ScreenUpdating = False to not repaint the screen.

Every time you get a new answer or every 1000, let Excel re-draw the screen. Problem: Excel is not redrawing the screen unless the cell pointer moves. I found that by selecting a new cell while ScreenUpdating is True, Excel would re-paint the screen. I decided to have it alternate between the Counter cell and the Best Results So Far.

Application.ScreenUpdating = True
If Selection.Address = "$T$1" Then
  Cells(NR, 34).Select
Else
  Range("T1").Select
End If
Application.ScreenUpdating = Range("AH2").Value

Alternate Solving Solutions

I considered many titles for this video: Press F9 Until Close, Guess Until Correct, Brute Force Solving, Measure of Closeness

Note that I did try using Solver to solve the problem. But Solver could not get close. It never got better than 26 teams when the goal was 28.

Also note that any solution that I get in this video is "dumb-luck". There is nothing intelligent about the solving method. For example, the macro does not say, "We should start from the best solution so far and make some micro-adjustments." Even if you geta solution that is only one number away, it blindly presses F9 again. There is likely a more intelligent way to attack the problem. But... right now... for our swim commissioner, this approach worked.

Download the Workbook

Click here to download the workbook.

Watch the video below to see how the workbook can be used.