This one was again a good challenge.
The missing border, moving the tiles within their pictures and the varying background colours were no problem. What made it quite a bit more difficult is that there are only eight different border patterns, so every eighth piece matches instead of every 32nd as in the prior challenge. This was made worse by having many more pieces to begin with.
Shredded and Scrambled
I'm glad you liked it!
I thought about doing only 2 or 4 possibilities for each connection, but maybe that would be much harder.
The change of background color and of the piece position in the file werw only supposed to change a little bit the solver for this challenge compared to the previous one.
Was the increased number of pieces a problem for you, Tron? And have you started to assemble the jigsaw puzzle from which piece/group of pieces?
Cheers,
Bruno
I thought about doing only 2 or 4 possibilities for each connection, but maybe that would be much harder.
The change of background color and of the piece position in the file werw only supposed to change a little bit the solver for this challenge compared to the previous one.
Was the increased number of pieces a problem for you, Tron? And have you started to assemble the jigsaw puzzle from which piece/group of pieces?
Cheers,
Bruno
Not per se, but it in combination with the smaller edges it made it harder: It is four times more likely that another piece fits (1 in 8 instead of 1 in 32) and there are 3.3125 times the number pieces, so there are on average 13.25 times the candidates at each place. Mostly the effect was that my solver to longer to decide on the next piece.bsguedes wrote:Was the increased number of pieces a problem for you, Tron?
I just started with a random piece. At some point the big sign popped up.And have you started to assemble the jigsaw puzzle from which piece/group of pieces?
So even for the first challenge your solver looked for candidates according to piece's colors?
Because for the first level I thought it was easier to assemble all borders like this :
Once you had the 'x' pieces positioned, to determine the 'y' pieces was not hard because you have one piece in 1024 that would match. Then it would be easy to find 'z' pieces and so on. I think 95% of the first challenge solvers used this strategy.
The idea of removing the borders was to turn this approach impossible for the second challenge. But it seems you were smarter and used an strategy that worked well for both levels without too much modifications between both solvers ^^
EDIT: to answer your question in the other topic about filenames. In this challenge I meant to have some significance for the filenames of the pieces. I've concatenated some piece information for each piece (i.e. the codes of connections (four numbers between 0 and 7), the background color, and the x,y position of the piece in the picture, with some random numbers too) and this information had 80 bits for each piece, so 20 characters each filename for a hexadecimal representation. But I was stupid and I submitted the file to adum without seeing that the filename generation was erroneous: for all the parts of the filename where I had non-significant 0s to the left in the binary representation I've lost those bits and that's the reason why the filename's sizes don't have the same length.
Because for the first level I thought it was easier to assemble all borders like this :
Code: Select all
xxxxxxxxxx
xyz zyx
xz zx
x x
xz zx
xyz zyx
xxxxxxxxxxThe idea of removing the borders was to turn this approach impossible for the second challenge. But it seems you were smarter and used an strategy that worked well for both levels without too much modifications between both solvers ^^
EDIT: to answer your question in the other topic about filenames. In this challenge I meant to have some significance for the filenames of the pieces. I've concatenated some piece information for each piece (i.e. the codes of connections (four numbers between 0 and 7), the background color, and the x,y position of the piece in the picture, with some random numbers too) and this information had 80 bits for each piece, so 20 characters each filename for a hexadecimal representation. But I was stupid and I submitted the file to adum without seeing that the filename generation was erroneous: for all the parts of the filename where I had non-significant 0s to the left in the binary representation I've lost those bits and that's the reason why the filename's sizes don't have the same length.
I think your suggested approach is infeasible. On the edge one in 32 pieces fit, so about 2 or 3, and in the middle one in 1024 (if you have two neighbours placed), so about 4. So you have multiple pieces to choose from at every place, this is exponential in the number of places. It's easily more combinations than particles in the universe. My very first test was similar to this and produced absolute garbage as result.
-
TheBigBoss
- Posts: 29
- Joined: Thu Jun 07, 2012 12:07 pm
- Location: Germany
Seems I am the only one who let a lot of work to himself ... I used the interactive solver from the previous level and added some kind of sorting by edge matches.
I had mostly the required piece among first 10 when having 2 borders known.
When having one border known and interesting color edge in the piece, I had the piece in about first 80 (often much sooner).
When on darker (nonflicked) regions it determined several pieces themselve, but on flicked regions it needed assistance. I had to change the interface to allow emphasize the color differences to help me detect bad matches manually in the problematic regions.
I probably should have experimented more with both the sorting and the automated backtracking.
Actually I was thinking about the code matching the cross patterned pieces when I was not able to start.
But occassionally while experimenting with matches, 4 pieces of a STOP sign appeared, so I got a starting point. After a while big part of the front car appeared, so I have started the "manual puzzling".
When I have connected the JO mossaic part with the part containing the 2 cars, I have seen the answer on both the mosaic and the wall, so I tried it.
... Now I am not sure I will finish the puzzle.
I had mostly the required piece among first 10 when having 2 borders known.
When having one border known and interesting color edge in the piece, I had the piece in about first 80 (often much sooner).
When on darker (nonflicked) regions it determined several pieces themselve, but on flicked regions it needed assistance. I had to change the interface to allow emphasize the color differences to help me detect bad matches manually in the problematic regions.
I probably should have experimented more with both the sorting and the automated backtracking.
Actually I was thinking about the code matching the cross patterned pieces when I was not able to start.
But occassionally while experimenting with matches, 4 pieces of a STOP sign appeared, so I got a starting point. After a while big part of the front car appeared, so I have started the "manual puzzling".
When I have connected the JO mossaic part with the part containing the 2 cars, I have seen the answer on both the mosaic and the wall, so I tried it.
... Now I am not sure I will finish the puzzle.
I have continued a bit even after submitting the answer.
At first I have looked at the code to see it was actually not sorting by color simillarity at all.
So making it to do some sort improved the heuristics a lot.
I have finished colored regions, just I have resigned on several regions not bearing an information.
... I have not joined the "Hairy part" on the right bottom nor the "stripes" in the left bottom corner.
Redford@: are you sure the fill of remaining regions you did is correct? Arenot there other almost equally good fills?
I could imagine running the matching algorithm with some kind of limited backtracking not based on adding pieces one by one, but choosing best total evaluation of adding several pieces at once.
May be I will experiment with such an algorithm in far future
.
Did some solver used simillarity of images in top right corner with images in top left corner
(trying to eliminate the color transformation on left and the transformation on right for which I cannot find a good name)?
At first I have looked at the code to see it was actually not sorting by color simillarity at all.
So making it to do some sort improved the heuristics a lot.
I have finished colored regions, just I have resigned on several regions not bearing an information.
... I have not joined the "Hairy part" on the right bottom nor the "stripes" in the left bottom corner.
Redford@: are you sure the fill of remaining regions you did is correct? Arenot there other almost equally good fills?
I could imagine running the matching algorithm with some kind of limited backtracking not based on adding pieces one by one, but choosing best total evaluation of adding several pieces at once.
May be I will experiment with such an algorithm in far future
.Did some solver used simillarity of images in top right corner with images in top left corner
(trying to eliminate the color transformation on left and the transformation on right for which I cannot find a good name)?
I'm quite sure about that. If you zoom enough you can see "seems" on badly matched pieces. Yeah, there are many similar pieces that can match well, but if you put one in a wrong place, even if it fits good, the next one will not match (because of another edge pattern than in correct piece, which is very likely).Hippo wrote:Redford@: are you sure the fill of remaining regions you did is correct? Arenot there other almost equally good fills?
I created an image that seems to not have any "seems" between any pair of pieces, so it's likely to be the correct one
If you finish the whole image we can compare the results (if you want).Good luckHippo wrote:I could imagine running the matching algorithm with some kind of limited backtracking not based on adding pieces one by one, but choosing best total evaluation of adding several pieces at once.
May be I will experiment with such an algorithm in far future
Did some solver used simillarity of images in top right corner with images in top left corner
(trying to eliminate the color transformation on left and the transformation on right for which I cannot find a good name)?
No, I haven't used that similarity.
-
go.to.hell
- Posts: 5
- Joined: Fri Dec 25, 2009 4:25 pm
My not optimized Implementation of http://www.cv-foundation.org/openaccess ... _paper.pdf solves the Challenge in under 2 Hours.
-
go.to.hell
- Posts: 5
- Joined: Fri Dec 25, 2009 4:25 pm
I implemented a variation of that algorithm at http://webee.technion.ac.il/~ayellet/Ps/15-PT.pdf. It also needs some modification due to the different edges (I just assigned a dissimilarity of inf to them). It solves the challenge in a few minutes. A small number of pieces were placed incorrectly but I didn't bother doing additional fine-tuning. Anyways, very instructive challenge! =)go.to.hell wrote:My not optimized Implementation of http://www.cv-foundation.org/openaccess ... _paper.pdf solves the Challenge in under 2 Hours.
Nice links, I should try these approaches.
I have not transformed the pieces to LAB color space and I used RGB in the disimilarity computation.
I have not accelerated by distance of color averages, but by color interval's intersection and border shape.
Most of the time the best buddies were not applicable and just best neighbour of the partial solution was selected.
... OK, OK I had buggy disimilarity calculation.
After several experiments, the algorithm works rather well except the right up corner where it is almost clueless. After several more experiments with neihbour evaluation the right up corner starts looking interesting ... I had to evaluate not only diference from linearity on border in the direction, but in perpendicullar direction as well.
I will try the genetics one.
The genetics was may be a bit better in upper right, but actually the generation after first cross was almost as good/bad as all other generations. Making better edge evaluator for upright corner not confused by "grid modulator" would probbaly help both methods almost equally well.
... this approach lead to almost mess ... there were some regions with about 8 neighbouring pieces placed well ... (actually there does not exist starting piece according their restrictions so I had to modify even the initial selection) seems my interpretation of the paper was much worse then yours.dxer wrote: I implemented a variation of that algorithm at http://webee.technion.ac.il/~ayellet/Ps/15-PT.pdf. It also needs some modification due to the different edges (I just assigned a dissimilarity of inf to them). It solves the challenge in a few minutes. A small number of pieces were placed incorrectly but I didn't bother doing additional fine-tuning. Anyways, very instructive challenge! =)
I have not transformed the pieces to LAB color space and I used RGB in the disimilarity computation.
I have not accelerated by distance of color averages, but by color interval's intersection and border shape.
Most of the time the best buddies were not applicable and just best neighbour of the partial solution was selected.
... OK, OK I had buggy disimilarity calculation.
After several experiments, the algorithm works rather well except the right up corner where it is almost clueless. After several more experiments with neihbour evaluation the right up corner starts looking interesting ... I had to evaluate not only diference from linearity on border in the direction, but in perpendicullar direction as well.
I will try the genetics one.
The genetics was may be a bit better in upper right, but actually the generation after first cross was almost as good/bad as all other generations. Making better edge evaluator for upright corner not confused by "grid modulator" would probbaly help both methods almost equally well.