I made three simple changes.
First: start $cnt as $n*$n instead of 1.
Second: change while loop to continue until $cnt is not greater then 0.
Third: decrement $cnt everywhere it was incremented before.

#!/usr/bin/perl -w

use strict;

print "Enter n: ";
chomp(my $n = <>);

my @shiza;
my $firstD = my $secondD = 0;
my $cnt    = $n*$n; 
my $inc     = 1;

while ($cnt > 0) {
   while (!$shiza[$firstD][$secondD] && $secondD < $n && $inc == 1) {
      $shiza[$firstD][$secondD] = $cnt;
      $secondD++ unless($shiza[$firstD][$secondD+1] || ($secondD+1) >=
+ $n);
      $cnt--;
   }
   $firstD++;

   while (!$shiza[$firstD][$secondD] && $firstD < $n && $inc == 1) {
      $shiza[$firstD][$secondD] = $cnt;
      $firstD++ unless($shiza[$firstD+1][$secondD] || ($firstD+1) >= $
+n);
      $cnt--;
   }
   $secondD--;
   $inc = 0;

   while (!$shiza[$firstD][$secondD] && $secondD >= 0 && $inc == 0) {
      $shiza[$firstD][$secondD] = $cnt;
      $secondD-- unless($shiza[$firstD][$secondD-1] || ($secondD-1) < 
+0);
      $cnt--;
   }
   $firstD--;

   while (!$shiza[$firstD][$secondD] && $firstD >= 0 && $inc == 0) {
      $shiza[$firstD][$secondD] = $cnt;
      $firstD-- unless($shiza[$firstD-1][$secondD] || ($firstD-1) < 0)
+;
      $cnt--;
   }
   $secondD++;
   $inc = 1;
}

for (@shiza) {
   for (@{$_}) {
      print "$_\t" if($_);
   }
   print "\n";
}
[download]