Opti-Pentobattle

In the original version of this puzzle it was too easy to find an optimal solution. With the added challenge to minimise the grid size it became a very good optimiser puzzle. Here are my thoughts on the steps needed to solve it.

(On an earlier discussion, I'm not against people using a computer to solve an optimising problem. It is usually very slow to do though. Writing a computer program to solve Opti-Pentobattle is probably a bad idea. There are vast numbers of cases to check, and any insights to speed up the program would also allow you to solve it on paper 10x faster. Although if anyone did successfully write a program I would love to talk to you more about it)

Q1: How many pentominoes are needed?
Two ships always need at least one extra sea cell to join between them.
Three ships would always need two+ extra sea cells.
Ten ships need nine extra cells. So the area must be at least 29 cells, so 6 pentominoes are needed.

Q2: How small can the grid be?
Any 2x2 square can never contain pieces from two different ships.
The fleet contains 7 ships that can fit on one 2x2 square, and 3 ships that fit on two 2x2 squares.
So the whole grid must include at least 13 different 2x2 squares (or pieces of squares).
A 9x5 grid contains 5x3=15 squares, a 7x7 grid contains 4x4=16 squares, anything smaller will not fit the whole fleet.
Of these two, 9x5=45 is better than 7x7=49.

Q3: How can the fleet fit into a 9x5 grid?
At first I could not fit 10 ships into this grid size. But consider this:
Maths: [Imagine the grid has an extra row and column (right and below), it is 6x10.
And imagine each ship has an extra row and column (right and below) of empty space where another ship cannot go.
So a 1-ship "occupies" 4 cells, and a 4-ship occupies 10 cells.
The whole fleet occupies 4x4+3x6+2x8+1x10 = 60 cells, the same size as the 6x10 grid.
So _every_ cell must be used.]
=> Rule for 9x5 grid only: Every 2x2 square that covers some of the 9x5 grid must include a piece of ship. (even overlapping an edge or corner)
Therefore:
- Every corner cell has a ship piece.
- The 4-ship must be horizontal (parallel to the 9-edge) in row 1 or 3 or 5.
There are different ways to do this, e.g. I just created three horizontal rows containing 421, 331, and 2211 ships.

Q4: How do I join the fleet to have a unique solution?
There are some cases you cannot have:
- You cannot join a 1 directly to another 1. Because "1.1" can be swapped with a "3" elsewhere.
- You cannot join two different sizes in a straight line. Because "2.3" might also be "3.2", etc.
- You cannot join a 1 to the end of a 3. Because a V-pentomino containing a 1.3 could also be 3.1.

So this should lead you to a shape that has a unique Battleships solution.
The final step is to find a combination of 6 different pentominoes to cover this shape.
Because only 29 cells are needed for the unique solution, you have one 'spare' cell that can be added anywhere, which should make this step easier.

Also, if you want to solve one of the contestant's 9x5 solutions, use the rules "Every 2x2 square must include a piece of ship" and "Every ship cell cannot diagonally touch another ship cell" will make it much faster.
Most solutions use one of these approaches early on:
- After placing initial pieces there is only one location that the 4-ship can fit.
- After placing initial pieces the four 1-ships have been found, so all other ship pieces are 2+ long.

Edited by kiwijam 2016-04-29 4:41 AM

We have compiled the submissions of Opti-PentoBattle in a pdf. Here is the link. The submissions are not checked for correctness.

All twelve solutions with (Area=45, K=6, N=1) are good.

I seem to have written GOGOGOV instead of GOGOVOV. I think that is my error in the Sextet at least.

I misplaced one Cloud stupidly.

And I had found the 44, but counted it as 42 so didn't submit it.

Not my contest clearly.

Edited by Para 2016-04-29 10:45 AM

my solution to puzzle 1 seems all right to me.
I noticed the same solution has also been submitted by two other players
here is the solution. Is it possible that the puzzle had multiple solutions?

http://web.freepass.it/sf2l/mysoln1.JPG

are the solutions to be posted somewhere soon?
stefano

Edited by forcolin 2016-04-29 1:19 PM

It looks to me that some may have multiple solutions.

I congratulate the winners - Ken, Hideaki, Tomoya and James!


Several solvers were caught in the step of victory, but were prevented by the puzzle Accordances. I invented it few years ago, but did not dare to include in the Contest. I didn't want to hear claims in its incorrectness. So in the last two April Contests (2014 and 2015) I suggested puzzles, where some of the letters match the Roman numbers (see Roman XO and Roman COOL-L-L). Only after that I included the puzzle in the Contest.

Final score page, with puzzle ratings - http://logicmastersindia.com/2016/04Contest/score.asp

VOYAGE was voted as the best puzzle, with a near-10 rating.

It seems typos are not penalized.I also had one (typed 3 instead of 2)

Congratulations to the champions , and to Riad.
I had less time this year to look for the problems, but they seemed harder than last year.
For Mirrored sudokus, I only answered to puzzle B, but it seems my answer is correct : why don't I get 1.5 points ? (which will not change anything...)

Accordances just clicked when I tried Roman Numerals. 51(Li) was key for me. Got some use out of remembering HHeLiBeBCNOF as a mnemonic when I was in high school.

Solved these on an 11hr flight and still couldn't finish it!
Mirrored Sudoku, Borderless Sextet and Voyages alone took me about 6-7 hours combined.
As someone who also solve word and lateral puzzles, I got Accordances in about 5 seconds (high fives self).

I've never tried optimizing puzzles seriously before so its nice to see I can still score well there.
Also eager waiting to see the solutions for Crossmind, love the idea a lot but did anyone else find the individual Mastermind puzzles having too many multiple solutions?
Which translated to having to trial and error the criss-cross portion a little too much for it to be as enjoyable as other puzzles in the set.

The flight attendant told me I had to put the tray-table back up cause we're about to land so I couldn't go back to finish Bricks ;)

Thanks Riad!
Will you be doing this in September as well?

The typos have been to several solvers. I recognized correct those solutions that had a long answer.

I thought that the points for Mirrored Sudokus is done automatically. I'm with Deb now you will add 1.5 points, thank you.

These puzzles I made in 2104-15, and in January I tested at the time. The fastest I solved Mirrored Sudokus – for 72 minutes, the longest – Crossmind – for 100 minutes. This despite the fact that I am very fast in solving verbal puzzles. In the preparation of each of Mastermind I used word meaning the same thing in different languages. I am from a small Tabasaran ethnic groups, compactly living in Dagestan. In addition I speak Azerbaijani and Turkish languages. So the idea to make a multilingual puzzle using 5-letter words.
This year I plan to meet with you at LMI twice. I promise a lot of innovation in the September Sudoku Contest and the Moscow Puzzle Cup. I have the booklets ready, so it remains only to discuss dates.

Hello. No solutions for accordances? I would like know the solution.

If you write the left numbers at the Roman way, they will resemble the symbols of chemical elements. On the right indicate the atomic numbers of these elements.

Thanks. I wrote the left numbers at the Roman way, but I not seen the chemical elements... Very interesting. Congratulations for all the puzzles. Very funny.

So, feedback about the contest.

Not particularly enjoyable. This contest just reiterates the reason I dislike large puzzles. (Even though I authored NEW, HUGE, AND CHALLENGING! and one puzzle in Puzzle Marathon, yes.) The puzzles are so tough that you don't know where to look. While this is not a very big problem for the earlier puzzles (Pentobattle and the Clouds variant were nice), I particularly dislike Borderless Sextet and Crossmind. The former is probably because of the rules being terribly unclear, even after clarifications in-thread (where some went unanswered). The latter because it looks like pretty much all work, with no logic visible. I bruteforced the Mastermind puzzles by programming, and even after getting all possible answers for each, I couldn't even start putting any to the grid; too many letters that cross each other in all positions. And of course I loathe Accordances just like I loathe similar inductive puzzles. Yes, I got the expected answer for that, but I still dislike it anyway.

Puzzles that I solved, besides Accordances above... Pentobattle was a nice, easy puzzle. In Terms of Area, despite being big, is actually manageable, because that's approximately the size of medium-large Clouds puzzles. Both are my favorites for the contest. Coded Arrows wasn't very memorable; I think there were a few trial and error, testing whether a number works for a letter. Bricks was fine during solving, although it's a rather awful idea; I don't know why, I just don't like that genre in general. Probably because the positions of the clues are already given, so finding the sums can be independent from placing the bricks. I distinctly recall Trid-Fir requiring quite a lot of casework, putting a certain number here to find a contradiction about 10-20 numbers later. Mirrored Sudokus were actually quite fine; the large-scale logic of placing the 4s and the 3s early is interesting, although I think that's pretty common in Mirrored Sudokus in general. Opti-Pentobattle was a fun one. In The Citadels was just messy; the first thing I did was to convert it to a graph, then blindly trying things until I stumbled on a solution.

So, yes, I don't know why I keep doing these April Contests even though I don't particularly enjoy some of them. Maybe just because they are puzzle tests that are otherwise rare here on LMI nowadays.

The feedback about the contest from me is the opposite... one of the best contests of the year.
People believe we are good because we solve difficult puzzle.
But what about those persons who SET the difficult puzzles? they are even more genial in my opinion.
I enjoy particularly this contest because traditionally I have my best results. A bit unconventional, speed does not count that much..... This contest is the Paris-Roubaix of puzzling. If it wasn't for a stupid typing mistake I could have been in the top five, in excellent company. Will try again next year.
These puzzles in general are very well constructed and with the right type of twist. The best for me was the borderless sextet, very deceptive with that double black cell on which I lost hours. Believe it or not, I started solving it from the Scrabble. Also very good the Voyage; I also liked the Coded Arrows for its simple and very logical solving path (couldn't see it, Chaotic?).The least beautiful the mirrored sudokus (ended up cross-eyed... you know, at my age......) and the Crossmind. And yes, I did not like too much Accordances, which requires more intuition than logic. The first optimizer, in the modified variant, has turned out to be very good, while the Citadel could have been a bit larger thus offering more possible options. As it has been pointed out before in the discussion, for both optimizers it was possible to demonstrate at a certain (early) stage that no better solutions were possible.
Thanks Riad for yet another very enjoyable week.
Stefano

Edited by forcolin 2016-04-30 3:48 AM

The Crossmind puzzle was really enjoyable to me. I could get to all Mastermind puzzles logically, Even with the non-uniqueness. It helped me reinforce some of the logic involved as I hadn't really done many recently.
The secong part of the puzzle relied very much on uniqueness. Knowing that certain words had multiple solutions, they would have to go cross with other words to fix uniqueness. This actually made the Crossword very solvable. This might not be the favourite logic for many, but it's the kind of creative thinking that is expected in this contest. Think outside the box, find ways to approach the problem differently. That's what to expect in this contest.

The same could be said about the Bordeless Sextet. I actually constructed almost the whole crossword, except for LQQ on a separate piece of paper and then tried to fit it in. It's a bit like optimising. How can I use this space optimally, so that I expect everything to fit? You know in advance there's going to be relatively little space to use, so you start recognising how things fit together. It's not necessarily, "oh this 9 shape has to go there", but "oh this would be a perfect spot for this 9 shape; it is like it's made for it". It's good to train these skills too, to have a feeling what the author did, instead of what the author wants you to do.

That thinking also comes into place in the optimisers. First you figure out you need an even number of steps to get to 0, then you work out how to get this as high as possible. The highest possible Even Steps path doesn't have a 0 solution though. That took me a while to prove. So then lose 2 steps and try again.
The other optimiser turned from easy to, how do I get these 10 ships in as small a shape as possible. And then, which cells should remain blank to have a possibility to ever be unique. And then can I cover the rest with pentominos. With the last step being, make sure it's unique. This can be annoying.

I get that this contest isn't for everyone, which is why it gets these low competitor totals. But for those who enjoy it, they are always fun.

In general, I have the same mindset as Ivan (Chaotic). Large puzzles are boring (we're talking 25x25 sudoku "large" and not some other creative "large" eg. some of the puzzles in LMI marathon).
However, I will make the case for the Borderless Sextet and Voyages.
Who would think Borderless Sextet starts from the Scrabble? The weird letter patterns in the word list should prompt you create a draft of the grid - which only had about 3-4 possible alternatives and ruling out each one wasn't so guessy. Packing in numbers and tetrominoes were very logical. So I felt this puzzle required initial insight and mostly logic. Defitinitely not blind stumbling like the Crossmind (I don't think using uniqueness should be a job for solvers).

Voyages was also procedural. Start with the biggest piece and work your way from the maximum values 21-20-19-18-17.. Etc.
The solving path may have been a little too narrow that one mistake can ruin hours of work.
But the bottom line is you can see that it is logical.

My complaint about Borderless Sextet is that I can't understand the instructions, so I didn't even attempt to solve it. For example, I've been understanding Loop that "touching" means Snake-like touching; if adjacent cells are both part of the loop, then the loop must also go through them consecutively. The regions are also said to be contiguous, so I wondered what could fit inside the hole that the Loop region had to make. (Although I haven't seen the solution, I'm pretty sure that the loop simply had to not cross each other, so the "touching" is Masyu-like touching; going in adjacent cells is okay.)

While that alone isn't a big complaint, my issue is that I asked for clarification, but it went unanswered. I believe rule questions should be answered, because otherwise it's an unfair disadvantage for people that interpreted the ambiguous instruction incorrectly (for having an immediate contradiction like above).

For Crossmind, the fact that you need to use uniqueness metalogic also means that it's a bad puzzle. If Riad created this puzzle by also using uniqueness, I wonder how many solutions were missed; if Riad created it purely with logic, I'm interested to know the intended path.

I agree on both points. I also had to rereard the instructions several times over before solving. In the past (and this time) well-intentioned early finishers help answer questions in the forums. But surely, having a test solver reword some of the instructions beforehand would be quite productive.

Also eager to hear other people's experience with the Crossmind.

Hi, just checked why I had no points for Borderless Sextet. For the first column, the offcial answer is FXLLDVD99LQQ--B-B and mine is FXLLDVD99LQQ--B-- (only difference is a ship or not in the last cell). In my grid, I have on the last row for battleship a BBB-B- pattern which could be switched to B-BBB- to get the official solution. Could it be that the aswer is not completely unique ? Or I have made an error elsewhere that I fail to see. Could someone enlighten me ?
http://i.imgur.com/WJqx96W.jpg