# The Grey Labyrinth is a collection of puzzles, riddles, mind games, paradoxes and other intellectually challenging diversions. Related topics: puzzle games, logic puzzles, lateral thinking puzzles, philosophy, mind benders, brain teasers, word problems, conundrums, 3d puzzles, spatial reasoning, intelligence tests, mathematical diversions, paradoxes, physics problems, reasoning, math, science.

Author Message
Icarian Member

 Posted: Sun Apr 05, 2009 10:01 pm    Post subject: 1 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
Tired of his old title

Posted: Mon Apr 06, 2009 2:41 am    Post subject: 2

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.

 Code: 0 +1  0 -1  0   0  0  0  0  0   0 -1  0 +1  0   0  0  0  0  0   0  0  0  0  0
Antrax
ESL Student

 Posted: Mon Apr 06, 2009 5:34 am    Post subject: 3 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*
Guest

 Posted: Mon Apr 06, 2009 9:52 am    Post subject: 4 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
Daedalian Member

 Posted: Mon Apr 06, 2009 10:12 am    Post subject: 5 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
ESL Student

 Posted: Mon Apr 06, 2009 10:42 am    Post subject: 6 ...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
Daedalian Member

 Posted: Mon Apr 06, 2009 4:43 pm    Post subject: 7 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
Daedalian Member

 Posted: Mon Apr 06, 2009 6:47 pm    Post subject: 8 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
Daedalian Member

 Posted: Mon Apr 06, 2009 6:55 pm    Post subject: 9 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
ESL Student

 Posted: Tue Apr 07, 2009 5:16 am    Post subject: 10 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
Tired of his old title

Posted: Tue Apr 07, 2009 1:01 pm    Post subject: 11

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.

 Code: 8 9 7 1 9  8 7 8 2 5  0 9 4 7 9  4 2 9 3 9  4 1 2 6 4

As I said above, once you have one solution, you can trivially make more with transformations that don't change the sums. For example, by applying the matrix on the right side to the solution above, I got the solution on the left. You could use that one 3 more times. Then turn the transformation matrix 90 degrees and reflect it, then use it up to 6 times, plus combinations, etc.

 Code: 8 9 7 1 9     0  0  0  0  0  7 7 8 2 6    -1  0  0  0 +1  0 9 4 7 9     0  0  0  0  0  5 2 9 3 8    +1  0  0  0 -1  4 1 2 6 4     0  0  0  0  0
Zag
Tired of his old title

Posted: Tue Apr 07, 2009 1:44 pm    Post subject: 12

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.

 Code: X C D . X  E B F . .  G H X I .  . A J . .  X . . . X

Worst case = 5 * 10^9 = 5 billion combinations, which is doable on a PC in a reasonable amount of time.
lostdummy
Daedalian Member

 Posted: Tue Apr 07, 2009 2:21 pm    Post subject: 13 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
Tired of his old title

 Posted: Tue Apr 07, 2009 4:44 pm    Post subject: 14 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
Daedalian Member

Posted: Tue Apr 07, 2009 5:00 pm    Post subject: 15

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

well, in my implementation it needed to be "tried", because I had to check if value that I could compute is in fact legal ( 0..9). It was easier to just treat it like other nodes and put it in order list ;p
ralphmerridew
Daedalian Member

 Posted: Wed Apr 08, 2009 1:08 am    Post subject: 16 Least number of givens needed is zero, if all the row sums are zero.
lostdummy
Daedalian Member

Posted: Wed Apr 08, 2009 7:37 am    Post subject: 17

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

true, and it would be true for all sums of 45 too, although I was more thinking about situation where we keep original row/column sums, like in example with 7 predefined cells ;p
Antrax
ESL Student

 Posted: Mon Apr 20, 2009 11:29 am    Post subject: 18 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
Daedalian Member

Posted: Thu May 14, 2009 1:43 pm    Post subject: 19

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:
 Code: :- use_module(library('clp/bounds')). seablade(ProblemID,Solution):-    problem_definition(ProblemID, Solution, RowSums, ColSums, FwDiSu,BaDiSu),    clipper(Solution, RowSums, ColSums, FwDiSu, BaDiSu). clipper(Tableau, RowSums, ColSums, FwDiSu,BaDiSu):-        flatten(Tableau, FlatProblem),    FlatProblem in 0..9,        addRows(Tableau,RowSums),        transpose(Tableau,TransposedProblem),    addRows(TransposedProblem,ColSums),        addBackwardDiagonal(Tableau, BaDiSu),        reverse(Tableau,ReverseTableau),    addBackwardDiagonal(ReverseTableau,FwDiSu),        label(FlatProblem).     problem_definition(1,    [[8,_,_,_,9],     [_,_,_,_,_],     [_,_,4,_,_],     [_,_,_,_,_],     [4,_,_,_,0]    ],    [34,30,29,27,17],    [24,28,30,19,36],    21,    26). addRows([],[]):-!. addRows([HH|TT],[H|T]):-    sum(HH,#=,H),    addRows(TT,T). addBackwardDiagonal(Matrix,Sum):-    backwardDiagonal(Matrix,Diagonal,0),    sum(Diagonal,#=,Sum). backwardDiagonal([],_,_):-!. backwardDiagonal([M|Atrix],[D|Iagonal],Depth):-    length(Prefix,Depth),    append(Prefix,[D|_],M),    Increment is Depth + 1,    backwardDiagonal(Atrix,Iagonal,Increment). transpose([W], C) :- !,    l2c(W, C). transpose([H|T], Cs) :- !,    transpose(T, C0),    p_c(H, C0, Cs). l2c([], []):-!. l2c([X|Xs], [[X]|Zs]) :- l2c(Xs, Zs). p_c([], Cs, Cs):-!. p_c([X|T], [C|C0], [[X|C]|Cs]) :- p_c(T, C0, Cs).

; will keep on producing solutions till you get bored. I did after about 10.
 Code: Solution = [[8, 0, 8, 9, 9], [0, 9, 9, 3, 9], [5, 9, 4, 2, 9], [7, 1, 5, 5, 9], [4, 9, 4, 0, 0]] ; Solution = [[8, 0, 8, 9, 9], [0, 9, 9, 3, 9], [6, 9, 4, 1, 9], [6, 1, 6, 5, 9], [4, 9, 3, 1, 0]] ; Solution = [[8, 0, 8, 9, 9], [0, 9, 9, 3, 9], [7, 9, 4, 0, 9], [5, 1, 7, 5, 9], [4, 9, 2, 2, 0]] ; Solution = [[8, 0, 8, 9, 9], [1, 9, 8, 3, 9], [5, 9, 4, 2, 9], [6, 1, 6, 5, 9], [4, 9, 4, 0, 0]] ; Solution = [[8, 0, 8, 9, 9], [1, 9, 8, 3, 9], [6, 9, 4, 1, 9], [5, 1, 7, 5, 9], [4, 9, 3, 1, 0]] ; Solution = [[8, 0, 8, 9, 9], [1, 9, 8, 3, 9], [7, 9, 4, 0, 9], [4, 1, 8, 5, 9], [4, 9, 2, 2, 0]] ; Solution = [[8, 0, 8, 9, 9], [1, 9, 9, 2, 9], [4, 9, 4, 3, 9], [7, 2, 4, 5, 9], [4, 8, 5, 0, 0]] ; Solution = [[8, 0, 8, 9, 9], [1, 9, 9, 2, 9], [5, 8, 4, 3, 9], [6, 2, 5, 5, 9], [4, 9, 4, 0, 0]] ; Solution = [[8, 0, 8, 9, 9], [1, 9, 9, 2, 9], [5, 9, 4, 2, 9], [6, 2, 5, 5, 9], [4, 8, 4, 1, 0]] ; Solution = [[8, 0, 8, 9, 9], [1, 9, 9, 2, 9], [6, 8, 4, 2, 9], [5, 2, 6, 5, 9], [4, 9, 3, 1, 0]] ;

_________________
Better ways to push & pull!
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year by All usersAnonymousAntraxlostdummyralphmerridewSeabladeTermitalZag Oldest FirstNewest First
 All times are GMT Page 1 of 1

 Jump to: Select a forum Puzzles and Games----------------Grey Labyrinth PuzzlesVisitor Submitted PuzzlesVisitor GamesMafia Games Miscellaneous----------------Off-TopicVisitor Submitted NewsScience, Art, and CulturePoll Tournaments Administration----------------Grey Labyrinth NewsFeature Requests / Site Problems
You cannot post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum