Cut a pizza into identical slices
PHP code, 1808 971 bytes

Quick and dirty implementation in PHP. First brute-force all possible slice shapes, next brute-force all positions and orientations of the slices. 

Usage: cat pizza.txt | php pizza.php

Edit: reduced code size by more than 45% by rewring algorithm using recursion rather than nested loops. However, this eats memory (and pizza's ;-)). Pizza's larger than 8x8 will probably run out of memory. The nested loop variant can easily handle any size, but is twice the code size.

&lt;?php define('A',98);$n=fgets(STDIN);$d=array();$m=$u=str_pad('',A,'+');$s=0;while($g=fgets(STDIN)){$g=rtrim($g);assert(strlen($g)&lt;=A-2);$s++;$m.='+'.str_pad(rtrim($g),A-2,' ').'+';for($l=0;$l&lt;strlen($g);$l++)if($g[$l]=='#')$d[]=$s*A+$l+1;}$m.=$u;$r=count($d)/$n;x(reset($d),array(array()),0,0,0,0);die('No pizza for you!');function x($e,$c,$b,$a,$q,$t){global$r,$m,$d;$h=$a*A+$b;if(!in_array($e+$h,$d))return;if(in_array($h,$c[0]))return;$c[0][]=$h;$c[1][]=$b*A-$a;$c[2][]=-$a*A-$b;$c[3][]=-$b*A+$a;if(count($c[0])&lt;$r)do{x($e,$c,$b+1,$a,$b,$a);x($e,$c,$b,$a+1,$b,$a);x($e,$c,$b-1,$a,$b,$a);x($e,$c,$b,$a-1,$b,$a);$v=($b!=$q||$a!=$t);$b=$q;$a=$t;}while($v);else w($c,$m,0,reset($d),0);}function w(&amp;$p,$f,$o,$e,$i){global$n,$d;foreach($p[$i]as$h){$j=$e+$h;if(!isset($f[$j])||$f[$j]!='#')return;$f[$j]=chr(ord('0')+$o);}if(++$o==$n){for($k=A;$k&lt;strlen($f)-A;$k++)if($k%A==A-1)echo PHP_EOL;else if($k%A)echo$f[$k];exit;}foreach($d as$j)for($i=0;$i&lt;4;$i++)w($p,$f,$o,$j,$i);}


Ungolfed, documented code

Below is the documented, original code. To keep my sanity, I worked with the full source code, and wrote a simple minifier script to strip statements like assert() and error_reporting(), remove unnecessary brackets, rename variables, functions and constants to generate the golfed code above.

&lt;?php
error_reporting(E_ALL) ;

// Width of each line of pizza shape.
// Constant will be reduced to single character by minifier,
// so the extra cost of the define() will be gained back.
define('WIDTH', 98) ;

// Read number of slices
$nrSlices = fgets(STDIN) ;

// Read pizza shape definition and 
// convert to individual $positionList[]=$y*width+$x and
// linear (1D) $pizzaShape[$y*WIDTH+$x] with protective border around it.
//
// WARNING: assumes maximum pizza width of WIDTH-2 characters!
$positionList = array() ;
$pizzaShape = $headerFooter = str_pad('', WIDTH, '+') ;
$y = 0 ;
while ($line = fgets(STDIN))
{  $line = rtrim($line) ;
   assert(strlen($line) &lt;= WIDTH-2) ;
   $y++ ;
   $pizzaShape .= '+'.str_pad(rtrim($line), WIDTH-2, ' ').'+' ;
   for ($x = 0 ; $x &lt; strlen($line) ; $x++)
   {  if ($line[$x] == '#') $positionList[] = $y*WIDTH + $x+1 ;
   }
}
$pizzaShape .= $headerFooter ;

// Determine size of a slice
$sliceSize = count($positionList)/$nrSlices ;

// Build all possible slice shapes. All shapes start with their first part at 
// the top of the pizza, and "grow" new parts in all directions next to the 
// existing parts. This continues until the slice has the full size. This way
// we end up with all shapes that fit at the top of the pizza.
//
// The shape is defined as the offsets of the parts relative to the base 
// position at the top of the pizza. Offsets are defined as linear offsets in
// the 1-D $pizzaShape string.
//
// For efficiency, we keep track of all four possible rotations while building
// the slice shape.
//
growSlice(reset($positionList), array(array()), 0, 0, 0, 0) ;
die('No pizza for you!') ;

function growSlice($basePosition, $shapeDeltas, $dx, $dy, $prevDx, $prevDy)
{  global $sliceSize, $pizzaShape, $positionList ;

   // Check validity of new position
   // Abort if position is not part of pizza, or 
   // if position is already part of slice
   $delta = $dy*WIDTH + $dx ;
   if (!in_array($basePosition+$delta, $positionList)) return ;
   if (in_array($delta, $shapeDeltas[0])) return ;

   // Add all four rotations to shapeDeltas[]
   $shapeDeltas[0][] = $delta ;
   $shapeDeltas[1][] = $dx*WIDTH - $dy ;
   $shapeDeltas[2][] = -$dy*WIDTH - $dx ;
   $shapeDeltas[3][] = -$dx*WIDTH + $dy ;

   // Have we built a full slice shape?
   if (count($shapeDeltas[0]) &lt; $sliceSize) 
   {  // Grow shape either at current position or at previous position
      do
      {  growSlice($basePosition, $shapeDeltas, $dx+1, $dy,   $dx, $dy) ;
         growSlice($basePosition, $shapeDeltas, $dx,   $dy+1, $dx, $dy) ;
         growSlice($basePosition, $shapeDeltas, $dx-1, $dy,   $dx, $dy) ;
         growSlice($basePosition, $shapeDeltas, $dx,   $dy-1, $dx, $dy) ;
         $retry = ($dx != $prevDx || $dy != $prevDy) ;
         $dx = $prevDx ;
         $dy = $prevDy ;
      } while ($retry) ;
   } else
   {  // Try to cover the entire pizza by translated and rotated instances of
      // the slice shape.
      fitSlice($shapeDeltas, $pizzaShape, 0, reset($positionList), 0) ;
   }
}

function fitSlice(&amp;$shape, $pizza, $id, $basePosition, $rotation)
{  global $nrSlices, $positionList ;

   // Try to fit each part of the slice onto the pizza. If the part falls
   // outsize the pizza, or overlays another slice we reject this position
   // and rotation. If it fits, we mark the $pizza[] with the slice $id.
   foreach ($shape[$rotation] as $delta)
   {  $position = $basePosition + $delta ;
      if (!isset($pizza[$position]) || $pizza[$position] != '#') return ;
      $pizza[$position] = chr(ord('0')+$id) ;
   }

   // If $nrSlices slices have been fitted, we have found a valid solution!
   // In that case, we display the solution and quit.
   if (++$id == $nrSlices)
   {  for ($pos = WIDTH ; $pos &lt; strlen($pizza)-WIDTH ; $pos++)
      {  if ($pos % WIDTH == WIDTH-1) echo PHP_EOL ;
         else if ($pos % WIDTH) echo $pizza[$pos] ;
      }
      exit ;
   }

   // The current slice did fit, but we have still more slices to fit.
   // Try all positions and rotations for the next slice.
   foreach ($positionList as $position)
   {  for ($rotation = 0 ; $rotation &lt; 4 ; $rotation++)
      {  fitSlice($shape, $pizza, $id, $position, $rotation) ;
      }
   }
}