disoriented
Level: Smitemaster

Rank Points: 2384
Registered: 08-07-2007
IP: Logged

As a followup to this topic.

Do you know how to write a solver for Fillomino?

It’s potentially an Exact Cover variant similar to the Tetris tiling problem (without colors this time), but the pieces can be any size. As an additional restriction, no N-omino can border another N-omino of the same degree.

Puzzle:

?121?
????2
41??4
?51?3
???1?

Solution:

41212
44242
41444
55133
55513

I’d like to try to solve this the same way as in Tetris tiling -- but for each unknown space, it seems you’d have to try every omino size from 1 up to some upper bound AND all possible orientations for it. Impractical?

Challenge Puzzle:

??6?9?7??5?
?6?3?4??3??
??29??2?15?
??4???1????
4?1?5???66?
?7??5??56?3
??????3??6?
?468??????5
6???8?4????
??48?873?6?
??2??????6?

____________________________
34th Skywatcher

Best to PM me, since I might miss your message on CaravelNet chat.

---

[Last edited by disoriented at 12-30-2014 01:13 AM]

Kallor
Level: Master Delver
Rank Points: 277
Registered: 04-02-2007
IP: Logged

How about dividing the posible omioes into 2 categories: those that contain some initial numbers (all of which have the same value) and those that don't. Then you can enumerate them by making a loop over starting tiles and having the omino grow from that tile like a disease; in the first category avoiding any numbers different from the number in the starting tile and growing until it is the size of the number in the staring tile, and in the second category avoiding all numbered tiles and growing up to any size. To avoid counting the same omino several times, once the starting tile is used up in the loop it is completely forbidden for any other omino starting from a different tile, and while the omino grows make an agreement that growing from a tile needs to happen North first, then East, South and West (meaning for example that if the omino grows to South from some tile it may never again grow to North or East from that tile).

Surely this would be very unpractical, but not too slow I think. There will anyways be less than 2^n subsets (I think some lesser exponential function when we demand that the subset is connected), while the dancing links looks like it may take up to m! (m is the number of subsets, not sure about this) steps. So the preparation code should only take a fraction of time compared to the algorithm itself.

____________________________
Kallor

TripleM
Level: Smitemaster
Rank Points: 1373
Registered: 02-05-2003
IP: Logged

DLX isn't possible anyway as there's no way to represent the constraint of not having two adjacent polyominoes of the same degree.

The same general principles apply though - working with more restricted areas of the board will lead to a faster solution. Equally, the quicker you can decide a partial solution is invalid the better.

I would probably approach this by using human logic to begin with - figuring out the techniques that allow a human to fill in forced unknown cells, and getting the algorithm to do the same thing. Before every stage of the backtracking this can be repeated, preventing you from looping over lots of unnecessary options. Given these are designed for humans, and have unique solutions, if done correctly it's likely this will solve the majority for you anyway leaving backtracking only where necessary.

(One example: for each numbered square, loop over every polyomino containing that square. Rather than recurse, check if all options share any square(s). If so, fill in that square. Repeat this process until you can't make any more updates. Then start the backtracking.)

---

[Last edited by TripleM at 12-30-2014 09:06 PM]

Kallor
Level: Master Delver
Rank Points: 277
Registered: 04-02-2007
IP: Logged

Oh, I forgot about that extra constraint.

Still applying DLX is possible. Add 9 (replace 9 with the maximum of the initial numbers in the puzzle if it's allowed to be more) new "mini-tiles" labeled from 1 to 9 to each edge of the grid. Make the convention that an n-omino occupies (in addition to the n normal tiles) the "mini-tiles" labeled n on its boundaries. Allow also shapes that cover exactly 1 "mini-tile" and nothing else. Now two adjacent n-ominoes will overlap but adjacent n- and m-ominoes won't when n is not m. In addition the grid can be completely covered with the help of the new shapes.

This might not be the way you want to take, though.
EDIT: On the second thought it just might. The new matrix is only 10 times wider and a little bit taller, considering there is 9n new shapes and probably about exp(n) shapes to begin with.

____________________________
Kallor

---

[Last edited by Kallor at 12-30-2014 10:30 PM]

TripleM
Level: Smitemaster
Rank Points: 1373
Registered: 02-05-2003
IP: Logged

Ah yeah, good point. Just tried that and it worked fine on the smaller grid, but shows no signs of stopping on the larger one - only 8397 rows* but there's just too many possibilities for it to consider. I think the logic-based method I described above will perform much better.

*assuming an upper limit of 9-ominoes

---

[Last edited by TripleM at 12-31-2014 01:05 AM]

TripleM
Level: Smitemaster
Rank Points: 1373
Registered: 02-05-2003
IP: Logged

Managed to code up something logic based which came up with this in about 8 seconds.. code could be optimised a lot:

66639977355
66339427335
62299427155
44499417666
47195477663
77795555633
44777833365
44688844665
66668443365
64488873765
44227777765

disoriented
Level: Smitemaster

Rank Points: 2384
Registered: 08-07-2007
IP: Logged

TripleM wrote: about 8 seconds.

Wow -- really good! Do you mind sharing your program so I can learn from it?

____________________________
34th Skywatcher

Best to PM me, since I might miss your message on CaravelNet chat.

---

[Last edited by disoriented at 12-31-2014 08:24 AM]

disoriented
Level: Smitemaster

Rank Points: 2384
Registered: 08-07-2007
IP: Logged

Another test puzzle, max polyomino size is 10.

??????3?????
??46?9???53?
41?9??65?6?7
?7?1?24???7?
??3??2???7??
?6?3??1?3?7?
6????1??2?A?
?65?1???????
5??1?32?5??7
???7??7??57?
?5?8?74?6???
?1?????4?7??

(A = 10)


____________________________
34th Skywatcher

Best to PM me, since I might miss your message on CaravelNet chat.

---

[Last edited by disoriented at 01-01-2015 01:08 AM]

TripleM
Level: Smitemaster
Rank Points: 1373
Registered: 02-05-2003
IP: Logged

File: ntiling2.cpp (5.2 KB)
Downloaded 46 times.
License: Public Domain

About 13 seconds:



My (messy) code basically does the following:

- have an array of booleans stating whether the number 'z' is not allowed to go in position (x,y) (initially all false)

- have a 'valid' function: for each numbered square, test if there exists a polyomino that fits in the grid and covers that square (considering the current grid and the above array)

- have a 'forced' function: for each question mark, try filling it with a certain number and test if valid returns false. If so, add this to the above array. If all but one number are disallowed for a square, fill it in with the remaining option. Keep repeating this until we can't update anything else.

- extend the above slightly - for each question mark, try filling it with a certain number, then called the forced function and see if the result is still valid. If not, add it to the above array, and repeat.

That doesn't guarantee solving the whole grid, but does in all of these cases (and I expect always would when there's a unique solution).

---

[Last edited by TripleM at 01-01-2015 02:59 AM]

disoriented
Level: Smitemaster

Rank Points: 2384
Registered: 08-07-2007
IP: Logged

(and I expect always would when there's a unique solution).

I don't believe that's correct. Try this:

????87??????
?48?4?7??4B2
????7?77?3??
?74??7??B???
?7???5???28?
?7?A?AB???8?
43?????4??5?
??4??A?88?2?
5?7??16????8
?5??6????8??
55?A?9?68?32
?????????8??

(A=10, B=11)

____________________________
34th Skywatcher

Best to PM me, since I might miss your message on CaravelNet chat.

---

[Last edited by disoriented at 01-03-2015 10:29 AM]

lopsidation
Level: Master Delver

Rank Points: 176
Registered: 05-30-2008
IP: Logged

Here's a fillomino which is trivial for humans, but hard without heuristics or backtracking:

??????
?4?S4?
??????
??????
?4??4?
??????

(S=28)

Fillomino is NP-complete, so you'll need some kind of backtracking to solve it in general. Assuming P != NP.

____________________________
"Happiness is like a cat. If you pay no attention to it and go about your business, you'll find it rubbing against your legs and jumping into your lap."