Brute Force

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

 

Search

 

Search DelphiForFun.org only

Support DFF

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.

In Association with Amazon.com

 

Support DFF

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

 

 

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

 

Search DelphiForFun.org only

 

 

 

 

 

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:

bullet

The  word arithmetic problems called Alphametics,  where each variable is a digit 0..9.   The Alphametics program previously posted only solved addition problems.  BruteForce should be able to solve problems with other operations, although I haven't tried any yet.  

bullet

 NxN Magic squares have a solution set consisting of the integers 1..N2.    

bullet

What 3 digit number together with it's square contains all 10 digits?.   

bullet

The Bookshelf problem: "Kristen noticed that if she arranged her 9 volume set of Horse books with volumes 6729 on the top shelf of her bookcase and 13458 on the bottom, the result was a fraction with value 1/2.  She started rearranging the books trying to make other fractions (1/3, 1/4, 1/5, 1/6, 1/7, 1/8 and 1/9).  Can you help her?"  

bullet

The 5 Olympic rings overlap to form 9 distinct areas.  Write the digits 1..9 in the areas so that the sum of the digits in any ring is 11.   

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: 

bullet It uses my Combo unit to produce permutations of integers that may be solutions. 
bullet BruteForce contains a  postfix equation evaluator to test trial solutions against a set of equations entered as text. 
bullet I've added an alternative incremental solution algorithm that tries to solve one equation at a time. 
bullet It lets you define, save, and load new problems and  uses a TTabControl component  to display loaded problems. 

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 PuzzlesLot'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:

bulletProblem description text had previously been reformatted when the case was reloaded.  It should now stay "as entered".
bulletMath is now performed with 64 bit integers instead of 32 bit.  This increases the maximum number of digits in   integer calculations from 9 to 18 digits. 
bulletThe best one:   A new option allows the user to specify that all variable names have single character names.  This allows the program to interpret input ABCD as a 4 digit integer as opposed to a variable named "ABCD".  I rewrote many of the sample problem to take advantage of the new feature.  ABCD is much easier to write than (1000*A+100*B+10*C+D).
bulletA user requested the ability to save solutions, so a new button saves solutions as CSV (comma separated value) files which can loaded directly in Excel, etc. 

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.

Place the numbers 1 to 9, one per square, so that no two consecutive numbers in squares that touch in any way, even at a a corner.  Three numbers have been placed to get you started.

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.


February 9, 2014: 

Mensa Puzzle 2-5-14 Calendar

Version 3.0 fixes a problem with Incremental Solving when multiple variables can have the same value.  The problem was that it didn't work very well!  The problem that brought this to light is illustrated here and is included in the downloads:  It takes 12 equations with 17 variables to define the algebraic solution for coin sums of each row, column, and long diagonal.  Each variable (empty square) needs one of 4 values: empty, nickel, dime, or quarter (0,5,10,25).   This implies that there are 417, (something over 17 trillion) configurations to be checked by the straight forward Brute Force search!   Brute Force button found the solution in about 30 minutes  and verified that it is unique in 15 minutes more. 

 Incremental Solve works by enumerating each solution for the 1st equation, then testing the 2nd equation to see if there could be a valid solution given the trial solution for the 1st.  If so, see if the trial values assigned for the 1st and 2nd  equations would allow the 3rd to be solved, etc.  Understanding the mechanics requires  understanding the powerful Computer Science concepts of Depth First Search and Recursion, but it is not necessary to see how well it can work.  The Incremental Search button finds the unique solution in 0.05 seconds and takes an additional 0.10 second to verify that the solution us unique!.        

 

April 12, 2014:  Version 3.1 adds the absolute value function, "abs", to enable solving the "Billiard Balls" problem.  The problem is to arrange 10 billiard balls into a triangle meeting a set of rules about the ball numbers.  One of the constraints is that the balls in a particular row all have numbers more than 1 away from their neighbors.  This constraint for balls with numbers "a" and "b" can be expressed with the equation "abs(a-b)>1".  Sample problem BilliardBalls.prb is included with the download and is solved in about one second.  
 

Running/Exploring the Program

bulletDownload source  (requires DFF library DFFLIB03 or later to recompile)
bulletDownload library DFFLibV14_24Mar2014
bulletDownload  executable  

Suggestions for further exploration

Feb. 2011 Done!:  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: April 13, 2014

  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright © 2000-2013, Gary Darby    All rights reserved.