#!/bin/perl

use strict;
use warnings;
use Time::Stopwatch;
tie my $timer, 'Time::Stopwatch';

#@ARGV = ( "1549.......8..426....8....9.....63....6.2..743421...5.4..6839.....7.5.1.6.7.9...." );
#@ARGV = ( "15.9.......8..426....8....9.....63....6.2..743421...5.4..6839.....7.5.1.6.7.9...." );
#@ARGV = ( ".........46.13.8...3..8.1.7.76...4.............5...71.7.3.6..4...4.21.35........." );
#@ARGV = ( "5......169....7.......38....79........3.2.9........54....97.......3....768......1" );
#@ARGV = ( "........1.....2.3...4..5..........5......46...17.8........1...7.2.9.....5.....4.." );
#@ARGV = ( "................................................................................." );

my(@board, @marks, @rowCnt, @colCnt, @squCnt);

#---------------------------- initBoard() ------------------------------------#
sub initBoard {
  if ( $#ARGV || (length($ARGV[0]) != 81) ) {
    printf("ERROR: invalid input (need %s)\n", $#ARGV ? "argument" : "81 characters");
    exit(-1);
  }

  map { my $row=$_; map { $board[$row][$_] = 0 } ( 0..8 ) } ( 0..8 );
  map { my $row=$_; map { my $col=$_; map { $marks[$row][$col][$_] = 0 } ( 1..9 ) } ( 0..8 ) } ( 0..8 );
  map { my $idx=$_; map { $rowCnt[$idx][$_] = $colCnt[$idx][$_] = $squCnt[$idx][$_] = 9 } ( 1..9 ) } ( 0..8 );

  for my $row ( 0..8 ) {
    for my $col ( 0..8 ) {
      my($val) = substr($ARGV[0], $row*9 + $col, 1);

      if ( ($val ne '.') && (existsInRow($row, $val) || existsInCol($col, $val) || existsInSqu($row, $col, $val)) ) {
        printf("ERROR: invalid input '$val' (row: %d, col: %d)\n", $row+1, $col+1);
        exit(-1);
      }

      setCell($row, $col, ($val eq '.') ? 0 : $val);
    }
  }
}

#---------------------------- nextCell() -------------------------------------#
sub nextCell {
  my($row, $col) = @_;

  $row++ unless ( ($col = ($col + 1) % 9) );

  return($row, $col);
}

#---------------------------- existsInRow() ----------------------------------#
sub existsInRow {
  my($row, $val) = @_;

  map { return(1) if ( $board[$row][$_] == $val ) } ( 0..8 );

  return(0);
}

#---------------------------- existsInCol() ----------------------------------#
sub existsInCol {
  my($col, $val) = @_;

  map { return(1) if ( $board[$_][$col] == $val ) } ( 0..8 );

  return(0);
}

#---------------------------- existsInSqu() ----------------------------------#
sub existsInSqu {
  my($row, $col, $val) = ( 3 * int($_[0] / 3), 3 * int($_[1] / 3), $_[2] );

  return(($val == $board[$row]  [$col]) || ($val == $board[$row]  [$col+1]) || ($val == $board[$row]  [$col+2]) ||
         ($val == $board[$row+1][$col]) || ($val == $board[$row+1][$col+1]) || ($val == $board[$row+1][$col+2]) ||
         ($val == $board[$row+2][$col]) || ($val == $board[$row+2][$col+1]) || ($val == $board[$row+2][$col+2]));
}

#---------------------------- markCell() -------------------------------------#
sub markCell {
  my($row, $col, $val) = @_;
  my($squIdx)          = 3*int($row/3)+int($col/3);

  if ( $val ) {
    for my $tmpVal ( 1..9 ) {
      if ( ! $marks[$row][$col][$tmpVal] ) {
        $rowCnt[$row][$tmpVal]--;
        $colCnt[$col][$tmpVal]--;
        $squCnt[$squIdx][$tmpVal]--;
        $marks[$row][$col][$tmpVal] = 1;
      }
    }
  }
}

#---------------------------- markRow() --------------------------------------#
sub markRow {
  my($row, $col, $val) = @_;
  my($squRow) = 3*int($row/3);
  my($cnt) = 0;

  if ( $val ) {
    for my $tmpCol ( 0..8 ) {
      my($squIdx) = $squRow+int($tmpCol/3);

      if ( ! $marks[$row][$tmpCol][$val] ) {
        $rowCnt[$row][$val]--;
        $colCnt[$tmpCol][$val]--;
        $squCnt[$squIdx][$val]--;
        $cnt++;
        $marks[$row][$tmpCol][$val] = 1;
      }
    }
  }

  return($cnt);
}

#---------------------------- markRowExceptTwo() -----------------------------#
sub markRowExceptTwo {
  my($row, $col1, $col2, $val) = @_;
  my($squRow) = 3*int($row/3);
  my($cnt) = 0;

  if ( $val ) {
    for my $tmpCol ( 0..8 ) {
      next if ( ($tmpCol == $col1) || ($tmpCol == $col2) );

      my($squIdx) = $squRow+int($tmpCol/3);

      if ( ! $marks[$row][$tmpCol][$val] ) {
        $rowCnt[$row][$val]--;
        $colCnt[$tmpCol][$val]--;
        $squCnt[$squIdx][$val]--;
        $cnt++;
        $marks[$row][$tmpCol][$val] = 1;
      }
    }
  }

  return($cnt);
}

#---------------------------- markCol() --------------------------------------#
sub markCol {
  my($row, $col, $val) = @_;
  my($squCol) = int($col/3);
  my($cnt) = 0;

  if ( $val ) {
    for my $tmpRow ( 0..8 ) {
      my($squIdx) = 3*int($tmpRow/3)+$squCol;

      if ( ! $marks[$tmpRow][$col][$val] ) {
        $rowCnt[$tmpRow][$val]--;
        $colCnt[$col][$val]--;
        $squCnt[$squIdx][$val]--;
        $cnt++;
        $marks[$tmpRow][$col][$val] = 1;
      }
    }
  }

  return($cnt);
}

#---------------------------- markColExceptTwo() -----------------------------#
sub markColExceptTwo {
  my($col, $row1, $row2, $val) = @_;
  my($squCol) = int($col/3);
  my($cnt) = 0;

  if ( $val ) {
    for my $tmpRow ( 0..8 ) {
      next if ( ($tmpRow == $row1) || ($tmpRow == $row2) );

      my($squIdx) = 3*int($tmpRow/3)+$squCol;

      if ( ! $marks[$tmpRow][$col][$val] ) {
        $rowCnt[$tmpRow][$val]--;
        $colCnt[$col][$val]--;
        $squCnt[$squIdx][$val]--;
        $cnt++;
        $marks[$tmpRow][$col][$val] = 1;
      }
    }
  }

  return($cnt);
}

#---------------------------- markSqu() --------------------------------------#
sub markSqu {
  my($row, $col, $val)   = @_;
  my($snapRow, $snapCol) = ( 3*int($row/3) , 3*int($col/3) );
  my($cnt) = 0;

  if ( $ val ) {
    for my $subRow ( 0..2 ) {
      for my $subCol ( 0..2 ) {
        my($tmpRow, $tmpCol) = ( $snapRow+$subRow, $snapCol+$subCol);
        my($squIdx)          = 3*int($tmpRow/3)+int($tmpCol/3);

        if ( ! $marks[$tmpRow][$tmpCol][$val] ) {
          $rowCnt[$tmpRow][$val]--;
          $colCnt[$tmpCol][$val]--;
          $squCnt[$squIdx][$val]--;
          $cnt++;
          $marks[$tmpRow][$tmpCol][$val] = 1;
        }
      }
    }
  }

  return($cnt);
}

#---------------------------- setCell() --------------------------------------#
sub setCell {
  my($row, $col, $val) = @_;

  if ( ! $board[$row][$col] ) {
    markCell($row, $col, $val);
    markRow($row, $col, $val);
    markCol($row, $col, $val);
    markSqu($row, $col, $val);
    $board[$row][$col] = $val;

    return(1);
  }

  return(0);
}

#---------------------------- findSinglesInRow() -----------------------------#
sub findSinglesInRow {
  my($gotSingles) = 0;

  for my $val ( 1..9 ) {
    for my $row ( 0..8 ) {
      next if ( $rowCnt[$row][$val] != 1 );

      for my $col ( 0..8 ) {
        if ( ! $marks[$row][$col][$val] ) {
          $gotSingles++;
          setCell($row, $col, $val);
          last;
        }
      }
    }
  }

  return($gotSingles);
}

#---------------------------- findSinglesInCol() -----------------------------#
sub findSinglesInCol {
  my($gotSingles) = 0;

  for my $val ( 1..9 ) {
    for my $col ( 0..8 ) {
      next if ( $colCnt[$col][$val] != 1 );

      for my $row ( 0..8 ) {
        if ( ! $marks[$row][$col][$val] ) {
          $gotSingles++;
          setCell($row, $col, $val);
          last;
        }
      }
    }
  }

  return($gotSingles);
}

#---------------------------- findSinglesInSqu() -----------------------------#
sub findSinglesInSqu {
  my($gotSingles) = 0;
  my($hitRow, $hitCol);

  for my $val ( 1..9 ) {
    for my $squIdx ( 0..8 ) {
      my($row, $col) = ( 3*int($squIdx/3), 3*($squIdx%3) );
      my($cnt) = 0;

      for my $subRow ( 0..2 ) {
        for my $subCol ( 0..2 ) {
          my($tmpRow, $tmpCol) = ( $row+$subRow, $col+$subCol );

          if ( ! $marks[$tmpRow][$tmpCol][$val] ) {
            $hitRow = $tmpRow;
            $hitCol = $tmpCol;
            $cnt++;
          }
        }
      }

      if ( $cnt == 1 ) {
        $gotSingles++;
        setCell($hitRow, $hitCol, $val);
      }
    }
  }

  return($gotSingles);
}

#---------------------------- getZeroSubCoords() -----------------------------#
sub getZeroSubCoords {
  my($snapRow, $snapCol, $val, $n) = @_;
  my(@rows, @cols);

  for my $subRow ( 0..2 ) {
    for my $subCol ( 0..2 ) {
      my($row, $col) = ( $snapRow+$subRow, $snapCol+$subCol );

      if ( ! $marks[$row][$col][$val] ) {
        push(@rows, $row);
        push(@cols, $col);

        return(@rows, @cols) if ( @rows == $n );
      }
    }
  }
}

#---------------------------- matchDoublePairs() -----------------------------#
sub matchDoublePairs {
  my($snapRowA, $snapColA, $squIdxB, $val) = @_;
  my($snapRowB, $snapColB) = ( 3*int($squIdxB/3), 3*($squIdxB%3) );
  my(@tmpRowB, @tmpColB, @coordsA, @coordsB);
  my($gotMatch) = 0;

  return(0) if ( ($snapRowA != $snapRowB) && ($snapColA != $snapColB) );

  @coordsA = getZeroSubCoords($snapRowA, $snapColA, $val, 2);
  @coordsB = getZeroSubCoords($snapRowB, $snapColB, $val, 2);

  if ( $snapRowA == $snapRowB ) {
    if ( ($coordsA[0] == $coordsB[0]) && ($coordsA[1] == $coordsB[1]) &&
         ($coordsA[2] == $coordsA[3]) && ($coordsB[2] == $coordsB[3]) ) {
      $gotMatch++;
    }
  }
  else {
    if ( ($coordsA[0] == $coordsA[1]) && ($coordsB[0] == $coordsB[1]) &&
         ($coordsA[2] == $coordsB[2]) && ($coordsA[3] == $coordsB[3]) ) {
      $gotMatch++;
    }
  }

  if ( $gotMatch ) {
    $gotMatch  = 0;
    $gotMatch += markRowExceptTwo($coordsA[0], $coordsA[2], $coordsB[3], $val);
    $gotMatch += markRowExceptTwo($coordsB[1], $coordsB[3], $coordsA[2], $val);
    $gotMatch += markColExceptTwo($coordsA[2], $coordsA[0], $coordsB[1], $val);
    $gotMatch += markColExceptTwo($coordsB[3], $coordsB[1], $coordsA[0], $val);
  }

  return($gotMatch);
}

#---------------------------- findDoublePairs() ------------------------------#
sub findDoublePairs {
  my($gotMatch) = 0;

  for my $val ( 1..9 ) {
    for my $squIdxA ( 0..7 ) {
      next if ( $squCnt[$squIdxA][$val] != 2 );

      my($snapRowA, $snapColA) = ( 3*int($squIdxA/3), 3*($squIdxA%3) );

      for my $squIdxB ( ($squIdxA+1)..8 ) {
        next if ( $squCnt[$squIdxB][$val] != 2 );

        $gotMatch += matchDoublePairs($snapRowA, $snapColA, $squIdxB, $val);
      }
    }
  }

  return($gotMatch);
}

#---------------------------- excludeRow() -----------------------------------#
sub excludeRow {
  my($squIdx, $val, $subRow) = @_;
  my($row) = 3*int($squIdx/3) + $subRow;
  my($snapCol) = 3*($squIdx%3);
  my($gotMatch) = 0;

  for my $col ( 0..8 ) {
    next if ( ($col >= $snapCol) && ($col < ($snapCol + 3)) );

    my($tmpSquIdx) = 3*int($row/3)+int($col/3);

    if ( ! $marks[$row][$col][$val] ) {
      $squCnt[$tmpSquIdx][$val]--;
      $gotMatch++;
    }

    $marks[$row][$col][$val] = 1;
  }

  return($gotMatch);
}

#---------------------------- excludeCol() -----------------------------------#
sub excludeCol {
  my($squIdx, $val, $subCol) = @_;
  my($col) = 3*($squIdx%3) + $subCol;
  my($snapRow) = 3*int($squIdx/3);
  my($gotMatch) = 0;

  for my $row ( 0..8 ) {
    next if ( ($row >= $snapRow) && ($row < ($snapRow + 3)) );

    my($tmpSquIdx) = 3*int($row/3)+int($col/3);

    if ( ! $marks[$row][$col][$val] ) {
      $squCnt[$tmpSquIdx][$val]--;
      $gotMatch++;
    }

    $marks[$row][$col][$val] = 1;
  }

  return($gotMatch);
}

#---------------------------- findStripeInSquare() ---------------------------#
sub findStripeInSquare {
  my($squIdx, $val) = @_;
  my($snapRow, $snapCol) = ( 3*int($squIdx/3), 3*($squIdx%3) );
  my($gotMatch) = 0;

  #--- SEARCH FOR COLUMNS ! --------------------------------------------------#
  for my $subCol ( 0..2 ) {
    my($cnt) = 0;

    for my $subRow ( 0..2 ) {
      $cnt++ if ( ! $marks[$snapRow+$subRow][$snapCol+$subCol][$val] );
    }

    if ( $cnt && ($cnt == $squCnt[$squIdx][$val]) ) {
      $gotMatch += excludeCol($squIdx, $val, $subCol);
    }
  }

  #--- SEARCH FOR ROWS ! -----------------------------------------------------#
  for my $subRow ( 0..2 ) {
    my($cnt) = 0;

    for my $subCol ( 0..2 ) {
      $cnt++ if ( ! $marks[$snapRow+$subRow][$snapCol+$subCol][$val] );
    }

    if ( $cnt && ($cnt == $squCnt[$squIdx][$val]) ) {
      $gotMatch += excludeRow($squIdx, $val, $subRow);
    }
  }

  return($gotMatch);
}

#---------------------------- findIsolatedStripes() --------------------------#
sub findIsolatedStripes {
  my($gotMatch) = 0;

  for my $val ( 1..9 ) {
    for my $squIdx ( 0..8 ) {
      my($cnt) = $squCnt[$squIdx][$val];

      next if ( ! $cnt || ($cnt > 3) );

      $gotMatch += findStripeInSquare($squIdx, $val);
    }
  }

  return($gotMatch);
}

#---------------------------- findLastRemaining() ----------------------------#
sub findLastRemaining {
  my($theVal, %vals);
  my($gotMatch) = 0;

  for my $row ( 0..8 ) {
    for my $col ( 0..8 ) {
      map { $vals{$_} = 1 } ( 1..9 );

      for my $val ( 1..9 ) {
        if ( $marks[$row][$col][$val] ) {
          delete($vals{$val}) if ( $marks[$row][$col][$val] );
        }
        else {
          $theVal = $val;
        }
      }

      if ( scalar(keys(%vals)) == 1 ) {
           setCell($row, $col, $theVal);
           $gotMatch++;
      }
    }
  }

  return($gotMatch);
}

#---------------------------- showBoard() ------------------------------------#
sub showBoard {
  my($title) = @_;

  printf("------------------------ BOARD $title -------------------------\n");
  printf("TIME: %s sec\n", $timer);
  $timer = 0;

  for my $row ( 0..8 ) {
    printf("------+-------+------\n") if ( $row && ! ($row % 3) );
    printf("%s %s %s | %s %s %s | %s %s %s\n", @{$board[$row]});
  }
}

###############################################################################
initBoard();
showBoard("initial");

my($gotMatch, $cnt);

do {
  $gotMatch = 0;

  #----- FIND SINGLES WITHIN ROWS, COLS, SUQARES ! ---------------------------#
  while ( $cnt = findSinglesInRow() + findSinglesInCol() + findSinglesInSqu() ) { $gotMatch += $cnt }

  #----- FIND CORRESPONDING DOUBLE PAIRES IN DIFFERENT SQUARES ! -------------#
  while ( $cnt = findDoublePairs() ) { $gotMatch += $cnt }

  #----- FIND ROWS OF 2 OR 3 WITHIN A SQUARE AS THE ONLY HOLES ! -------------#
  while ( $cnt = findIsolatedStripes() ) { $gotMatch += $cnt }

  #----- FIND LAST NUMBER REMAINING FOR A CERTAIN CELL ! ---------------------#
  while ( $cnt = findLastRemaining() ) { $gotMatch += $cnt }
} while ( $gotMatch );

showBoard("solved");