Autor Zpráva
KarelPolacek
Profil *
#1 · Zasláno: 25. 2. 2016, 08:45:37
Odpovědět Citovat
Ahoj,

snažím se napsat program, co bude řešit sudoku. Stavím na backtrace řešení.

Napsal jsem celou třídu, co by měla sudoku řešit a enormně jednoduché kousky opravdu vyřeší, jenže tím enormně jednoduché myslím, že z 81 čísel chybí tak 5. Klasické sudoku, spadající do kategorie lehké (cca 40 chybějících čísel) už to rozhodně nezvládá. U těch co nezvládá vrací chybu Fatal error: Allowed memory size of 1342177280 bytes exhausted (tried to allocate 65488 bytes). Co jsem tak koukal na internetu a zkoumal, tak to vypadá na infinite loop. Jenže ať jsem hledal jak jsem hledal, nemohl jsem ho najít.

Moje solve třída funguje následovně: 

Najít prázdné políčko
   Pokud dotaz na prázdné políčko vrátí true, tak už neexistuje volné políčko => sudoku je hotové

Pokud je nalezené políčko prázdné, připravíme si číslo 1
Pokud vybrané políčko není prázdné, vezmeme číslo co tam je a přičteme 1 (Tato funkcionalita je kvůli vracení se k již vyplněným políčkům a zkoušením jiné možnosti.)

Vyzkoušíme vložit připravené číslo, pokud s ním obsahuje sudoku chybu, zvětšíme ho o 1, pokud je zkoušené číslo 9 a nefunguje, tak se vracíme k předchozímu políčku (toto celé je while cyklus)

Pokud vložené číslo nezpůsobilo chybu, zapíšeme ho

Celý tento proces se zde spustí znovu sám v sobě (tady by asi mohlo docházet k infinite loop?)

Zkouše jsem to pomocí die() debbugovat, ale prvních pár čísel fungovalo dobře, takže bych řekl, že princip řešení je ok. Kde bych mohla být chyba? 

<?php

class sudokuSolver {

    private $line = 0; 
    private $column = 0;

    private $sudokuOnlyForRead = array( 
    array('', '', '6', '4', '7', '', '3', '', ''),
    array('', '', '4', '6', '5', '', '9', '', ''),
    array('3', '', '', '', '', '8', '', '4', ''),

    array('2', '6', '7', '3', '', '9', '5', '', ''),
    array('8', '', '', '2', '4', '7', '1', '', ''),
    array('', '', '', '', '', '', '', '', '7'),

    array('', '', '2', '', '6', '5', '4', '3', '1'),
    array('', '', '8', '9', '3', '1', '', '2', ''),
    array('', '3', '', '', '', '', '', '', ''),
    );

    private $sudoku = array( 
    array('', '', '6', '4', '7', '', '3', '', ''),
    array('', '', '4', '6', '5', '', '9', '', ''),
    array('3', '', '', '', '', '8', '', '4', ''),

    array('2', '6', '7', '3', '', '9', '5', '', ''),
    array('8', '', '', '2', '4', '7', '1', '', ''),
    array('', '', '', '', '', '', '', '', '7'),

    array('', '', '2', '', '6', '5', '4', '3', '1'),
    array('', '', '8', '9', '3', '1', '', '2', ''),
    array('', '3', '', '', '', '', '', '', ''),
    );


    public function solve()
    {
        $nextEmptyCell = $this->findNextEmptyCell(); 

        startForLastEmptyCell:

        if ($nextEmptyCell === true) {
            return $this->sudoku;
        }

        if (empty($this->getActualCell())) { 
            $newNumber = 1; 
        } else {
            $newNumber = $this->getActualCell()+1;
        }

        while ($this->isNewNumberValid($newNumber) == false) { 
            $newNumber++; 

            if ($newNumber == 10) {
                $this->findLastEmptyCell();
                goto startForLastEmptyCell;
            }
        }

        $this->sudoku[$this->line][$this->column] = $newNumber;

        $this->solve();
    }

    private function isValidInLine($number)
    {
        $searchedLine = $this->line;

        if (in_array($number, $this->sudoku[$searchedLine])) {
            return false;
        } 

        return true;
    }

    private function isValidInColumn($number) 
    {
        $searchedColumn = $this->column;

        foreach ($this->sudoku as $lines) {
            if ($lines[$searchedColumn] == $number) {
                return false;
            }
        }

        return true;
    }

    private function isValidInBox($number)
    {
        $searchedLine = $this->line;
        $searchedColumn = $this->column;

        $linesToInspect = $this->coordsToInspectInBox($searchedLine);
        $columnsToInspect = $this->coordsToInspectInBox($searchedColumn);

        foreach ($linesToInspect as $lineToInspect) {
            foreach ($columnsToInspect as $columnToInspect) {
                if ($number == $this->sudoku[$lineToInspect][$columnToInspect]) {
                    return false;
                }
            }
        }

        return true;
    }

    private function isNewNumberValid($number)
    {
        if ($this->isValidInLine($number) && $this->isValidInColumn($number) && $this->isValidInBox($number)) {
            return true;
        }

        return false;
    }

    private function findNextEmptyCell()
    {
        $nextEmptyCell = '';

        $searchedLine = $this->line; 
        $searchedColumn = $this->column;

        while(empty($nextEmptyCell)) { 

            if ($searchedColumn == 9) { 
                $searchedColumn = 0;
                $searchedLine++;
            } 

            if ($searchedLine == 9) { 
                return true;
            }

            if(empty($this->sudoku[$searchedLine][$searchedColumn])) { 
                $nextEmptyCell = array($searchedLine, $searchedColumn);

                $this->line = $searchedLine;
                $this->column = $searchedColumn;

                return $nextEmptyCell; 
            }

            $searchedColumn++; 
        }
    }

    private function findLastEmptyCell() 
    {
        $lastEmptyCell = '';

        $searchedLine = $this->line;
        $searchedColumn = $this->column;

        while(empty($lastEmptyCell)) { 

            if ($searchedColumn == 0) { 

                $searchedColumn = 8;
                --$searchedLine;
            }

            --$searchedColumn; 

            if(empty($this->sudokuOnlyForRead[$searchedLine][$searchedColumn])) { 

                $lastEmptyCell = array($searchedLine, $searchedColumn);

                $this->line = $searchedLine;
                $this->column = $searchedColumn;
            }
        }

        return $lastEmptyCell; 
    }

    private function coordsToInspectInBox($coord)
    {
        if ($coord % 3 == 0) {
            return array($coord, $coord+1, $coord+2);
        } elseif ($coord % 3 == 1) {
            return array($coord-1, $coord, $coord+1);
        } elseif ($coord % 3 == 2) {
            return array($coord-2, $coord-1, $coord);
        }
    }

    private function getActualCell()
    {
        return $this->sudoku[$this->line][$this->column];
    }

}
juriad
Profil
#2 · Zasláno: 25. 2. 2016, 09:51:42
Odpovědět Citovat
Důvod, proč to nefunguje, je ten, že ty se skoro nikdy nevynoříš z té rekurze. Přidej si do do solve parametr hloubka a uvidíš, jak ti roste. Ty potřebuješ tu hloubku omezit na nějakou uvěřítelnou hodnotu. 

public function solve($hloubka)
{
echo $hloubka . "\n";

...

$this->solve($hloubka + 1);
}

Zahoď informaci o aktuálním políčku (proměnné $line a $column), tu si budeš pamatovat v lokální proměnné ve funkci solve.
Nebudeš ani potřebovat funkce findNextEmptyCell, findLastEmptyCell a getActualCell.

Zkusím ten kód upravit, mezitím si zkus vypisovat tu hloubku, schválně, jestli tě napadne, proč roste.
juriad
Profil
#3 · Zasláno: 25. 2. 2016, 10:26:31
Odpovědět Citovat
Zjednodušený program, který skutečně funguje: 

<?php
 
class SudokuSolver {
 
    private $sudoku;

    function __construct($sudoku) {
        $this->sudoku = $sudoku;
    }
 
    public function solve($line = 0, $column = 0) {
        # returns either true of false
        
        if ($line >= 9) {
            # whole sudoku has been filled in
            return true;
        }

        # empty cell contains 0
        if (!empty($this->sudoku[$line][$column])) {
            # this cell is already filled in; we continue to next one
            return $this->solve($line + ($column + 1 >= 9), ($column + 1) % 9);
        }
 
        # now we know that [$line, $column] is an empty cell to be processed
        for ($number = 1; $number <= 9; $number++) {
            # we try all nine numbers

            if ($this->isNewNumberValid($line, $column, $number)) {
                # if number $number can be assigned, try it
                $this->sudoku[$line][$column] = $number;

                # and try to fill the rest of sudoku
                $solution = $this->solve($line + ($column + 1 >= 9), ($column + 1) % 9);
                if ($solution !== false) {
                    # we found our solution, we can return
                    return true;
                }

                # try different number in next iteration
            }
        }

        # no number works, we have to make the cell empty again
        $this->sudoku[$line][$column] = 0;

        # and go back one step
        return false;
    }
 
    private function isValidInLine($line, $number) {
        return !in_array($number, $this->sudoku[$line]);
    }
 
    private function isValidInColumn($column, $number) {
        foreach ($this->sudoku as $lines) {
            if ($lines[$column] == $number) {
                return false;
            }
        }
 
        return true;
    }
 
    private function isValidInBox($line, $column, $number) {
        # we move $line and $column to top left corner of the box
        $line -= $line % 3;
        $column -= $column % 3;

        # and iterate over the box
        for ($l = $line; $l < $line + 3; $l++) {
            for ($c = $column; $c < $column + 3; $c++) {
                if ($number == $this->sudoku[$l][$c]) {
                    return false;
                }
            }
        }
 
        return true;
    }
 
    private function isNewNumberValid($line, $column, $number) {
        # no need for if
        return $this->isValidInLine($line, $number)
            && $this->isValidInColumn($column, $number)
            && $this->isValidInBox($line, $column, $number);
    }

    public function printSudoku() {
        echo "-------------------\n";
        for ($l = 0; $l < 9; $l++) {
            for ($c = 0; $c < 9; $c++) {
                echo $this->sudoku[$l][$c];
                echo " ";
                if ($c == 2 || $c == 5) {
                    echo " ";
                }
            }
            echo "\n";
            if ($l == 2 || $l == 5) {
                echo "\n";
            }
        }
        echo "-------------------\n\n";
    }
}


$sudoku1 = array( 
    array(0, 0, 6, 4, 7, 0, 3, 0, 0),
    array(0, 0, 4, 6, 5, 0, 9, 0, 0),
    array(3, 0, 0, 0, 0, 8, 0, 4, 0),

    array(2, 6, 7, 3, 0, 9, 5, 0, 0),
    array(8, 0, 0, 2, 4, 7, 1, 0, 0),
    array(0, 0, 0, 0, 0, 0, 0, 0, 7),
 
    array(0, 0, 2, 0, 6, 5, 4, 3, 1),
    array(0, 0, 8, 9, 3, 1, 0, 2, 0),
    array(0, 3, 0, 0, 0, 0, 0, 0, 0),
);

$s1 = new SudokuSolver($sudoku1);
$s1->printSudoku();
if ($s1->solve()) {
    $s1->printSudoku();
} else {
    echo "Has no solution\n";
}
KarelPolacek
Profil *
#4 · Zasláno: 26. 2. 2016, 18:20:03
Odpovědět Citovat
Aha, chápu. Zanořovalo se to cca 200000x. Opravil jsem a použil jsem část Tvé úpravy. Děkuji moc za Tvůj čas.
Časová prodleva: 10 let

Vaše odpověď

Mohlo by se hodit


Prosím používejte diakritiku a interpunkci.

Ochrana proti spamu. Napište prosím číslo dvě-sta čtyřicet-sedm:

0