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; 

Find the six digit number in which the first digit is one less than the second and one half the third, the fourth digit is one more than the third and is also the sum of the first and second, and the the fifth and six digits make a number which is the sum of the first four digits. The sum of all the digits is 19.

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.

Running/Exploring the Program

Suggestions for further exploration

Expand the expression evaluator to include additional operators, e.g. mod. <, <>.

Add an additional solution mode to try all solutions within a range.  This would allow solutions with repeated digits.  Even more advanced, develop an appropriate interface syntax to allow this problem to be entered and solved:  "Find all 5 digit numbers whose square contains all of the digits 1..9 exactly once".

It would be nice if the popup menu for description text, equations and digits editing  included Cut, Copy, and Paste options. 

Rewrite the code to incorporate dynamic in place of static arrays and in TStack the expression evaluator.   
  
Created: December 10, 2001

Modified: November 07, 2008