Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2016-11-12 01:05:04

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,558

SOLS v5x5

Hi all;

This is a 5x5 version of the kind posted last year by patchy1, which was a 7x7 grid.

Each row A, C & E and each column 1,3 & 5 contain the numbers 1 to 5, and the number in each shaded square is the sum of the numbers in the eight white squares that immediately surround the shaded square.

No duplicate numbers are allowed in the white squares in any of the five rows and five columns.

YHNJEdk.jpg

I thought I'd post this 5x5 junior version as it's more doable than the huge 7x7.

I've found two solutions, but there may be more. One was with Excel's standard Solver, and the other was with a combination of logic, T&E and PoE on an Excel spreadsheet.

Last edited by phrontister (2017-02-23 18:30:16)


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

#2 2016-11-13 16:06:56

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,467

Re: SOLS v5x5

Hi;


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#3 2016-11-13 21:16:39

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,558

Re: SOLS v5x5

Hi Bobby;

Excellent! They're the two answers I got, too.

One is just a flip over the S-W/N-E diagonal of the other. I hadn't noticed that before I found my second solution (the non-Solver one), otherwise I could have saved myself a fair bit of extra effort!

There don't seem to be any other solutions.

Could you give me an idea of how to do this in M?

I notice from your answers that you seem to have spotted that the four shaded squares can be treated as white squares for part of the coding. That's how I drew up my Excel Solver model, which helped simplify and shorten the code.

Last edited by phrontister (2016-11-13 21:56:44)


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

#4 2016-11-14 04:25:40

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,467

Re: SOLS v5x5

Hi;

One is just a flip over the S-W/N-E diagonal of the other.

Yea, just a rotation of the other answer.

Could you give me an idea of how to do this in M?

I have been having problems with this type of problem for a while now. It started with the anonimnystefy square problem which gAr and I worked on but were unable to solve although gAr went further than I did. The problem stayed that way for a long time until I started working on it about 2 weeks ago. At first, I just assumed that the reason was that the problem was just too tough. But it became apparent that I could not solve any square problem of fill in the blanks with constraints like yours. When I saw your problem,  even though it is not too similar it was a good chance to see if I could do an easier one. I got about half way through with my own solution but am having difficulties.  So, the short answer is...no!


I searched the forums for some advice without asking for any help, just lurking. I came upon enzotib's answer over here.
http://mathematica.stackexchange.com/qu … 8509#78509
It can find solutions to your type problem in a reasonable amount of time.

I notice from your answers that you seem to have spotted that the four shaded squares can be treated as white squares for part of the coding.

It became obvious that this is a latin square problem with an extra condition. It simplifies the coding to not bother with the 4 sum squares.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#5 2016-11-14 09:18:22

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,558

Re: SOLS v5x5

Good morning, Bobby;

Thanks for the info and the link - I'll check it all out. Yes, I'd thought the matrix would feature but I don't have any experience with them and didn't know how to implement it. It was on my to-do list for further research.

Gonna have brekkie in a minute and then I'm gone for the day.

Catch you later. smile


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

#6 2016-11-14 09:27:27

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,467

Re: SOLS v5x5

Hi;

A matrix is a fancy name for a box that has a bunch of boxes inside it. These boxes can hold numbers and some other things. Operations can be performed on these matrices bsed on the rules that are defined for them. They were invented by Cayley and are incredibly useful.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#7 2016-11-15 01:10:36

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,558

Re: SOLS v5x5

Hi Bobby;

Thanks for the matrix info...I think I might be getting it.

I got enzotib's code to work for me, except that I could only get it to give me one answer per evaluation. A subsequent evaluation (or more) gave another answer. Only two answers were ever found, and they were the same as ours.

I couldn't work out how to change the code to output both answers in the one run.

Also, my run time varies from zero to about 100 seconds because of the RandomInteger just after the While.

I can't see how we could use this code on a 7x7 grid like patchy1's puzzle, given the HUGE leap in the number of permutations from my 5x5 puzzle that solves nowhere near fast enough to even think of trying it...unless I can find my time machine.


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

#8 2016-11-15 05:12:44

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,467

Re: SOLS v5x5

Hi;

Run this for a surprise.

r1 = Permutations[{1, 2, 3, 4, 5}];
ans = ParallelTable[
   r2 = Select[r1, Count[# - r1[[k]], 0] == 0 &];
     Table[r3 = Select[r2, Count[# - r2[[m]], 0] == 0 &];
          Table[r4 = Select[r3, Count[# - r3[[n]], 0] == 0 &];
              Table[r5 = Select[r4, Count[# - r4[[q]], 0] == 0 &];
                {r1[[k]], r2[[m]], r3[[n]], r4[[q]], r5[[1]]},
                {q, 1, Length[r4]}],
           {n, 1, Length[r3]}],
       {m, 1, Length[r2]}],
   {k, 1, Length[r1]}];
ans = Flatten[ans, 3];
ans = Select[
   ans, #[[1, 1]] + #[[1, 2]] + #[[1, 3]] + #[[2, 1]] + #[[2, 
        3]] + #[[3, 1]] + #[[3, 2]] + #[[3, 3]] == 
      21 && #[[1, 3]] + #[[1, 4]] + #[[1, 5]] + #[[2, 3]] + #[[2, 
        5]] + #[[3, 3]] + #[[3, 4]] + #[[3, 5]] == 24 &];
ans = Select[
   ans, #[[3, 1]] + #[[3, 2]] + #[[3, 3]] + #[[4, 1]] + #[[4, 
        3]] + #[[5, 1]] + #[[5, 2]] + #[[5, 3]] == 
      22 && #[[3, 3]] + #[[3, 4]] + #[[3, 5]] + #[[4, 3]] + #[[4, 
        5]] + #[[5, 3]] + #[[5, 4]] + #[[5, 5]] == 21 &];

MatrixForm[#] & /@ ans

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#9 2016-11-19 01:02:32

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,558

Re: SOLS v5x5

Congratulations! up

That's exactly what my problem needed...a full Latin Square list that could be searched for all answers. And the solution also lists the other two duplicate answers I found yesterday.

On my PC, compiling the list takes about 14 seconds, plus a further second for the search.

The 'ans' variable also runs in ubpdqn's (SE) code (replace 'ls /@ Permutations[Range[5]]' with 'ans')...change his criteria too, of course. Search output is the same as yours, and time is about 1 second.

This morning I generated a dummy 161280 list in a 'For' loop, incorporating two correct answers. That took 1 minute, and ubpdqn's code then found those two answers in 1 second.

So...now we're getting really close to solving a 7x7 for all answers! At your 5x5's speed it would only take about 170 years to compile the 7x7 list, plus a further 12 years to find all the answers. wink

Will your work help you with anonimnystefy's square problem?

Last edited by phrontister (2016-11-19 01:08:28)


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

#10 2016-11-19 01:19:06

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,467

Re: SOLS v5x5

Will your work help you with anonimnystefy's square problem?

He wants a 11 x 11 so it is unlikely that any counting them up is going to work. An analytical solution using Markov chains or maybe Cellular Automata. At present I could not get them to work.

For your 7 x 7, this 5 x 5 was my first ever for a square problem. I can go faster by using partitions rather than permutations.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#11 2016-11-19 09:25:13

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,558

Re: SOLS v5x5

The Excel add-in that I used to find the 24 solutions to patchy1's 7x7 puzzle is an analytic solver.


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

#12 2016-11-19 09:50:13

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,467

Re: SOLS v5x5

Hi;

I was a little vague in what I meant. We can consider two types of solutions, one is when the solution just spits out the number of ways something can be done. Like, there are 120 ways to permute the digits 1,2,3,4,5. Another type would generate all the solutions and find all 120 of them or look at a lots of them and find the 120.

For the 7 x 7 problem there are only 24 solutions which means either approach can be used. But for anonimnystefy's problem 3 x 3 there are 433 solutions. For a 5 x 5 there are over 209 million. I do not have any idea what an 11 x 11 has, but the number must be beyond astronomical. So, we do not have the luxury of a solver that gets them all or looks at a lot of them. There is no place to print or hold the list. This fact leaves most computer attempts out. We need something that just spits out the answer without counting anything. This will require the use of mathematics and lots of it.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#13 2016-11-19 10:21:49

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,558

Re: SOLS v5x5

Sorry, I'm not sure if I understand you correctly:

For a 5 x 5 there are over 209 million.

Re the SE 5x5, ubpdqn says, "there are 56 reduced forms and 161280 overall". Also, OEIS A002860.

For the 7 x 7 problem there are only 24 solutions

They're just the ones I found with that solver add-in, but I've no doubt that there are many more. The add-in is an optimisation program that gives one answer, and by changing numbers in a particular constraint I was able to extract further answers from it. I couldn't see an option to get all solutions.

The above OEIS link says there are 61,479,419,904,000 Latin squares for a 7x7.


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

#14 2016-11-19 10:29:45

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,467

Re: SOLS v5x5

Hi;

I meant the anonimnystefy problem which is a square problem but not a latin square. It is much, much larger than these.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#15 2016-11-19 10:35:23

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,558

Re: SOLS v5x5

I was just in the middle of changing my post to say it might be something like that. smile


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

#16 2016-11-19 10:40:17

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,467

Re: SOLS v5x5

You might want to take a look at the A problem. As of right now gAr is the only person to have solved the 5 x 5. I have been unable to do it with M.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#17 2016-11-19 10:49:06

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,558

Re: SOLS v5x5

Yes, please supply the link. Now that I've dipped my toe into the water I'd like to have a look.


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

#18 2016-11-19 10:53:31

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,467

Re: SOLS v5x5


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#19 2016-11-19 11:01:53

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,558

Re: SOLS v5x5

Thanks...I'll have a read and report back. Most of today is planned for other things, so I won't be able to get into this right away.

But brekkie first...!


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

#20 2016-11-19 11:07:00

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,467

Re: SOLS v5x5

Okay, see you later. I am going to try and make something to eat.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#21 2016-11-20 00:56:40

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,558

Re: SOLS v5x5

Sorry, Bobby...too tough for me.

I remember that discussion now about stefy's puzzle, but had to let it go then as I didn't have the first clue as to how to go about solving it...and still don't.

Btw, I initially wondered if 'two adjacent squares' included the central square and if 'adjacent' included 'diagonally adjacent', but from my reading of later posts in the discussion it seems that the answer to both questions is 'no'.


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

#22 2016-11-20 07:03:14

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,467

Re: SOLS v5x5

Hi;

Adjacent squares include the central square but no diagonal squares are considered. You are right it is very, very tough.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

Board footer

Powered by FluxBB