SOLS v5x5

phrontister · 2016-11-12 01:05:04

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.

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)

bobbym · 2016-11-13 16:06:56

Hi;

phrontister · 2016-11-13 21:16:39

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)

bobbym · 2016-11-14 04:25:40

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.

phrontister · 2016-11-14 09:18:22

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.

bobbym · 2016-11-14 09:27:27

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.

phrontister · 2016-11-15 01:10:36

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.

bobbym · 2016-11-15 05:12:44

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

phrontister · 2016-11-19 01:02:32

Congratulations!

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.

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

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

bobbym · 2016-11-19 01:19:06

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.

phrontister · 2016-11-19 09:25:13

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

bobbym · 2016-11-19 09:50:13

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.

phrontister · 2016-11-19 10:21:49

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.

bobbym · 2016-11-19 10:29:45

Hi;

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

phrontister · 2016-11-19 10:35:23

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

bobbym · 2016-11-19 10:40:17

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.

phrontister · 2016-11-19 10:49:06

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

bobbym · 2016-11-19 10:53:31

http://www.mathisfunforum.com/viewtopic … 00#p243200

phrontister · 2016-11-19 11:01:53

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...!

bobbym · 2016-11-19 11:07:00

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

phrontister · 2016-11-20 00:56:40

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'.

bobbym · 2016-11-20 07:03:14

Hi;

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

Math Is Fun Forum

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

SOLS v5x5

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

Re: SOLS v5x5

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

Re: SOLS v5x5

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

Re: SOLS v5x5

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

Re: SOLS v5x5

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

Re: SOLS v5x5

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

Re: SOLS v5x5

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

Re: SOLS v5x5

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

Re: SOLS v5x5

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

Re: SOLS v5x5

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

Re: SOLS v5x5

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

Re: SOLS v5x5

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

Re: SOLS v5x5

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

Re: SOLS v5x5

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

Re: SOLS v5x5

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

Re: SOLS v5x5

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

Re: SOLS v5x5

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

Re: SOLS v5x5

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

Re: SOLS v5x5

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

Re: SOLS v5x5

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

Re: SOLS v5x5

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

Re: SOLS v5x5

Board footer