<?php
/************************************
SUDOKU PUZZLE SOLVER
BY PARKER PHINNEY
http://madebyparker.com/contact.php

to do
    ability to show ALL solutions
        snippets of code already started
    ability to adjust difficulty of generated puzzle
        snippets of code already started
        line 316
    AJAX-ification
    design tweaks
        buttons on one row
    trivial
        remove set_value function
        replace nests of for with foreach- ln207
************************************/


//show them the source if they want to see it
if($_GET['action'] == 'source'){
$source = file_get_contents(__FILE__);
echo highlight_string($source);
exit();
}

$puzzle = array();

/*COORDINATES ARE IN THE FORM (COL NUMBER [FROM LEFT])(ROW NUMBER [FROM BOTTOM])
    they follow the normal cartesian coordinate system
ex:
 13 23 33
12 22 32
11 21 31

the puzzle is stored as a muti-dimensional array.
the dimensions are
    coordinates
    possibilities
    bool
ex
    $puzzle[34][6] = TRUE
    the cell at (3,4) has 6 as a possibility
*/

//DEFINE A COUPLE FUNCTIONS FIRST

//function to set the value of a cell
//that is to say, eliminate all other possibilities
function set_value($coordinates, $value){
    $coordinates = array(
        $value => TRUE
    );
    return $coordinates;
}

//function to see whether or not a specific cell is solved
function cell_solved($coordinates){
     $possibilites = 0;
        foreach($coordinates as $number => $possible){
                $possibilites+= 1;
                $solution = $number;
         }
     if($possibilites == 1){
        return $solution;
     }
     else{
        return FALSE;
     }
}
//function to see if the whole puzzle is solved
function puzzle_solved($puzzle){
    foreach($puzzle as $coordinates){
        if(!cell_solved($coordinates)){
            return FALSE;
        }
    }
return TRUE;
}

//function to see if a puzzle is impossible
function impossible($puzzle){
    if(!$puzzle){
        return TRUE;
    }
    foreach($puzzle as $coordinates => $values){
        if(!$values){
            return TRUE;
        }
    }
return FALSE;
}

//function to eliminate impossibilities based on a known solution
function eliminations($solvedx, $solvedy, $solution, $puzzle){
    //so we know that all boxes in that row
    for($eliminationy = 1; $eliminationy <= 9 ; $eliminationy++){
        //except for that particular box
        if($eliminationy != $solvedy){
            //cant have that solution
            unset($puzzle[$solvedx . $eliminationy][$solution]);
        }
    }
    //we also know that all boxes in that column
    for($eliminationx = 1; $eliminationx <= 9 ; $eliminationx++){
        //except for that particular box
        if($eliminationx != $solvedx){
            //cant have that solution
            unset($puzzle[$eliminationx . $solvedy][$solution]);
        }
    }
    //ELIMINATING POSSIBILITIES BY 3X3 BOX POSITION
    //set the x and y's that fellow box-members will be in (that arent already in the same row/column)
    //if its in the RIGHT COLUMN of a 3x3 box
    if($solvedx % 3 == 0){
        $unsetx1 = -1;
        $unsetx2 = -2;
    }
    //if it is in the CENTER COLUMN of a 3x3 box
    else if($solvedx % 3 == 2){
        $unsetx1 = -1;
        $unsetx2 = +1;
    }
    //if it is in the LEFT COLUMN of a 3x3 box
    else if($solvedx % 3 == 1){
        $unsetx1 = +1;
        $unsetx2 = +2;
    }
    //if its in the TOP ROW of a 3x3 box
    if($solvedy % 3 == 0){
        $unsety1 = -1;
        $unsety2 = -2;
    }
    //if its in the CENTER ROW of a 3x3 box
    else if($solvedy % 3 == 2){
        $unsety1 = +1;
        $unsety2 = -1;
    }
    //if its in the BOTTOM ROW of a 3x3 box
    else if($solvedy % 3 == 1){
        $unsety1 = +1;
        $unsety2 = +2;
    }
    //remove the possibility of those x's and y's
    unset($puzzle[$solvedx + $unsetx1 . $solvedy + $unsety1][$solution]);
    unset($puzzle[$solvedx + $unsetx1 . $solvedy + $unsety2][$solution]);
    unset($puzzle[$solvedx + $unsetx2 . $solvedy + $unsety1][$solution]);
    unset($puzzle[$solvedx + $unsetx2 . $solvedy + $unsety2][$solution]);
    return $puzzle;
}



//function to make one pass of eliminating impossibilities
function eliminationsloop($puzzle){
    //as long as we're still making progress
    while($puzzle != $puzzlelast){
        //keep a copy of the last pass, to make sure we're making progress
        $puzzlelast = $puzzle;
        //for each x
        for ($solvedx = 1; $solvedx <= 9; $solvedx++) {
            //and each y
                 for ($solvedy = 1; $solvedy <= 9; $solvedy++) {
                    //see if we know the solution at those coordinates.  if we do, we can eliminate some possibilities elsewhere
                     if($solution = cell_solved($puzzle[$solvedx . $solvedy])){
                    $puzzle = eliminations($solvedx, $solvedy, $solution, $puzzle);
                }
            }
        }
    }
    return $puzzle;
}

function solve($puzzle, $r = null){
    //run the puzzle through an eliminations loop
    $puzzle = eliminationsloop($puzzle);
    //if that's enough to solve the puzzle
    if (puzzle_solved($puzzle)){
        //we're done, that's it
        return $puzzle;
    }
    //if we're going to have to make some guesses...
    else if (!impossible($puzzle)){
        //CHOOSE THE CELL WITH THE FEWEST POSSIBILITIES (that isn't solved yet)
        //set a base number of possibilities for a potential cell to guess for
        $possibilities = 9;
        //for each x
        //THE FOLLOWING TWO FOR NESTS SHOULD BE CONVERTED INTO FOREACH'S
        for ($unsolvedx = 1; $unsolvedx <= 9; $unsolvedx++) {
            //and each y
                 for ($unsolvedy = 1; $unsolvedy <= 9; $unsolvedy++) {
                //if it isn't solved yet
                if(!cell_solved($puzzle[$unsolvedx . $unsolvedy])){
                    //see how many possibilities are left for this cell
                    $possibilitiesnew = count($puzzle[$unsolvedx . $unsolvedy]);
                    //if it's fewer than any other cell
                    if($possibilitiesnew <= $possibilities){
                        //that'll be the lowest number of possibilities
                        $possibilities = $possibilitiesnew;
                    }
                }
            }
        }
        //stick all candidates for guess coordinates in an array
        $i = 0;
        for ($unsolvedx = 1; $unsolvedx <= 9; $unsolvedx++) {
            //and each y
                 for ($unsolvedy = 1; $unsolvedy <= 9; $unsolvedy++) {
                //if it isn't solved yet
                if(!cell_solved($puzzle[$unsolvedx . $unsolvedy])){
                    //if it has the minimum number of possibilities left
                    if(count($puzzle[$unsolvedx . $unsolvedy]) == $possibilities){
                        //add it to an array with all candidates for guess coordinates
                        $possiblecoords[$i] = $unsolvedx . $unsolvedy;
                        $i++;
                    }
                }
            }
        }
        //grab a random guess candidate
        $guesscell = $possiblecoords[array_rand($possiblecoords)];
        //let's try each of these guesses until one works
        //(the "return" will keep us from looping unnecessarily)
        foreach($puzzle[$guesscell] as $guess => $irrelevant){
            //duplicate the puzzle
            $puzzledupe = $puzzle;
            //set the duplicate to have that possibility as the solution
            $puzzledupe[$guesscell] = set_value($puzzledupe[$guesscell], $guess);
            //solve with that guess
            $puzzledupe = solve($puzzledupe);
            if(!impossible($puzzledupe)){
                return $puzzledupe;
            }
        }
    }
    //if the puzzle is impossible
    else{
        return FALSE;
    }
}

//DONE DEFINING FUNCTIONS---------------

//if they wanted to make a puzzle---------------------------------------------
if($_POST['action'] == 'generate'){
    //make an array full of possibilities
    for ($y = 9; $y >= 1; $y--) {
        for ($x = 1; $x <= 9; $x++) {
                for ($i = 1; $i <= 9; $i++) {
                        $puzzle[$x . $y][$i] = TRUE;
                    }
        }
    }
    //generate a random full board
    $puzzle = solve($puzzle);
    //DIFFICULTY LEVEL!!!!
    //right now this doesn't do anything
    $diflevel = 40;
    //it'll actually go for one more than the difficult level... w/e
    $i = 0;
    //duplicate the puzzle
    $puzzledupe = $puzzle;
    //as long as we haven't made a puzzle the requires guesses
    while(puzzle_solved(eliminationsloop($puzzledupe)) && $i<= $diflevel){
        //apply the changes of the last iteration
        $puzzle = $puzzledupe;
        //generate a couple of random coords
        $randx = rand(1, 9);
        $randy = rand(1, 9);
        //if that cell hasn't been blanked yet
        if(cell_solved($puzzle[$randx . $randy])){
            //duplicate the puzzle
            $puzzledupe = $puzzle;
            //unset the cell solution
            $puzzledupe[$randx . $randy] = array(
                1 => TRUE,
                2 => TRUE,
                3 => TRUE,
                4 => TRUE,
                5 => TRUE,
                6 => TRUE,
                7 => TRUE,
                8 => TRUE,
                9 => TRUE
            );
            $i++;
        }
    }
}
//if they wanted to solve a puzzle----------------------------------------------------
else if($_POST['action'] == "solve"){
    //get the known
    foreach($_POST as $coordinates => $value){
        //make sure that the post item is coordinates (and not something else)
        if(substr($coordinates, 0, 5) == "coord"  && $value){
                //strip the string "coord" from the beginning of the coordinates
                $coordinates = str_replace("coord", "", $coordinates);
            //make sure that its only two integers
            $coordinates = substr($coordinates, 0, 2);
            //stick it's value in the array
            $puzzle[$coordinates][$value] = TRUE;
            //get an extra copy of the given puzzle
            $puzzle_given = $puzzle;
        }
    }
    //fill in the rest of the puzzle with all possibilites
    for ($y = 9; $y >= 1; $y--) {
        for ($x = 1; $x <= 9; $x++) {
            if(!array_key_exists($x . $y, $puzzle)){
                    for ($i = 1; $i <= 9; $i++) {
                            $puzzle[$x . $y][$i] = TRUE;
                        }
            }
        }
    }
    //solve the frikkin puzzle!
    $puzzlesolutions = solve($puzzle);

}
?>
<!DOCTYPE html PUBLIC '-//W3C//DTD XHTML 1.0 Strict//EN' 'http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd'>
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
    <head>
        <title>MadeByParker.com</title>
        <meta http-equiv="Content-Language" content="EN-US" />
        <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1" />
        <style type="text/css">
            html{
                width: 100%;
                height: 100%;
            }
            body{
                width: 600px;
                margin: auto;
                margin-top: 10px;
                position: relative;
                font-family: arial;
                background-color: #ffffff;
                background-image: url(gradient.gif);
                background-repeat: repeat-x;
                background-position: top left;
                letter-spacing: .05em;
                line-height: 1.4em;
                margin-bottom: 10em;
            }
            p{
                margin-left: 3em;
            }
            p.bottompar{
                clear: both;
                padding-bottom: 2em;
                position: relative;
                bottom: 70px;
            }
            a{
                text-decoration: none;
                color: #0000ff;
            }
            a:hover{
                border-top: solid 1px #333333;
                border-bottom: solid 1px #333333;
            }
            h1{
                font-weight: normal;
                font-size: 1.3em;
            }
            .puzzle_form, .generateform, .clearform{
                font-family: arial;
                padding: 0px;
                margin: 0px;
                letter-spacing: 0px;
                line-height: 0px;
            }
            .puzzle_form fieldset, .generateform fieldset, .clearform fieldset{
                border: none;
                padding: 0px;
                margin: 0px;
                margin-left: 3em;
            }
            .puzzle_form fieldset{
            }
            .puzzle_form fieldset table {
                border: 0px;
                padding: 0px;
                margin: 0px;
                background-color: black;
                z-index:2;
                border: 0px;
            }
            .puzzle_form fieldset table tr{
                padding: 0px;
                margin: 0px;
            }
            .puzzle_form fieldset table tr td{
                padding: 0px;
                margin: 0px;
                border: none;
            }
            .puzzle_form fieldset table tr td input{
                border: none;
                text-align: center;
                vertical-align: middle;
                padding: 0px;
                margin: 0px;
                width: 1.5em;
                height: 1.5em;
                font-size: 1.7em;
            }
            input.given{
                font-weight: normal;
                background-color: #F2F2F2;
            }
            input.solved{
                font-style: italic;
            }
            
            .puzzle_form fieldset input.button{
                position: relative;
                left: 400px;
                bottom: 260px;
                z-index: 1;
            }
            .generateform fieldset input.button{
                position: relative;
                left: 400px;
                bottom: 250px;
                z-index: 1;
            }
            .clearform fieldset input.button{
                position: relative;
                left: 400px;
                bottom: 240px;
                z-index: 1;
            }
            

            .puzzle_form fieldset input.button, .generateform fieldset input.button, .clearform fieldset input.button{
                /*background-image: url(gradient.gif);*/
                background-color: #ffffff;
                padding: .1em;
                margin-left: 0px;
                font-family: arial;
                font-size: 1.2em;
                border-top: black 1px dotted;
                border-bottom: black 1px dotted;
                border-left: black 1px dotted;
                border-right: black 1px dotted;
                width: 100px;
            }
            .puzzle_form fieldset input.button:hover, .generateform fieldset input.button:hover, .clearform fieldset input.button:hover{
                border-top: black 1px solid;
                border-bottom: black 1px solid;
                border-left: black 1px solid;
                border-right: black 1px solid;
            }
            .puzzle_form fieldset table tr td.box_top{
                border-bottom: black 0px solid;
                border-top: black 1px solid;
            }
            .puzzle_form fieldset table tr td.box_bottom{
                border-bottom: black 1px solid;
                border-top: black 0px solid;
            }
            .puzzle_form fieldset table tr td.box_right{
                border-right: black 1px solid;
                border-left: black 0px solid;
            }
            .puzzle_form fieldset table tr td.box_left{
                border-right: black 0px solid;
                border-left: black 1px solid;
            }
            .generateform{
                display: inline;
            }
            .generateform fieldset{
                border: 0px;
            }
            
        </style>
    </head>
    <body>
        <h1>
            Sudoku Puzzle Generator and Solver
        </h1>
<?php

//if something went wrong in the solving process
if($_POST['action'] == "solve" && !$puzzlesolutions){
    //let them know
    echo "<p>I wasn't able to solve your puzzle.  You may have entered an impossible puzzle.</p>";
    //and give them a fresh puzzle
    unset($_POST['action']);
}
?>

<form method="post" action="<?php echo $_SERVER['PHP_SELF'] ?>" class="puzzle_form">
    <fieldset>
        <table>
        
        
<?php
//function to get the position within of a cell within a 3x3 box
function boxclass($x, $y){
    //ELIMINATING POSSIBILITIES BY 3X3 BOX POSITION
    //set the x and y's that fellow box-members will be in (that arent already in the same row/column)
    //if its in the TOP ROW of a 3x3 box
    if($y % 3 == 0){
        $class .=  'box_top ';
    }
    //if its in the BOTTOM ROW of a 3x3 box
    else if($y % 3 == 1){
        $class .= 'box_bottom ';
    }
    //if its in the RIGHT COLUMN of a 3x3 box
    if($x % 3 == 0){
        $class .= 'box_right';
    }
    //if it is in the LEFT COLUMN of a 3x3 box
    else if($x % 3 == 1){
        $class .= 'box_left';
    }
    return ' class="' . $class . '"';
}
?>
<?php
if($_POST['action'] == "generate"){
    for ($y = 9; $y >= 1; $y--) {
        echo "\n\t" . '<tr>';
        for ($x = 1; $x <= 9; $x++){
            if($solution = cell_solved($puzzle[$x . $y])){
                $content = '<input type="text" class="given" name="coord' . $x . $y .  '" value="' . $solution . '" maxlength="1"/>';
            }
            else{
                $content = '<input type="text" name="coord' . $x . $y .  '" value="" maxlength="1"/>';
            }
                echo "\n\t\t" . '<td' . boxclass($x,$y) . '>';
                echo "\n\t\t\t" . $content;
                echo "\n\t\t" . '</td>';
        }
        echo "\n\t" . '</tr>';
    }
}
//if they had wanted to solve a puzzle
else if($_POST['action'] == "solve"){
    //if there was only one solution
    //if(count($puzzlesolutions) == 1){
        //let's take a dimension off that array to simplify things
        //FOR MUTLIPLE SOLUTIONS
        //$puzzle = $puzzlesolutions[0];
        //new variable name (inefficiency ftw)
        $puzzle = $puzzlesolutions;
        for ($y = 9; $y >= 1; $y--) {
            echo "\n\t" . '<tr>';
            for ($x = 1; $x <= 9; $x++) {
                if($puzzle_given[$x . $y]){
                    $content = '<input type="text" class="given" name="coord' . $x . $y .  '" value="' . cell_solved($puzzle[$x . $y]) . '" maxlength="1"/>';
                }
                else{
                    $content = '<input type="text" class="solved" name="coord' . $x . $y .  '" value="' . cell_solved($puzzle[$x . $y]) . '" maxlength="1"/>';
                }
                echo "\n\t\t" . '<td' . boxclass($x,$y) . '>';
                echo "\n\t\t\t" . $content;
                echo "\n\t\t" . '</td>';
            }
            echo "\n\t" . '</tr>';
        }
    //}
    //if there was more than one solution
    /*else{
        //JUST FOR NOW, JUST PRINT ONE SOLUTION
        $puzzle = $puzzlesolutions[0];
        for ($y = 9; $y >= 1; $y--) {
            echo "\n\t" . '<tr>';
            for ($x = 1; $x <= 9; $x++) {
                if($puzzle_given[$x . $y]){
                    $content = '<input type="text" class="given" name="coord' . $x . $y .  '" value="' . cell_solved($puzzle[$x . $y]) . '" maxlength="1"/>';
                }
                else{
                    $content = '<input type="text" class="solved" name="coord' . $x . $y .  '" value="' . cell_solved($puzzle[$x . $y]) . '" maxlength="1"/>';
                }
                echo "\n\t\t" . '<td' . boxclass($x,$y) . '>';
                echo "\n\t\t\t" . $content;
                echo "\n\t\t" . '</td>';
            }
            echo "\n\t" . '</tr>';
        }
        //AND LET THEM KNOW THAT THERE ARE MORE SOLUTIONS
        $multiple = TRUE;
    }*/
}
//if they wanted a blank puzzle
else{
    for ($y = 9; $y >= 1; $y--) {
        echo "\n\t" . '<tr>';
        for ($x = 1; $x <= 9; $x++) {
            echo "\n\t\t" . '<td' . boxclass($x,$y) . '>';
            echo "\n\t\t\t" . '<input type="text" name="coord' . $x . $y .  '" value="' . $_POST['coord' . $x . $y] . '" maxlength="1"/>';
            echo "\n\t\t" . '</td>';
        }
        echo "\n\t" . '</tr>';
    }
}
?>
        </table>
        <input type="hidden" name="action" value="solve" />
        <input type="submit" value="Solve" class="button" />
    </fieldset>
</form>

<form method="post" action="<?php echo $_SERVER['PHP_SELF'] ?>" class="generateform">
    <fieldset>
        <input type="hidden" name="action" value="generate" />
        <input type="submit" value="Generate" class="button" />
    </fieldset>
</form>
<form method="post" action="<?php echo $_SERVER['PHP_SELF'] ?>" class="clearform">
    <fieldset>
        <input type="hidden" name="action" value="clear" />
        <input type="submit" value="Clear" class="button" />
    </fieldset>
</form>


<p class="bottompar">
I'm still hammering out a few bugs that appear in some <a href="http://en.wikipedia.org/wiki/Web_standards">noncompliant</a> browsers.  In the meantime, <a href="http://getfirefox.com">get firefox</a>.  This project is <a href="<?php echo $_SERVER['PHP_SELF']?>?action=source">open source</a>.
</p>

    </body>
</html>
<?php
//function to print a puzzle (for debugging)
function printpuz($puzzle){
    $string = '<table>';
    for ($y = 9; $y >= 1; $y--) {
        $string.= "\n\t" . '<tr>';
        for ($x = 1; $x <= 9; $x++) {
            $content = cell_solved($puzzle[$x . $y]);
            $string.= "\n\t\t" . '<td>';
        $string.= "\n\t\t\t" . $content;
        $string.= "\n\t\t" . '</td>';
        }
        $string.= "\n\t" . '</tr>';
    }
    $string.= "\n</table>";
    echo $string;
}
?>
1