[Home] [Puzzles & Projects] [Delphi Techniques] [Math topics] [Library] [Utilities]
|
|
Problem DescriptionBrute 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 & TechniquesThis 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.
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.
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. File AlphabetLongDivision.prb is the 40th sample problem file added to
the download zip files since the original posting in 2001. It is the
perhaps the first to extensively test the shorthand feature that treats
character strings as multi-digit integers and can define the problem with
equations like BRINK / RIB = RUN, RIB * R= OAR, etc.
Click the here if you have the
April program update and just want the new problem to play with.
September 28, 2014: One more small change to enable solving this Mensa Calendar puzzle. I hadn't realized that Divide operations by default were ignoring remainders. This puzzle produced two solutions under those conditions. Version 3.2 adds an option requiring that divide operations in solutions be exact (with no remainders). With that option selected, the program now returns a unique solution. The problem file "Mensa 09-26-14.prb" is included in the downloads below.
October 5, 2014: Version 3.2.1 fixes a small problem when the image from the previous problem still displays when a new problem is started or an existing problem without an associated image is opened. December 3, 2014: It recently occurred to me that not everyone will be entering new puzzles to Brute Force, but might want to solve some of the 42 sample problems included with the downloads. Version 3.3 no longer displays saved parameters and equations when a problem is loaded. Try to solve it on your own first! A new button allows saved solution stuff to be displayed if you need help. Running/Exploring the Program
Suggestions for further exploration
|
[Feedback] [Newsletters (subscribe/view)] [About me]Copyright © 2000-2018, Gary Darby All rights reserved. |