An alogorithm for this puzzle?

[Seablade]

Here's a puzzle that I wanted to see if anyone could come up with the solution:


The numbers at the bottom and to the right are the sums of the digits contained in each cell. For example, the first column on the left says the sum is 24 and the sum of the first row on the top says the sum is 34. The diagonal sums are provided as well.

Each cell can contain only the numbers from 0 throuh 9 and can be repeated more than once in any given row or column so its more complex than a sudoku puzzle. Five cells are provided to start.

What I would like to know is this:
1) What are the values for each cell?
2) Is there a general purpose algorithm that will generate those cell values?
3) If not, how were the generated numbers deduced from the information?

[Zag]

If there is no restriction on duplicate digits in a row or column, then it is easy to show that the solution is not unique. Find any solution, then apply a matrix like the following to it. There are 6 such rectangles that do not hit any of the diagonals.

[Antrax]

A brute force search using backtracking should be good enough for such a small puzzle (though I'd recommend coding early exits in and starting with the most constrained constraint first, as actually checking all possible combinations would take too much time).
If you want something more intelligent, it's probably possible to solve this using relaxation. i.e. guess a totally random solution, then start randomly decrementing one to a oversubscribed constraint or adding one to an undersubscribed one, with some basic hashing thrown in to make sure you don't end in an infinite loop. That's a lot more interesting algorithmically, but also has considerably more pitfalls, and I have no clue if it's bound to work.
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[Lepton*]

I'd love to see an evolutionary algorithm (with some sort of cute graphics, so I could keep track of it) applied to this problem. Antrax is right, though: brute force is probably the "right" way to do it.

[lostdummy]

Well, brute force is not exactly "right way to go" ;p

Approximate size of search space is 10^25 (well, 10^20 when 5 cells are predefined). If we assume only 10 CPU instructions per one check, and some 3GHz CPU, we would need about 10 millenniums to really "brute force" that.

But if we do some kind of "optimized" brute force, that would significantly reduce search space, than it would probably be possible to find solution in normal time. After all, when I was making my Sudoku solver and generator, I could not use brute force either, and this is similar type of problem.

[Antrax]

...which is why I added the disclaimer about the early exits and searching in an optimal order
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[lostdummy]

Well, here is program that can solve it:

sudoku25.rar

It has two options:

-"brute" force (not exactly brute, has optimizations, can solve problem)
-up/down (try to increase/decrease cells ...but can not find solution yet, needs hash to stop repeats)

As an added bonus, it can show/draw step by step its progress - just change edit field to the right of "Next" from 1000000 to 1 (it says how many steps to try on each press of "Next" button).

[ralphmerridew]

Will linear programming methods work? (I'm not sure how well the simplex algorithm copes with equalities.)

8 + a12 + a13 + a14 + 9 - 34 >= 0
-8 - a12 - a13 - a14 - 9 + 34 >= 0
a12 >= 0
-a12 + 9 >= 0
...

http://en.wikipedia.org/wiki/Linear_programming
http://en.wikipedia.org/wiki/Simplex_Algorithm

The simplex algorithm itself doesn't force integer values, but with all coefficients +- 1, it will probably give such an answer or be quickly adjustable to one, if one exits. (Probably.)

Integer programming itself is known to be NP-hard, so more general problems may not be efficiently solvable.

[ralphmerridew]

Or:
- Treat it as a system of 11 equations in 20 unknowns. (One row / column is redundant.)
- Choose a set of nine squares such that the remaining 11 are independent.
- Brute force those 10^9 possibilities.

For Antrax's method, try doing:
define
f(x) := 0 if 0<= x <= 9
:= x^2 if x < 0
:= (x-9)^2 if x > 9

Then only allow using moves that reduce the sum of all the fs.

[Antrax]

You can model a == b by doing a >=b and -a >= -b.
I'm not entirely sure about your assertion that the answer can be easily adjustable to an integer value.
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[Zag]

Here's one solution. I just solved it by hand, using a spreadsheet. I just put in the numbers that were fixed, put in formulas for the sums, and then put the target numbers just outside of those. Then I just futzed with it until it was right.

[Zag]

To answer the original question about an algorithm, I would hand-craft the order you vary the cells, since certain cells are more "powerful."

X = given
A-J = order cells should be tried
. = can be calculated

A = 0 to 4
B = 0 to 9
C = 0 to 9
D = 0 to min(9, 17-C)
E = 0 to 9
etc.

[lostdummy]

It would be interesting to see what is minimal number of predefined cells that would still end up with unique solution.

For example, if we keep all row sums same, and change cells to:

8xx2x
xx1xx
x6xxx
3xxxx
45xxx

tt result in unique solution, with 7 predefined cells. I'm not sure if that is best or there is problem with 6 (or less) predefined that result in unique solution, since I only used "Design" option in my program from above to test/try few setups until i got one posted here.

As for algorithm, I used cell ordering based on score, where:

Cell_score = sum(row_scores)* 2^N_diagonals
Row_score= 10^N_of_predefs

In other words, if row has 3 predefined cells (and "predefined" means also previously selected higher order cells), that row has score=10^3=1000. If cell happens to be on one diagonal, it has score=2*10^3. If row happens to have all cells but current one filled, its score=10^4.

That result in fairly simple ordering which favor almost full rows, and after that diagonals, but which is not "hand coded" and can adapt to different initial setups (for example if someone use "Design" option)

For original problem, it result in this order:

XCDEX
IAJMN
KLXOS
PQRBT
XFGHX

and it result in solution after less than million combinations.

[Zag]

Wow! I totally didn't understand that.

I realized in my algorithm, above, that J doesn't need to be tried; it can also be calculated.

[lostdummy]

[ralphmerridew]

Least number of givens needed is zero, if all the row sums are zero.

[lostdummy]

[Antrax]

I realised a couple of days after my previous post what I had in mind with "relaxation" etc - I think a Flow-Network-based algorithm can be used to find a solution to this type of puzzle. Add a dummy source connected to all nodes where you put numbers, dummy nodes for the sums and dummy sink from them, and define the constraints on the edges connecting "sum nodes" to the sink based on their sum constraint.
I hope that made sense.
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[Termital]

Given how underconstrained the problem is, if it's only one solution you need, any form of CLP will produce results almost instantly, even the rather sub-optimal Prolog code below: