Author |
Topic: covering problem (Read 339 times) |
|
BNC
Uberpuzzler
Gender: 
Posts: 1732
|
 |
covering problem
« on: Jan 19th, 2007, 2:32pm » |
 Quote  Modify
|
A friend of mine told me he think he came up with an algorithm for solving the covering problem. He asked for my help in demonstrating / proving it.
Is it a well-known problem? Is it NP or P? Are there any / many algorithms to solve it?
Thanks!
Note: The covering problem (or at least the variant I'm dealing with) is: given an area composed of squares (the area may be any shape, connected), and a cell, also composed of squares, what is the minimal number of cells needed to cover the whole area>
|
|
 IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: covering problem
« Reply #1 on: Jan 19th, 2007, 6:44pm » |
Quote Modify
|
Sounds like the Set Cover problem.
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
BNC
Uberpuzzler
Gender:
Posts: 1732
|
|
Re: covering problem
« Reply #2 on: Jan 19th, 2007, 10:14pm » |
Quote Modify
|
But is it identical?
A simple example of the covering problem I was presented with may be this:
Take a chess board, with N (N>=0) of its squares removed, but in such a way that it's still connected (one area).
Now, take a simple shape -- say a domino like 1X2 element, or a cross-like element (a center piece, and its immediate neighbors to the E, W, S, N).
How many elements are required to cover the whole area?
elements may overlap, and they may "cover" squares outside of the area. They may not be turned, though.
|
|
IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print