[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math Topics]   [Library]   [Utilities]

Problem Description

Brute Force solves a class of problems that can be represented as equations with integer solutions.  The solution must be from a predefined set of integers.  As restrictive as that sounds, there a many problems that qualify.  Examples:

Brute Force tries to solve such problems.

Background & Techniques

This is kind of a neat program.  I wrote it a few years ago when I realized that a large class of problems met the conditions described above.  The name reflects the fact that it tries to solve problems by  trial and error, or brute force.   The puzzle must be represented as a set of equations to be solved use values from a given set of integers.     I've learned a bit since then and the code would probably look different if I were to start over,  but I'll leave any extensive rewriting for the viewer, or  when I run out of other projects.    

All of the problems tested so far have solutions space of 16 or fewer digits.  16 digits have 16! (over 10 trillion) permutations representing  possible solutions,  clearly an impossible task.  Those having 10 digits however have only 10! ("only" 3.6 million) possible solutions  and can always be solved in under a minute, if a solution exists.  

Some of the features: 

The incremental  solution algorithm is original as far as I know.  It is definitely not a trivial operation,  In fact, most of the time   preparing Brute Force for publication  this week was spent understanding and commenting the code. ( I have a resolved to make better comments the next time I write code this complicated.)    The algorithm reduces the solution search space by finding solutions one equation at a time. If there are 10 variables in all equations, but equation 1 has only 4, then permutations of 4 of 10 solutions are tried.   When a solution is found,  the next equation is examined.  Any new variables introduced define a new set of permutations to be chosen from the unused solution integers.  New permutations are combined with the previous partial solution and a recursive call is made to evaluate for all equations up to the current one.  When the last equation has been solved, a solution has been found.  It will start finding solutions for the 4X4 Magic Square in a minute or so.   How many exist, or if it would find them all in our lifetime, I do not know.

Postfix expression evaluation is the other aspect of the program that deserves a little explanation.  Postfix evaluation has the operators (+,-,*,/, etc. ) placed after the required operands.   During evaluation, a "stack" is used to contain the working elements.  A stack is a type of data structure which supports last In-first out (LIFO) accessing.  This is commonly implemented by "Push" and "Pop" procedures.   Current versions of Delphi have a TStack class which I'd probably use if I were writing new code. But BruteForce uses a simple TStringlist  with list.addobject and list.delete(count-1) to push and pop equation terms. 

In building a postfix equation string, a table of priorities is used to keep things in the proper order.   Before starting,  values are assigned for all variables.   Evaluation works like this:  1) get the next element from the equation string 2) If it is a variable or a constant, push the value onto the stack else 3) if it is an operator, pop the operands off of the stack, evaluate and push the result back onto the stack.  4) If there are more terms go back to step 1.  So the postfix form of (a+1)*2=c looks like this "a1+2*c=".   If the  final result is true, the equation was satisfied.  

This is the first program posted here that uses a TTabControl component.  Tabs are used  to hold problems as they are loaded so you can switch problems by clicking on a tab.   It uses an OnChanging event exit to store the old tab problem (and save if changed), and an OnChange  exit to set up the problem for the tab clicked    

Both the source and executable zip file include a dozen or so predefined problem files.  If you find others that are interesting, let me know.

Addendum May 22, 2004:   I ran across the following problem recently in my daily Mensa® Puzzle calendar; 

It's an algebra problem, but I thought I'd try to "Brute Force" it just for fun.   Well, every Brute Force problem to date had a unique value for each variable.  This problem has at least one repeated value. which required a small modification to the program (The program did not recognize that duplicate variable values could produce duplicate solutions.  It now checks and does not report duplicates.)  A few additional problems  have popped up since last posting  so there are now  16 samples included.     

Addendum May 10, 2005: 

This problem is from my early Father's Day gift this year: "The maximum number of individual regions formed by three lines dividing a circle is seven.  The circle contains an ant colony and  each region contains between one and seven ants.  Can you place seven groups of ants in the seven regions so that for each of the lines, the total number of ants on either side are all the same?  How many solutions can you find?".  This is from Ivan Moscovich's latest puzzle book Leonardo's Mirror & Other Puzzles,  Lot's of geometrical puzzles with great graphics.   I was going to write a program to solve the "ant" puzzle, when i realized that Brute Force could handle it.  So "Ant-ics.prb" problem  is now included with the downloads.  I also added the ability to include images with puzzle descriptions to help clarify the equations used.  

June 9, 2005:  I removed a test today that attempted to avoid reporting duplicate solutions.  Once a solution had been reported, any that assigned the same value to the variable was considered a duplicate and eliminated.  In hindsight, that is not a very good criterion so we'll do without the duplicate solution test until someone smarter comes along to fix it.         

September 29, 2005: An bug in evaluating  equations with successive minus signs (e.g. A-B-C=0) was uncovered and fixed today.  The program which uncovered the problem, LongDivision,prb, which was added to the included samples. Also the old Combo unit used to generate permutations was replaced by the current UComboV2 unit which is included n the DFF  library file.  Therefore a one-time download of the DFF Library file will be required  if you wish to  recompile BruteForce.   

May 16, 2006:   Enough new features have been added to make it worthwhile to repost a version as BruteForce2.   Enhancements include:

October 29, 2007:  Version  2.1 posted today allows non-unique variables values.  That is, more than one of the  variables may be assign to the same allowed value.  A new sample problem, "Brothers and Sisters.prb" is included which motivated the new feature:  "In a certain family, each boy child has twice as many sisters as brothers. Each girl  child has the same number of sisters as brothers. How many children are there of each gender?"

I also re-implemented the uniqueness test removed a couple of years ago.  Rather than assuming uniqueness and setting the flag to false when any variable match with a previous solution was found, we now assume not unique and set unique=true when any variable has a different value than any previous solution value.

February 12, 2009: I started out merely add the problem from today's Mensa Puzzle_A_Day Puzzle Calendar, which asks you to use the digits 1-9 to complete this form when equations are valuated left to right and top to bottom.  However, I decided to add support to the program for JPEG files in problem displays when the BMP file turned out to be  150 Kbytes.  The high quality JPEG image displayed here is 24 KBytes, a significant savings.    Version 2.2 is the result.  
 

April 6, 2009:  A viewer recently pointed out  that even tough there is an option to allow multiple variables to have the same value, there was still an implied constraint that the number of possible values be at least as large as the number of variables.  This because with M variables and N values, the algorithm tries all permutations selecting M of N values, with or without repeats.   Version 2.3 repeats the final value if necessary  so that at least M values exist.  This allows, for example, the program to solve binary conversion problems like the newly included Binary Conversion example: "Find values between  6 and 16 with the two middle digits of the binary representation having the same value."     

September 18 2009:  A small update today to Version 2.4 includes and additional relational operator, "<" (less than) to help solve a new sample problem, Digit Relations 2.prb:  "I'm a four-digit number with ascending digits whose first two digits have a difference of two. My third digit is even and the sum of my first three digits equals my last digit. What number am I?" 

It's also the first of many program updates which will be required to properly scale forms when "DPI Scaling" is used to increase displayed text size on high resolution screens.  See DPI Scaling page for more details.

February 25, 2011: Two more changes implemented today to one of my old favorites.  A new sample problem, Mensa Puzzle 2-22-11.prb,   requires that one of the solution digits be even; a good reason  excuse to finally add the "mod" remainder function.  ("X is even"  means that  X divided by 2 leaves a remainder of 0, or X mod 2 =0.)   Version 2.5 adds "mod" and also sorts solutions alphabetically by variable name.  Previous versions listed variables in the order that they appeared in the input equations.

September 9, 2011: While implementing another Mensa Calendar puzzle, I discovered a bug when there are several solutions displayed; The solution rows were being sorted in ascending variable name order after each solution was found, but the program assumed that they were still in the original sequence so subsequent solutions had the value posted in the wrong row.  In Version 2.5 posted today, sorting is now delayed until all solutions have been found.  Here's the puzzle which required 26 equations to identify enough constraints on values for each cell in order to get down to the correct  unique solution.  The puzzle is now included in the downloads as file   "Mensa 09-08-11.prb"

November 13, 2011:   Another Mensa Calendar Puzzle and another small feature upgrade today.  In Version 2.6, you can specify the allowed solution integers as a range ( for example. 1-5 instead of 1,2,3,4,5.  An additional Mensa Calendar Puzzle also included in the download files (Mensa 11-13-11.prb)., one that Brute Force solves easily simply by entering the equation NOW+NOW+NO=CHOW.

Running/Exploring the Program

  [Feedback]   [Newsletters (subscribe/view)] [About me]

Copyright © 2000-2013, Gary Darby    All rights reserved.