Scripting Corner

PHP:
Sudoku Class


<?php

/* ---------------------------------------------------------

                       LX' Sudoku Class

                 (c) 2006 Alexander Schulze

   ---------------------------------------------------------
   This  program  is free  software;  you  can  redistribute
   it  and/or  modify it  under the terms of the GNU General
   Public  License   as  published   by  the  Free  Software
   Foundation;  either  version 2  of  the License,  or  (at
   your option) any later version.

   This program  is  distributed  in the  hope that  it will
   be useful,  but WITHOUT  ANY  WARRANTY;  without even the
   implied  warranty  of  MERCHANTABILITY  or FITNESS  FOR A
   PARTICULAR  PURPOSE.  See the GNU  General Public License
   for more details.

   You should have received a copy of the GNU General Public
   License along  with this  program;  if not,  write to the
   Free Software Foundation, Inc., 51 Franklin Street, Fifth
   Floor, Boston, MA  02110-1301, USA.
   ---------------------------------------------------------

      Authors:   Alexander Schulze
      Contact:   http://www.lxhome.de/

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

      Changelog:

      v1.0    2006-04-17: first version publically available

   --------------------------------------------------------- */

class Sudoku
{
    var $zeichensatz;   // used characters in sudoku (1-9)
    var $groesse;       // size of board (9)
    var $kl_groesse;    // size of a small square (3)
    var $matrix;        // sudoku data structure
    var $changed;       // if a solver iteration changed anything
    var $col_cache, $row_cache, $box_cache;

    // constructor
    function Sudoku ( &$sudokustring, &$zeichenstring )
    {
        // define charset and therefore size of the board
        $this -> zeichensatz = explode ( ' ', $zeichenstring );
        $this -> groesse     = count ( $this -> zeichensatz );
        $this -> kl_groesse  = floor ( sqrt ( $this -> groesse ) );

        // initialize caches
        $this -> col_cache = array();
        $this -> row_cache = array();
        $this -> box_cache = array();

        // create and fill data structure
        $this -> createMatrix ( $sudokustring );
        $this -> firstFill();
    }

    // convert string into sudoku matrix
    function createMatrix ( &$string )
    {
        // linebreaks
        $nl = array ( "\r\n", "\n\r", "\n", "\r" );

        // split string into its elements
        if ( !strpos ( $string, ' ' ) )
            $temp = preg_split ( '//', str_replace ( $nl, '', $string ), -1, PREG_SPLIT_NO_EMPTY );
        else
            $temp = explode ( ' ', str_replace ( $nl, ' ', $string ) );


        for ( $zeile = 0; $zeile < $this -> groesse; $zeile++ )
        {
            $row = $zeile  % $this -> kl_groesse;

            // split into small squares
            for ( $spalte = 0; $spalte < $this -> groesse; $spalte++ )
            {
                $kasten = floor ( $zeile / $this -> kl_groesse ) * $this -> kl_groesse +
                          floor ( $spalte / $this -> kl_groesse );

                $col = $spalte % $this -> kl_groesse;

                $this -> matrix [ $kasten ]
                                [ $row    ]
                                [ $col    ] = $temp [ ( $zeile * $this -> groesse + $spalte ) ] ;
            }
        }
    }

    // fill empty fields with possibilities
    function firstFill()
    {
        for ( $i = 0; $i < $this -> groesse; $i++ )
        {
            $box = $this -> getBox ( $i );

            // every non-used symbol is added as possibility
            foreach ( $this -> zeichensatz as $zeichen )
            {
                if ( !in_array ( $zeichen, $box ) )
                {
                    for ( $j = 0; $j < $this -> groesse; $j++ )
                    {
                        if ( $box [ $j ] == 0 )
                            $box [ $j ] = array ( $zeichen );
                        elseif (is_array ( $box [ $j ] ) )
                            $box [ $j ][] = $zeichen;
                    }
                }
            }
        }
    }

    // output sudoku as HTML table
    function showSudoku_Matrix ( $kommentar = '' )
    {
        $ret = '<table cellspacing="0" cellpadding="0" title="' . $kommentar . '">';

        // small squares
        foreach ( $this -> matrix as $key => $kasten )
        {
            if ( $key % $this -> kl_groesse == 0 ) $ret .= '<tr>';
            $ret .= "<td>\n\n<table>\n";

            // columns inside a square
            foreach ( $kasten as $spalte )
            {
                $ret .= '<tr>';

                // cells in each column
                foreach ( $spalte as $werte )
                {
                    if ( is_array ( $werte ) )
                    {
                        if ( count ( $werte ) == 1 )
                        {
                            foreach ( $werte as $val ) $ret .= '<td class="solved">' . htmlspecialchars ( $val );
                        }
                        elseif ( count ( $werte ) == 0 )
                        {
                            $ret .= '<td class="error">';
                        }
                        else
                        {
                            sort ( $werte );
                            $ret .= '<td class="possibilities" title="'.implode ( ' ', $werte ).'">'.htmlspecialchars ( implode ( ' ', $werte ) );
                        }
                    }
                    else
                    {
                        $ret .= '<td class="start">';
                        $ret .= ( $werte ) ? htmlspecialchars ( $werte ) : '&nbsp;';
                    }
                    $ret .= '</td>';
                }

                $ret .= "</tr>\n";
            }

            $ret .= "</table>\n\n</td>";
            if ( $key % $this -> kl_groesse == $this -> kl_groesse - 1 ) $ret .= '</tr>';
        }

        $ret .= '</table>';

        return $ret;
    }

    // the solver
    function solve ( $step )
    {
        $this -> changed = true;

        // true if not the first iteration
        // used to speed up search because after the first iteration you don't
        // have to check against fields that were already known at the beginning
        $notfirst = false;

        while ( !$this -> checkWin() && $this -> changed )
        {
            $this -> changed = false;

            if ( $step [ 0 ] )
            {
                for ( $i = 0; $i < $this -> groesse; $i++ )
                {
                    // filter values that are already known from the combinations of possibilities
                    $this -> kill ( $this -> getRow ( $i ), $notfirst );
                    $this -> kill ( $this -> getCol ( $i ), $notfirst );
                    $this -> kill ( $this -> getBox ( $i ), $notfirst );
                }
                $notfirst = true;
                if ( $this -> changed ) continue;
            }

            if ( $step [ 1 ] )
            {
                for ( $i = 0; $i < $this -> groesse; $i++ )
                {
                    // sets fields that are the only one in one set to allow a certain value
                    $this -> setUnique ( $this -> getRow ( $i ) );
                    if ( $this -> changed ) continue 2;

                    $this -> setUnique ( $this -> getCol ( $i ) );
                    if ( $this -> changed ) continue 2;

                    $this -> setUnique ( $this -> getBox ( $i ) );
                    if ( $this -> changed ) continue 2;
                }
            }

            if ( $step [ 2 ] )
            {
                for ( $i = 0; $i < $this -> groesse; $i++ )
                {
                    // checks for identical combinations of possibilities which would exclude
                    // the elements of those combinations in all the other ones
                    $this -> checkIdentical ( $this -> getRow ( $i ) );
                    if ( $this -> changed ) continue 2;

                    $this -> checkIdentical ( $this -> getCol ( $i ) );
                    if ( $this -> changed ) continue 2;

                    $this -> checkIdentical ( $this -> getBox ( $i ) );
                    if ( $this -> changed ) continue 2;
                }
            }

            if ( $step [ 3 ] )
            {
                for ( $i = 0; $i < $this -> groesse; $i++ )
                {
                    // checks for subsets of combinations that are identical and would exclude those elements
                    // that are not part of that subset
                    $this -> checkCombination ( $this -> getRow ( $i ) );
                    if ( $this -> changed ) continue 2;

                    $this -> checkCombination ( $this -> getCol ( $i ) );
                    if ( $this -> changed ) continue 2;

                    $this -> checkCombination ( $this -> getBox ( $i ) );
                    if ( $this -> changed ) continue 2;
                }
            }

            if ( $step [ 4 ] )
            {
                for ( $i = 0; $i < $this -> groesse; $i++ )
                {
                    if ( $this -> guess ( $i, $step ) === true ) continue 2;
                }
            }
        }

        return $this -> checkWin();
    }

    //////
    // helper functions to get access to the parts of the sudoku more easily
    //////

    // returns a reference to a row of the sudoku
    function &getRow ( $zeile )
    {
        if ( !isset ( $this -> row_cache [ $zeile ] ) )
        {
            $row = $zeile % $this -> kl_groesse;

            for ( $spalte = 0; $spalte < $this -> groesse; $spalte++ )
            {
                $kasten = floor ( $zeile  / $this -> kl_groesse ) * $this -> kl_groesse +
                          floor ( $spalte / $this -> kl_groesse );

                $col = $spalte % $this -> kl_groesse;

                $temp[] =& $this -> matrix [ $kasten ]
                                           [ $row    ]
                                           [ $col    ];
            }

            $this -> row_cache [ $zeile ] =& $temp;
        }

        return $this -> row_cache [ $zeile ];
    }

    // returns a reference to a column of the sudoku
    function &getCol ( $spalte )
    {
        if ( !isset ( $this -> col_cache [ $spalte ] ) )
        {
            $col = $spalte % $this -> kl_groesse;

            for ( $zeile = 0; $zeile < $this -> groesse; $zeile++ )
            {
                $kasten = floor ( $zeile  / $this -> kl_groesse ) * $this -> kl_groesse +
                          floor ( $spalte / $this -> kl_groesse );

                $row = $zeile % $this -> kl_groesse;

                $temp[] =& $this -> matrix [ $kasten ]
                                           [ $row    ]
                                           [ $col    ];
            }
            $this -> col_cache [ $spalte ] =& $temp;
        }

        return $this -> col_cache [ $spalte ];
    }

    // returns a reference to a small square of the sudoku
    function &getBox ( $box )
    {
        if ( !isset ( $this -> box_cache [ $box ] ) )
        {
            foreach ( $this -> matrix [ $box ] as $x => $row )
                foreach ( $row as $y => $col )
                    $temp[] =& $this -> matrix [ $box ][ $x ][ $y ];

            $this -> box_cache [ $box ] =& $temp;
        }

        return $this -> box_cache [ $box ];
    }

    // checks if the sudoku is already solved
    // TODO: not only check if every field is filled but also if the fillings are correct :)
    function checkWin()
    {
        for ( $i = 0; $i < $this -> groesse; $i++ )
        {
            $box = $this -> getBox ( $i );
            for ( $j = 0; $j < $this -> groesse; $j++ )
            {
                if ( ( is_array ( $box [ $j ] ) && count ( $box [ $j ] ) > 1  ) ||
                     ( is_array ( $box [ $j ] ) && count ( $box [ $j ] ) == 0 ) ) return false;
            }
        }
        return true;
    }

    //////
    // solving algorithms
    //////

    // filter values that are already known from the combinations of possibilities
    function kill ( &$data, $notfirst )
    {
        foreach ( $data as $key => $val )
        {
            // compare against the known elements from the beginning
            if ( /*!$notfirst && */!is_array ( $val ) )
            {
                for ( $i = 0; $i < $this -> groesse; $i++ )
                {
                    if ( !is_array ( $data [ $i ] ) ) continue;

                    $d = array_search ( $val, $data [ $i ] );
                    if ( $d !== false )
                    {
                        unset ( $data [ $i ][ $d ] );
                        $this -> changed = true;
                    }
                }
            }
            // compare against elements already found out
            elseif ( is_array ( $val ) && count ( $val ) == 1 )
            {
                $val = array_pop ( $val );

                for ( $i = 0; $i < $this -> groesse; $i++ )
                {
                    if ( $i == $key || !is_array ( $data [ $i ] ) ) continue;

                    $d = array_search ( $val, $data [ $i ] );
                    if ( $d !== false )
                    {
                        unset ( $data [ $i ][ $d ] );
                        $this -> changed = true;
                    }
                }
            }
        }
    }

    // sets fields that are the only one in one set to allow a certain value
    function setUnique ( &$data )
    {
        foreach ( $this -> zeichensatz as $zeichen )
        {
            $temp = array();
            for ( $i = 0; $i < $this -> groesse; $i++ )
            {
                if ( !is_array ( $data [ $i ] ) || count ( $data [ $i ] ) == 1 ) continue;
                if ( array_search ( $zeichen, $data [ $i ] ) !== false )
                {
                    if ( count ( $temp ) < 1 )
                        $temp [ 0 ] = $i;
                    else
                        continue 2;
                }
            }
            if ( !isset ( $temp [ 0 ] ) ) continue;
            $data [ $temp [ 0 ] ][ 0 ] = $zeichen;
            for ( $i = 1; $i < $this -> groesse; $i++ ) unset ( $data [ $temp [ 0 ] ][ $i ] );
            $this -> changed = true;
        }
    }

    // if x combinations exist that include the same x possibilities
    // then those possibilities can be excluded from all other combinations of the same set
    function checkIdentical ( &$data )
    {
        foreach ( $data as $key => $val )
        {
            if ( !is_array ( $val ) ) continue;

            $valcount = count ( $val );
            if ( $valcount == 1 ) continue;

            $temp = array ( $key );

            for ( $i = 0; $i < $this -> groesse; $i++ )
            {
                $datacount = count ( $data [ $i ] );

                if ( !is_array ( $data [ $i ] ) || $datacount == 1 || $key == $i ) continue;

                if ( $valcount == $datacount )
                {
                    $schnittmenge = array_intersect ( $val, $data [$i ] );
                    if ( $val == $schnittmenge )
                        $temp[] = $i;
                }
            }

            if ( count ( $temp ) == $valcount )
            {
                // remove elements from all combinations but $temp
                foreach ( $val as $wert )
                {
                    for ( $i = 0; $i < $this -> groesse; $i++ )
                    {
                        if ( !is_array ( $data [ $i ] ) || in_array ( $i , $temp ) ) continue;

                        $d = array_search ( $wert, $data [ $i ] );
                        if ( $d !== false )
                        {
                            $this -> changed = true;
                            unset ( $data [ $i ][ $d ] );
                        }
                    }
                }
            }
        }
    }

    // similar to the method above, only this time subsets of combinations are checked
    // if subsets are identical then all other possibilities that are not part of the subset
    // can be excluded from those combinations
    function checkCombination ( &$data )
    {
        foreach ( $this -> zeichensatz as $zeichen )
        {
            $schnittmenge = array ( $zeichen );
            $elements     = array();

            // find all combinations that contain this symbol
            for ( $i = 0; $i < $this -> groesse; $i++ )
            {
                if ( !is_array ( $data [ $i ] ) || count ( $data [ $i ] ) == 1 ) continue;

                if ( in_array ( $zeichen, $data [ $i ] ) ) $elements[] = $i;
            }

            // find common intersections of those combinations
            if ( count ( $elements ) >= 2 )
            {
                $schnittmenge = array_intersect ( $data [ $elements [ 0 ] ], $data [ $elements [ 1 ] ] );

                if ( count ( $schnittmenge ) < count ( $elements ) ) continue;

                for ( $i = 2; $i < count ( $elements ); $i++ )
                {
                    $schnittmenge = array_intersect ( $schnittmenge, $data [ $elements [ $i ] ] );
                    if ( count ( $schnittmenge ) < count ( $elements ) ) continue 2;
                }

                // check if other combinations contain elements of that intersection
                for ( $i = 0; $i < $this -> groesse; $i++ )
                {
                    if ( in_array ( $i, $elements ) || !is_array ( $data [ $i ] ) ) continue;
                    $schnittmenge = array_diff ( $schnittmenge, $data [ $i ] );
                    if ( count ( $schnittmenge ) < count ( $elements ) ) continue 2;
                }

                if ( count ( $schnittmenge ) == count ( $elements ) )
                {
                    foreach ( $elements as $el )
                    {
                        $data [ $el ] = array_intersect ( $data [ $el ], $schnittmenge );
                    }
                }
            }
        }
    }

    // the most stupid (and resource eating) algorithm: trial and error
    // just guesses one value and then checks if the sudoku can be solved this way or if
    // it runs into inconsistencies
    function guess ( $box, $step )
    {
        // make a copy of the current state
        $kopie = unserialize ( serialize ( $this ) );

        $kopie -> col_cache = array();
        $kopie -> row_cache = array();
        $kopie -> box_cache = array();

        foreach ( $this -> matrix [ $box ] as $x => $col )
        foreach ( $col as $y => $val )
        {
            if ( is_array ( $val ) && count ( $val ) > 1 )
            {
                foreach ( $val as $guess )
                {
                    $kopie -> matrix [ $box ][ $x ][ $y ] = array ( $guess );
                    if ( $kopie -> solve ( $step ) === true )
                    {
                        $this -> matrix [ $box ][ $x ][ $y ] = array ( $guess );
                        $this -> changed = true;
                        return true;
                    }
                }
            }
        }
        return false;
    }
}

?>
Scripting Corner

PHP: Sudoku Class

PHP:
Sudoku Class
