C# - 897 862 bytes
Found a serious bug with it putting mirrors in places that they can't be. Now it works, hopefully! Also did some light golfing, couldn't leave the while loop in there... shameful.
Complete program, takes input from STDIN, outputs to STDOUT.
This was a lot of fun, it copes fine with the 7 by 5 problem (and when you remove one of the mirrors, making it impossible), took about 1 hour to solve the 30 by 5.
using Q=System.Console;class P{static int w,L;static string S(char[]M,int t,int r,int i,int d,int[]B){var s="";if(r<0)return s;M=(char[])M.Clone();B=(int[])B.Clone();B[i]=1;for(i+=d;M[t]<48|t==i;i=t+(d=t<w?w:t>L-w?-w:t%w<1?1:-1))if(++t>=L){for(i=0;++i<L&r>0;)if(B[i]<1&M[i]<33){M[i]='.';r--;}return r<1?new string(M):s;}int c=M[i];if(c>32)s=c>47|c<46?s=c==M[t]?S(M,t,r,t,0,B):s:S(M,t,r,i,c<47?w/d:-w/d,B);else if((s=S(M,t,r,i,d,B))==""&B[i]<1){M[i]='.';s=S(M,t,r-1,i,w/d,B);if(s==""){M[i]='/';s=S(M,t,r-1,i,-w/d,B);}}return s;}static void Main(){string a,A="",R=A;for(;(a=Q.ReadLine())!=null;A+=a)L+=(w=a.Length);var G=A.ToCharArray();int r=0,i=L;for(;i>0;G[i]=G[i]=='|'?',':G[i])if(G[--i]==47|G[i]==92){r++;G[i]=' ';}a=S(G,0,r,1,w,new int[L]);if(a=="")R="Impossible\n";else for(;i<L;i+=w)R+=a.Substring(i,w)+"\n";Q.Write(R.Replace(".","\\").Replace(",","|"));}}
7 by 5 Example:
+abcde+
f/////d
a// c
f |
+-b-e-+
+abcde+
f \ d
a/ //c
f/ \ /|
+-b-e-+
Impossible version:
+abcde+
f ////d
a// c
f |
+-b-e-+
Impossible
Something different (the program doesn't look at the original mirror layout):
+a----+
|//// |
|/////|
|/////|
+----a+
+a----+
| /\\\|
|\\\\\|
|\\/\\|
+----a+
30 by 5 solution:
+abcdefghijklmnopqrstuvwxyA-+
| \\\\\\\\\\\\\\\\\\\\\\\\ \|
| / //|
|\ \|
+-Abcdefghijklmnopqrstuvwxya+
It looks at each laser source in turn, and builds a valid route for it (if it can), and then moves onto the next. It's a pretty simple depth-first search, which has to know which laser source (target) it's looking at, how many mirrors it remain for it to place, the current cell it's "at", the direction it's moving in, and each cell it's visited already (so that it doesn't put a mirror somewhere it's already been). The last 3 are used for assembling the path for the current target, and at reset when the target changes. Once it's got all the lasers linked up, it goes ahead and fills in any gaps it doesn't need left empty (another reason it needs to know everywhere it's visited).
When it's building routes, it favours going "forward" over inserting a mirror, and when it does, it favours a "\" mirror - this is best seen in the "something different" example above, where it skips the first cell below the top-most 'a', then continually fills out a "\" if it can find a solution with one, otherwise a "/" (naturally, if skipping the first cell resulted in it being unable to find a solution, then it would back-track and try putting a mirror there instead).
using Q=System.Console;
class P
{
static int w,L;
// M is cur grid
// t is target edge thing (0->L)
// r is mirrors remaining
// i is pos
// d is dir
static string S(char[]M,int t,int r,int i,int d,int[]B)
{
var s="";
if(r<0) // no mirrors left
return s;
// clone everything
M=(char[])M.Clone();
B=(int[])B.Clone();
B[i]=1; // can't write to this
for(i+=d; // move i
M[t]<48|t==i; // only if target is something sensible (increment if i==t)
i=t+(d=t<w?w:t>L-w?-w:t%w<1?1:-1)) // reflect, should be fine for w=3
if(++t>=L) // run off the end
{
for(i=0;++i<L&r>0;) // don't need I any more (count through everything)
if(B[i]<1&M[i]<33) // not been here & it's open space
{
M[i]='.'; // doesn't matter
r--;
}
return r<1?new string(M):s; // none remaining ? victory : defeat
}
int c=M[i];
if(c>32) // not boring
s=c>47|c<46? // hit edge
s=c==M[t]? // hit the correct thing
S(M,t,r,t,0,B): // i+0=t, tells it to increment t
s
:S(M,t,r,i,c<47?w/d:-w/d,B); // mirror
else // boring
if((s=S(M,t,r,i,d,B))==""&B[i]<1) // fwd
{
M[i]='.'; // use . instead of \
s=S(M,t,r-1,i,w/d,B); // \
if(s=="")
{
M[i]='/';
s=S(M,t,r-1,i,-w/d,B); // /
}
}
return s;
}
static void Main()
{
string a,A="",R=A; // R is free
for(;(a=Q.ReadLine())!=null;A+=a) // read input
L+=(w=a.Length); // note width, accumulate length
var G=A.ToCharArray();
int r=0,i=L; // count mirrors (I refuse to make these static)
for(;i>0; // end on i=0
G[i]=G[i]=='|'?',':G[i]) // replace | with ,
if(G[--i]==47|G[i]==92) // remove and count mirrors
{
r++;
G[i]=' '; // storing G[i] doesn't seem to save anything
}
// search
a=S(G,0,r,1,w,new int[L]);
if(a=="") // defeat
R="Impossible\n";
else // victory
for(;i<L;i+=w) // for each line
R+=a.Substring(i,w)+"\n";
Q.Write(R.Replace(".","\\").Replace(",","|")); // swap back | and \
}
}
3This sounds like a hard problem, regardless of golfing. – orlp – 2015-04-02T09:36:59.867
2
Hint: brute force is not an option; it will take you 3 universe ages at 10k options per second for the larger example.
– Sanchises – 2015-04-02T14:01:22.320@sanchises I think it will take a great deal longer, as any mirror can be flipped, so I think you need a
* 2^30
component in there as well – VisualMelon – 2015-04-03T09:02:58.457Extra hint: You will need to exploit properties of the puzzle to prune your search space. You might also using combinations of partial solutions or hillclimbing from partial solutions that are close to a complete solution. It is now valid to answer with simpler solutions, so programs that solve one or two mirror puzzles are welcome too. – Logic Knight – 2015-04-03T09:33:51.250