<?php

function get_column_numbers($sudoku, $col) {
    $numbers = array();

    for ($i = 0; $i < 9; $i++) {
        if ($sudoku[$i][$col] != 0) {
            array_push($numbers, $sudoku[$i][$col]);
        }
    }

    return $numbers;
}

function get_row_numbers($sudoku, $row) {
    $numbers = array();

    for ($i = 0; $i < 9; $i++) {
        if ($sudoku[$row][$i] != 0) {
            array_push($numbers, $sudoku[$row][$i]);
        }
    }

    return $numbers;
}

function get_square_numbers($sudoku, $x, $y) {
    $numbers = array();

    for ($i = $x; $i < $x + 3; $i++) {
        for ($j = $y; $j < $y + 3; $j++) {
            if ($sudoku[$i][$j] != 0) {
                array_push($numbers, $sudoku[$i][$j]);
            }
        }
    }

    return $numbers;
}

function get_cell_square($x, $y) {
    $square_x = 0;
    $square_y = 0;

    if ($x >= 3) $square_x = 3;
    if ($y >= 3) $square_y = 3;

    if ($x >= 6) $square_x = 6;
    if ($y >= 6) $square_y = 6;

    return array('x' => $square_x, 'y' => $square_y);
}

function my_array_intersect($array1, $array2) {
    $intersection = $array1;

    foreach ($array2 as $value) {
        if (!in_array($value, $intersection)) {
            array_push($intersection, $value);
        }
    }

    return $intersection;
}

function missing_number($numbers) {
    for ($i = 1; $i <= 9; $i++) {
        if (!in_array($i, $numbers)) {
            return $i;
        }
    }
}

function compute_number($sudoku, $x, $y) {
    if ($sudoku[$x][$y] != 0) return $sudoku[$x][$y];

    $square = get_cell_square($x, $y);

    $neighbours = my_array_intersect(get_column_numbers($sudoku, $x), my_array_intersect(get_row_numbers($sudoku, $y), get_square_numbers($sudoku, $square['x'], $square['y'])));
    
    if (count($neighbours) == 8) {
        return missing_number($neighbours);
    } else {
        return 0;
    }
}

function solve($sudoku) {
    while (true) {
        $last_sudoku = $sudoku;
        
        for ($x = 0; $x < 9; $x++) {
            for ($y = 0; $y < 9; $y++) {
                $sudoku[$x][$y] = compute_number($sudoku, $x, $y);
            }
        }
        
        if ($last_sudoku == $sudoku) {
            return $sudoku;
        }
    }
}

function main($argc, $argv) {
    if ($argc != 2) {
        echo "Usage: $argv[0] <inputfile>\n";
    } else {
        $infile = fopen($argv[1], 'r');
        
        for ($i = 0; $i < 9; $i++) {
            $line = fgets($infile);
            
            for ($j = 0; $j < 9; $j++) {
                if (intval($line[$j]) >= 1 && intval($line[$j]) <= 9) {
                    $sudoku[$j][$i] = intval($line[$j]);
                } else {
                    $sudoku[$j][$i] = 0;
                }
            }
        }
        
        fclose($infile);
        
        $sudoku = solve($sudoku);
        
        for ($y = 0; $y < 9; $y++) {
            for ($x = 0; $x < 9; $x++) {
                echo $sudoku[$x][$y];
            }
            echo "\n";
        }
    }
}

main($argc, $argv);

?>