Online PHP editor | output for 5Z6BL

@ 2019-05-15T23:03:07Z

<?php

class SudokuGenerator extends SudokuSolver
{
    public $EleArray = NULL;
    const METRIC_EASY = 27;
    const METRIC_MEDIUM = 22;
    const METRIC_HARD = 17;
    public function __construct()
    {
        $this->EleArray();
        parent::__construct();
    }
    /*
    Creates an array of possible (row, col) combinations. So that uniquely a random elemnt can be selected
     */
    public function EleArray() 
    {
        $EleArray = array();
        foreach(range(0, 8) as $i )
            foreach(range(0, 8) as $j )
                    $EleArray[] = array($i, $j);
        $this->EleArray = $EleArray;
    }
    public function FillRandomValue()
    {
        if( $this->EleArray === NULL )
            throw new Exception('$this->EleArray() must be called before FillRandomValue', 1);
            
        $ele = array_rand( $this->EleArray );
        $randCol = $this->EleArray[$ele][0];
        $randRow = $this->EleArray[$ele][1];
        unset($this->EleArray[$ele]);
        for ( $i = 1; $i <= 9; $i++ )
        {
            if( $this->checkValid($randRow, $randCol, $i) )
            {
                $this->_oSudoku[$randRow][$randCol] = $i;
                break;
            }
        }
    }
    public function GenerateSudoku( $difficulty )
    {
        $this->EleArray();
        for( $i = 0; $i < $difficulty; $i++ )
            $this->FillRandomValue();
        do {
            $this->FillRandomValue();
            $this->Solve();
        } while( $this->HasUnique() === self::NOT_UNIQUE );
    }
}

class SudokuSolver {
    protected $_iSudoku = array();
    protected $_oSudoku = array();
    protected $_stack;
    protected $_blocks;
    protected $_oSudoku90;
    protected $_compare;
    const NOT_SOLVABLE = 10;
    const NOT_UNIQUE = 11;
    public function __construct( $sudoku = NULL, $stack = NULL, $seedVal = 0 ) {
        $this->seedVal = $seedVal;
        if ( $stack === NULL )
            $this->_stack = new Stack();
        else
            $this->_stack = $stack;
        if ( $sudoku === NULL )
            $sudoku = str_repeat( "0", 81 );
       
        /** Creates an sudoku array from the supplied string or empty string */
        if ( is_string( $sudoku ) ):
            $sudoku = str_split( $sudoku, 9 );
        array_walk( $sudoku, function( &$arg ) {
                $arg = str_split( $arg );
            } );
        endif;
        $this->_iSudoku = $this->_oSudoku = $sudoku;
        $this->_compare = range(1, 9);
        $this->_constuctBlock();
    }
    // Constructs block of 3 x 3 array, and row wise block that can later be used for direct
    // finding of possibles instead of looping
    protected function _constuctBlock() {
        for ( $x = 0; $x < 9; $x++ ) {
            $this->_oSudoku90[$x] = array();
            for ( $y = 0; $y < 9; $y++ ) {
                $this->_oSudoku90[$x][$y] = &$this->_oSudoku[$y][$x];
            }
        }
        // create '_blocks'
        for ( $blockX = 0; $blockX < 3; $blockX++ ) {
            $this->_blocks[$blockX] = array();
            for ( $blockY = 0; $blockY < 3; $blockY++ ) {
                $this->_blocks[$blockX][$blockY] = array();
                $gridX = $blockX * 3;
                for ( $cellX = 0; $cellX < 3; $cellX++ ) {
                    $gridY = $blockY * 3;
                    for ( $cellY = 0; $cellY <3; $cellY++ ) {
                        $this->_blocks[$blockX][$blockY][] = &$this->_oSudoku[$gridX][$gridY++];
                    }
                    $gridX++;
                }
            }
        }
    }
    /** The following functions find the possibles for column, row and 3 x 3 block */
    public function missingColumn($m) {
        return array_diff($this->_compare, $this->_oSudoku[$m]);
    }
    
    public function missingRow($n) {
        return array_diff($this->_compare, $this->_oSudoku90[$n]);
    }
    
    public function missingBlock($m,$n) {
        return array_diff($this->_compare, $this->_blocks[$m][$n]);
    }
    
    /* An intersect of all the possibles finds the possibles obeying rules of sudoku */
    public function possibles( $m, $n ) {
        return array_intersect(
            $this->missingBlock((int)$m / 3, (int)$n / 3),
            $this->missingColumn($m),
            $this->missingRow($n)
        );
    }
    public function checkValid( $m, $n, $val ) {
        return in_array( $val, array_intersect(
            $this->missingBlock((int)$m / 3, (int)$n / 3),
            $this->missingColumn($m),
            $this->missingRow($n)
        ));
    }
    /**
     * Function checks if the sudoku has a unique solution
     */
    public function HasUnique() {
        while ( !$this->_stack->isEmpty() ) {
            $stack = new Stack();
            $oldSudoku = &$this->_oSudoku;
            list( $m, $n ) = $this->_stack->pop();
            $val = $oldSudoku[$m][$n];
            $oldSudoku[$m][$n] = 0;
            $sudoku = new SudokuSolver( $oldSudoku, $stack, $val );
            if ( $sudoku->Solve() !== self::NOT_SOLVABLE )
                return self::NOT_UNIQUE;
        }
        return TRUE;
    }
    public function Solve() {
        $m = $n = 0;
        fx: while ( $m !== 9 ): //Loop till 9 x 9 sudoku processed
            if ( ( (int)( $cell = &$this->_oSudoku[$m][$n] ) === 0 ) ) {
                foreach ( $this->possibles($m, $n) as  $val) {
                    $this->seedVal = 0;
                    
                    //If cell's value was less than value of $val means insertion
                    //must be done otherwise it means it has returned from backtracking 
                    if( $cell < $val )
                        $cell = $val;
                    else
                        continue;
                    $this->_stack->push( $m, $n ); //Record the insertion
                    if ( $n === 8 ):
                        $m += 1;
                        $n = 0;
                    else:
                        $n += 1;
                    endif;
                    goto fx; ///if insertion was valid continue while
                }
                $this->_oSudoku[$m][$n] = 0;
                if ( $this->_stack->isEmpty() ) //If backtracked till begining return NOT SOLVABLE
                    return self::NOT_SOLVABLE;
                else
                    list( $m, $n ) = $this->_stack->pop(); //backtrack
            } else {
                if ( $n === 8 ):
                    $m += 1;
                    $n = 0;
                else:
                    $n += 1;
                endif;
        }
        endwhile;
    }
    public function OutputArray() {
        return $this->_oSudoku;
    }
    public function OutputString() {
        array_walk( $this->_oSudoku, function( &$ele ) { $ele = implode( "", $ele ); } );
        return implode( "", $this->_oSudoku );
    }
    public function __toString() {
        return print_r( $this->_oSudoku, true );
    }
}

class Stack {
    private $stk = array();
    public function push($m, $n) {
        array_push( $this->stk, array($m, $n) );
    }
    public function pop() {
        return array_pop($this->stk);
    }
    public function isEmpty()
    {
        return count($this->stk) === 0;
    }
    public function stackHeight()
    {
        return count( $this->stk );
    }
    public function emptyStack()
    {
        while( !$this->isEmpty() )
            $this->pop();
    }
}

$sudoku = new SudokuGenerator();
$sudoku->GenerateSudoku( SudokuGenerator::METRIC_EASY );

$sudoku = new SudokuSolver($sudoku->OutputString());
$sudoku->Solve();

print $sudoku->OutputString();

Output for 7.4.1: 351267849264385170000001023000010002000030000000002004140020000500143200632500001
Output for 7.4.0: 457263891683451720200000043540302010000000004016000032034020100000000200120030000
Output for 7.3.13: 453671829672839514891542673524167980306004150100200300200010430000453000000020000
Output for 7.3.12: 253946178647150002100830000000600000501400000030205010010320504400561723000700000
Output for 7.3.11: 637514289825679103400230500140300000302001000500420000004100020003000041200040000
Output for 7.3.10: 678219030040500000510003042000002103020104050000000000031000500000401000700300421
Output for 7.3.9: 364527189728169453519384672472698315853271946196435728235716894987040201601002000
Output for 7.3.8: 371245689528176403460000210050000002000400031130062540000000304010000050040300120
Output for 7.3.7: 426357891157264300000000200300001042000543000004002510002000000000100600010020403
Output for 7.3.6: 456718290203000001010004003024005010130402000005300402000250100000043025002100000
Output for 7.3.5: 546781392728653104300240000200304000004102000001506000002000003100005200003000410
Output for 7.3.4: 657289401302401000000003200000014000040020300035000120003000040010040030400032010
Output for 7.3.3: 235416789617538420000000130100000000002100000864357201301002000020003010050001340
Output for 7.3.2: 415672893367518042200000051003200100000100000000043000000321004102000035000054200
Output for 7.3.1: 637418290052000013400300005000240031000000000300105002040600000100520004023000106
Output for 7.3.0: 325176894614389275789452316256793481478510020130000000000045100000621003040030002
Output for 7.2.26: 346872159578416200120530000000320000001045602000601034005000000634100025002700010
Output for 7.2.25: 346782951578146023020053000100020000200310040000400010030000105000030204014200300
Output for 7.2.24: 137586429462793185589412637623857914741239568895641273354168792916325840200000301
Output for 7.2.23: 256471389417326000000050120100000000300165742020030510034002001001000000000000034
Output for 7.2.22: 467238519215467830030100200000321004300000072001004000100000450003000027000000361
Output for 7.2.21: 243617895561843720000000060000000010020300640010000250000000030302104500100025074
Output for 7.2.20: 243657819651849372789213456372165948194728530000304201060500023020030104010400000
Output for 7.2.19: 126834907007000040004210503003000001000305420402001300005020000010500000000403012
Output for 7.2.18: 456782190000453020320010400000004001001200030234000000102040050000136000000025003
Output for 7.2.17: 123657849567824000000100302000500020000040003000302010002403160056210430301000250
Output for 7.2.16: 316278459782435160054100203000001035001356042040002001000003000030000010025000000
Output for 7.2.15: 367824915584631702000050043000140020000002004120300000010000250200000061400005030
Output for 7.2.14: 423678591785241360001000000350020016064103020000000430100000000230000100500010240
Output for 7.2.13: 172638495356217800040000001000000002000021603000000500401503020530002100020104000
Output for 7.2.12: 174852693625731804000000200030046021502000000410003000200005000301604002040020100
Output for 7.2.11: 457312689312678450006054012004200030003140000160500000001403205000000001025000300
Output for 7.2.10: 617524839253167400004300261000001327102430056030200104001000000000000002000002000
Output for 7.1.12, 7.2.9: 615327489278514300003000012000000000000130200406200001054001060020050130301400020
Output for 7.2.8: 432576891567481302000000400200300100000000020005000000003205014004100200621700000
Output for 7.2.7: 357489261641753890000026005010000004400317020200540013000200000000600130020001000
Output for 7.2.6: 253784691178536402000100000431270000000040100000050000002010063310002005000060014
Output for 7.2.5: 451789326236100405000000001000213000145000030020040000000402613000000000000031502
Output for 7.2.4: 567481329849253671201000040400012000702046103130000000300005210000004005020100000
Output for 7.2.3: 643578910015002304200100050030000100001030240400210000000003001020001400000004032
Output for 7.2.2: 674289513385461279921357486753698142246175830100020000030002061002010004000000025
Output for 7.2.1: 451783629678521300320046051000352010010400002002000000100000046040100003200000175
Output for 7.2.0: 374158269568243701012000003100020000000400000200030010001000000025010034043600025
Output for 7.1.33: 374625819689714325215389467451867900020531000030240000000003204140000500002400130
Output for 7.1.32: 316578249275314680040200150000432001050061320000000000030100062020003000100020030
Output for 7.1.31: 563417289472689501000253000030000400200164300014005062005002130300040000100000020
Output for 7.1.30: 637218594124657830000300102300000400010530200000400600000000016240100000001002305
Output for 7.1.29: 234567891718493526569128437473215689681749352952630174000000703000000210120050000
Output for 7.1.28: 425167389361542700000000000000023010103000000000010402004030021000200500032051000
Output for 7.1.27: 452761389678253014130000200000000030000102605315006420004310000000400100020605000
Output for 7.1.26: 654137829783425601020000000240001350300000400015043200530200140400310000000504002
Output for 7.1.25: 785369214946125378123748569518972400400010000230004100054601032307200001060030000
Output for 7.1.24: 156378249247651803000002015030200000002413506010500000401025030000000104063100002
Output for 7.1.23: 246317589513426700000000204001002000002004103005001406134000602000005340000230051
Output for 7.1.22: 563714829214856370000320041000205013000001000100000200000000102001000035000100004
Output for 7.1.21: 571463829283157406460020301100000003000000210030000000314000500020030100000000002
Output for 7.1.20: 163758290000002003005430100030004050002000040041000730000501300000020014510043620
Output for 7.1.19: 265317849417895236389246517574932681628154370030600420040508100050723000000461000
Output for 7.1.18: 475183962689275314031004005000000000024000000000000201000010020003420100210030040
Output for 7.1.17: 513246789762893145849175236657918324421637598380020010000002001030504002204001003
Output for 7.1.16: 627841953183265470050000001240010030310420506005000140000003020000000060432050010
Output for 7.1.15: 142673589678125003300000124403500210000231460000400005000310040021054000000002031
Output for 7.1.14: 627451389541236700300000100003004020000005600200003501030012405010000000400300012
Output for 7.1.13: 784263195152789436369145728475621803203000001010000200026010307540000012030500064
Output for 7.1.11: 471683259658742301000105000003010020002034100010000000160350402000000030020060510
Output for 7.1.10: 215436789678921403340050120063210050100000340000000002000300001020100030500002604
Output for 7.1.9: 152647893673859021000000004000132050025004000431506000010300042300020010240010000
Output for 7.1.8: 643572189275618304001004000050030020300050001420001003000000000000143502010020400
Output for 7.1.7: 567823194489751362123649578274580013301406000000210040002100000000030200035002001
Output for 7.1.6: 671328945238549761594716832357160420046200103010000000102605304003000010405000200
Output for 7.1.5: 783452691162789534459361278645817302010030000000200010300520100500000000204100000
Output for 7.1.4: 874936512123475869569182374786053201410200003000041000002010000001000400000020000
Output for 7.1.3: 671482539382569147549137628263795481197843256458216370000301000000020010004650000
Output for 7.1.2: 526738941471692358389514267295167430010000002043005610060000003152003004030000120
Output for 7.1.1: 361748295247361800000502314000000001003204000002613000005100002004020103100000000
Output for 7.1.0: 423657189576814032100000004000000010000000200200501003000100000054300021361482597

preferences:dark modelive preview