julie@eecg.toronto.edu (Julie Payette) (04/14/90)
Bonjour!
I have to solve the following problem and I know it could be
done with exhaustive search, but since speed is of the essence
--- we will be parallizing it --- I would be interested in knowing
if there are any known, more efficient algorithms that might
be applicable to this problem.
Here's the problem:
====================================================================
Problem:
Given an empty n by n matrix and n^2 symbols from the
set { <blank>, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -, +, =, *, / }
assign the symbols to the elements of the matrix (one per element)
such that each string separated by white space when read
from left to write or top to bottom is either a constant (0..9)
or a correct equation of expressions, where white space
is defined to be one of more <blank> symbols or the edge of the array.
For example, "3" or "3+6" represent constants and
"7=4+6/2=2+3+2" represents an equation.
Note that
- the string may not contain white space.
- the remainder of a division must be zero, i.e. 7/3 is invalid
- * and / have priority over + and -
- + - are only allowed as binary operators (not as signs)
Example 1:
Given a 7x7 matrix and the following symbols: 24 <blanks>, 3 +'s,
6 ='s 8 0's and 8 1's then the following is a solution:
+-------+
| 0 |
| 1=1 |
| 1+0=1 |
|0=0+0=0|
| 1=0+1 |
| 1=1 |
| 0 |
+-------+
Example 2:
Given a 7x7 matrix and the following symbols: 16 blanks, 2 +'s,
2 -'s, 1 *, 1 / and 3 ='s then the following is a solution:
+-------+
| 1 4 9 |
|7=4+6/2|
| 2 5 3 |
|2*4 9-1|
| 3 7 1 |
|8-1+2=9|
| 5 2 2 |
+-------+
====================================================================
Please e-mail replies directly to julie@eecg.toronto.edu.
Merci mille fois!