
<?php
    // Sudoku Solver.
    define('MAX_STEPS', 500000);

    // The numbers.
    $s = initNumbers();
    // And a copy to remember which fields are known.
    $c = $s;

    $i=$j = 0;
    $backtrack = false;

    if (!empty($s)) {
        for ($inf_protection = 0; $inf_protection < MAX_STEPS; $inf_protection++) {
            if ($i == 9) {
                print 'Solved after '. $inf_protection .' steps.';
                break;
            }

            if ($c[$i][$j] != 0) {
                if ($backtrack) {
                    list($i, $j) = prevIndices($i, $j);
                }
                else {
                    list($i, $j) = nextIndices($i, $j);
                }
                continue;
            }

            // Try numbers.
            for ($s[$i][$j]++; $s[$i][$j] <= 9; $s[$i][$j]++) {
                if (is_valid($s, $i, $j)) {
                    list($i, $j) = nextIndices($i, $j);
                    $backtrack = false;
                    continue 2;
                }
            }
            // Backtrack.
            $s[$i][$j] = 0;
            list($i, $j) = prevIndices($i, $j);
            $backtrack = true;
        }
        if ($inf_protection == MAX_STEPS) {
            print 'Not solved. Stopped after '. MAX_STEPS .' steps.';
        }
    }

    function is_valid(&$s, $i, $j) {
        // Check row.
        $row = array();
        for ($v = 0; $v < 9; $v++) {
            if ($s[$i][$v] != 0 && $j != $v) {
                $row[] = $s[$i][$v];
            }
        }
        if (!empty($row) && in_array($s[$i][$j], $row)) {
            return false;
        }

        // Check column.
        $col = array();
        for ($u = 0; $u < 9; $u++) {
            if ($s[$u][$j] != 0 && $i != $u) {
                $col[] = $s[$u][$j];
            }
        }
        if (!empty($col) && in_array($s[$i][$j], $col)) {
            return false;
        }

        // Check block;
        $block = array();

        for ($u = (integer)($i / 3) * 3; $u < ((integer)($i / 3) + 1) * 3; $u++) {
            for ($v = (integer)($j / 3) * 3; $v < ((integer)($j / 3) + 1) * 3; $v++) {
                if ($s[$u][$v] != 0 && !($u == $i && $v == $j)) {
                    $block[] = $s[$u][$v];
                }
            }
        }
        if (!empty($block) && in_array($s[$i][$j], $block)) {
            return false;
        }

        return true;
    }

    function nextIndices($i, $j) {
        $j = $j + 1;

        if ($j % 9 == 0) {
            $i = $i + 1;
            $j = 0;
        }

        return array($i, $j);
    }

    function prevIndices($i, $j) {
        $j = $j - 1;

        if ($j == -1) {
            $i = $i - 1;
            $j = 8;
        }

        return array($i, $j);
    }

    function initNumbers() {
        $s = array();
        $g = array();
        if (!isset($_GET['sudoku'])) return $s;

        $i=$j = 0;

        $numbers = (string)$_GET['sudoku'];
        for ($str_index = 0; $str_index < strlen($numbers); $str_index++) {
            $char = $numbers{$str_index};
            if (is_numeric($char)) {
                $s[$i][$j] = (integer)$char;
                list($i, $j) = nextIndices($i, $j);
            }
            else if ($char == '-') {
                $s[$i][$j] = 0;
                list($i, $j) = nextIndices($i, $j);
            }
        }

        return $s;
    }

?><html>
    <head>
        <title>Sudoku Solver with simple Backtracking Algorithm</title>
    </head>
    <body>
        <form>
            <textarea name="sudoku" rows="15" cols="30"><?php
    if (empty($s)) {
        print <<<END
---            ---            ---
---            ---            ---
---            ---            ---

---            ---            ---
---            ---            ---
---            ---            ---

---            ---            ---
---            ---            ---
---            ---            ---
END;
    }
    else {
        for ($i = 0; $i < 9; $i++) {
            for ($j = 0; $j < 9; $j++) {
                print ($s[$i][$j] > -1) ? $s[$i][$j] : '-';
                if ($j == 2 || $j == 5) {
                    print "            ";
                }
            }
            print "\n";
            if (($i+1) % 3 == 0) print "\n";
        }
    }
?></textarea>
            <input type="submit" value="solve">
        </form>
        <br>
        <a href="source.php">View the source code of this file.</a>
    </body>
</html>