web-tourist.net

Posted: **Thu Oct 29, 2020 8:33 pm**

Може би ще помогне, ако гледаш малко по-абстрактно на нещата (думи и позиции вместо букви и двумерен масив).

Виж това: https://bg.wikipedia.org/wiki/%D0%91%D0 ... 0%BD%D0%B3

Начинът, по който аз генерирах кръстословица преди 2-3 години, беше:
1. имам клас, който представлява една дума. Той има координати (x, y) - къде започва, ориентация (хоризонтално, вертикално), и самата дума.
2. имам списък от думи, който при желание разбърквам преди да започне алгоритъма.
3. взимам първата дума и я слагам на (0,0), хоризонтално и я слагам в списъка с решения.
4. "влизам едно ниво навътре" (рекурсия), взимам следващата дума.
5. минавам през списъка с решения и се пробвам да я сложа някъде (условия: две думи да имат обща буква и ориентацията да е различна)
6. ако намеря, добавям я в решенията - ако имат обща буква, лесно можеш да изчислиш началната точка и ориентацията.
7. проверявам дали частичното решение е правилно (всички думи, които се пресичат, имат еднакви букви) - може би това е най-сложното. Може би ще помогне да пазиш във всяка дума къде се пресича.
8.1. АКО е наред, продължавам (докато не свърши списъка с думи или друго условие, например размер на кръстословицата)
8.2. АКО не е наред, махам думата от решението, махам едно ниво от рекурсията (бектрекинг) - например return null, и пробвам следващата дума.

Решението ти е списък с думи, техните позиции и ориентация, което е лесно да се визуализира.

Бектрекинг по принцип се имплементира почти буквално, както е описан – възможно е да има готови решения за PHP. Има разни оптимизации (forward checking, определена подредба на списъка с думи, и др.), които отхвърлят лоши решения по-рано. Това, което описах, може да се разшири (например, при лошо частично решение да не се отхвърля думата, а да се пробва друга позиция, ако съществуват няколко пресечни точки).

Posted: **Fri Oct 30, 2020 6:43 pm**

Правил съм подобно нещо. Не нормална кръстословица с въпроси, а такава с разбъркани думи, които трябва да се открият по хоризонтал, вертикал и диагонал (в двете посоки).

Пресичането го правя чрез рекурсия като тествам всяка една посока и минавам през всяка една буква на думата. Когато буквата стъпе на празен квадрат я слагам там и продължавам по избраната посока докато всички букви стъпят. Ако пресека квадрат, който вече има буква там, проверявам дали буквите съвпадат. Ако съвпадат - чудесно, продължавам напред - ако не съвпадат, значи тази посока не е правилната и я записвам като fail. И така през всяка една посока (напред и обратно). Ако всички посоки не стават, взимам нови стартови координати и правя същото.

Тествал съм с много думи и съм нямал проблем. С известни промени може да се направи да генерира и нормална кръстословица.
Със сигурност може да се направи по-добре, но нямах толкова време, а след това не ми се занимаваше.

Posted: **Tue Nov 03, 2020 11:02 am**

class.grid.php

Code: Select all

<?php
//----------------------------------------------------------------------
//  AUTHOR	: Jean-Francois GAZET
//  WEB		: http://www.jeffprod.com
//  TWITTER	: @JeffProd
//  MAIL	: jeffgazet@gmail.com
//  LICENCE	: GNU GENERAL PUBLIC LICENSE Version 2, June 1991
//----------------------------------------------------------------------

class Grid  {
    
    // SETTINGS ------------------------------------------------
    const MIN_LEN_WORD = 3; // longueur min des mots en base
    const MAX_LEN_WORD = 6; // longueur max des mots en base
    const DEFAULT_GRID_SIZE = 6; // taille grille par défaut
    // END SETTINGS --------------------------------------------
    
    const RENDER_HTML = 0; // afficher la grille en HTML
    const RENDER_TEXT = 1; // afficher la grille en mode texte
    
    private $_size; // (Int) longueur du coté de la grille carrée
    private $_cells; // (tableau de size*size éléments String) cellules de la grille, chacune contenant une lettre
    private $_wordsList; // (tableau d'objets Word) : liste des mots à trouver
    private $_arrayCOL; // tableau (Int) des numéros des colonnes d'après les index des cellules
    private $_db; // base de données de mots SQLite
    private $_errorMsg; // chaine de texte non nulle en cas d'erreur
    
    public function __construct($size=self::DEFAULT_GRID_SIZE) {
        
        $this->_errorMsg='';
        
        if($size<self::MIN_LEN_WORD || $size>self::MAX_LEN_WORD) {
            $this->_errorMsg='size must be between '.self::MIN_LEN_WORD.' and '.self::MAX_LEN_WORD;
            echo $this->_errorMsg;
            return;
            }
        
		$this->_size=$size;
        $this->_wordsList=array();
        $this->_cells=array_fill(0,$this->_size*$this->_size,'');
        $this->_db = new SQLite3('words.db',SQLITE3_OPEN_READONLY);
        
        // index des colonnes dans 2 grilles apposées verticalement
        // pour gérer les dépassement en bas
        $this->_arrayCOL = array(); 
        for($i=0;$i<(2*$this->_size*$this->_size);$i++) {
            $this->_arrayCOL[$i]=self::COL($i);
            }
		}
        
    public function __destruct() {
        if($this->_errorMsg!='') {return;}
        $this->_db->close();
        }
        
    public function getWordsList($end=' ') {
        
        // Retourne la liste des mots à trouver dans la grille par ordre alphabétique.
        // $end : séparateur de mots défini par l'utilisateur (\n, <br>, espace...)
        
        if($this->_errorMsg!='') {return;}
        $arr=array();
        foreach($this->_wordsList as $word) {
            $label=$word->getLabel();
            if($word->isReversed()) {$label=strrev($label);}
            $arr[]=$label;
            }
        sort($arr);
        $r='';
        foreach($arr as $label) {
            $r.=$label.$end;
            }        
        return $r;
        }
        
    public function getNbWords() {
        return count($this->_wordsList);
        }
        
    public function gen() {        

        // Cré une nouvelle grille        

        if($this->_errorMsg!='') {return;}        

        $size2=$this->_size*$this->_size;
        $i=rand(0,$size2-1); // on part d'une case au hasard
        
        // on parcourt toutes les cases
        $cpt=0;
        while($cpt<$size2) {
            $this->placeWord($i);
            $cpt++;
            $i++;
            if($i==$size2) {$i=0;}
            }
        } // gen()
    
    private function placeWord($start) {

        // Tente de placer un mot dans la case de départ $start, avec au hasard :
        // - horizontal,vertical,diagonal
        // - inversé

        // nouveau mot, case de départ donné en param ($start)
        $word=new Word(
            $start, // index de la case de départ
            -1, // fin, on verra plus bas selon l'orientation et la longueur du mot
            rand(0,2), // orientation
            '', // libellé tiré au dernier moment
            (0) // rand(0,1) == 1   inversé : true ou false au hasard
            );

        $inc=1; // incrément
        $len=rand(self::MIN_LEN_WORD,$this->_size); // longueur d'un mot au hasard, de MIN_LEN_WORD à _size
        
        switch($word->getOrientation()) {

            case Word::HORIZONTAL:
                $inc=1;
                $word->setEnd($word->getStart()+$len-1);
                 // si mot placé sur 2 lignes on décale à gauche
                while( $this->_arrayCOL[$word->getEnd()] < $this->_arrayCOL[$word->getStart()] ) {
                    $word->setStart($word->getStart()-1);
                    $word->setEnd($word->getStart()+$len-1);
                    }
                break;

            case Word::VERTICAL:
                $inc=$this->_size;
                $word->setEnd($word->getStart()+($len*$this->_size)-$this->_size);
                // si le mot dépasse la grille en bas, on décale vers le haut
                while($word->getEnd()>($this->_size*$this->_size)-1) {
                    $word->setStart($word->getStart()-$this->_size);
                    $word->setEnd($word->getStart()+($len*$this->_size)-$this->_size);
                    }
                break;
            }

        // on construit le pattern SQL ("A__O___") si le mot croise des lettres présentes dans la grille
        $s='';
        $flag=false;
        for($i=$word->getStart();$i<=$word->getEnd();$i+=$inc) {
            if($this->_cells[$i]=='') {$s.='_';}
            else {
                $s.=$this->_cells[$i];
                $flag=true;
                }
            }
   
        // si on trouve que des '_' => pas de chevauchement on ajoute le mot
        if(!$flag) {
            $word->setLabel($this->getRandomWord($len)); // on doit tirer un mot de longueur len
            if($word->isReversed()) {$word->setLabel(strrev($word->getLabel()));}
            $this->addWord($word);
            }

        // sinon
        else {
            // si le pattern est un texte entier on quitte
            if(strpos($s,'_')===false) {return;}

            // on en pioche un avec ce pattern
            $word->setLabel($this->getWordLike($s));
            $word->setReverse(false); // le nouveau mot pioché n'est pas inversé

            // ajout du mot (test null dans addmot)
            $this->addWord($word);
            }
        /*
        */

        } // placeWord()
       
    public function render($type=Grid::RENDER_HTML) {
        
        // Affiche la grille complète au format
        // TEXTE ou HTML (par défaut)
        
        if($this->_errorMsg!='') {return;}
        
        $r='';
        
        switch($type) {
            case Grid::RENDER_HTML:
            $cpt=0;
            $r.='<style type="text/css">
                table.gridtable {
                    font-family: verdana,arial,sans-serif;
                    font-size:16px;
                    color:#333333;
                    border-width: 1px;
                    border-color: #333;
                    border-collapse: collapse;
                    }
                table.gridtable td {
                    border-width: 0px;
                    padding: 8px;
                    border-style: solid;
                    border-color: #666666;
                    background-color: #ffffff;
                    }
                </style>'.PHP_EOL;
            $r.='<table class="gridtable">'.PHP_EOL;
            foreach($this->_cells as $letter) {
                if($cpt==0) {
                    $r.='<tr>';
                }
                if($letter == '') {
                    $r.='<td style="background: #000"></td>';//'.chr(rand(65,90)).' 
                }
                else {$r.='<td style="background: #fefefe">'.$letter.'</td>';}
                $cpt++;
                if($cpt==$this->_size) {$r.='</tr>'.PHP_EOL; $cpt=0;}
                }
            $r.='</table>'.PHP_EOL;
            break;
            
            case Grid::RENDER_TEXT:
            $cpt=0;
            foreach($this->_cells as $letter) {
                if($letter=='') {
                    $r.= ''; //chr(rand(65,90))
                }
                else {
                    $r.=$letter;
                }
                $r.=' ';
                $cpt++;
                if($cpt==$this->_size) {$r.="\n"; $cpt=0;}
                }            
            break;
            }
                        
        return $r;
        }
        
    private function COL($x) {
        // IN : (int $x) = index de la case
        // OUT : (int) numéro de la colonne, de 1 à $this->_size
        return ($x % $this->_size)+1;
        }        

    private function getRandomWord($len) {
        // IN (Int) : longueur du mot $len
        // OUT (String) : un mot au hasard de longueur $len
        $rqtxt='SELECT word FROM words WHERE LENGTH(word)='.$len.' ORDER BY RANDOM() LIMIT 1';
        return $this->_db->querySingle($rqtxt);
        }
        
    private function getWordLike($pattern) {
        // Retourne un mot qui ressemble au pattern.
        // IN (String) : $pattern, ex : A__U__S
        // OUT (String) : un mot au hasard qui correspond, "" sinon
        $rqtxt='SELECT word FROM words WHERE word LIKE "'.$pattern.'" ORDER BY RANDOM() LIMIT 1';
        return $this->_db->querySingle($rqtxt);
        }        

    private function addWord($word) {

        // ajoute un mot :
        // - dans les cases de la grille
        // - à la liste des mots à trouver
        
        if($word->getLabel()=='') {return;}

        // Ajout dans les cases de la grille
        $j=0;
        switch($word->getOrientation()) {

            case Word::HORIZONTAL:
                for ($i=$word->getStart(); $j<strlen($word->getLabel()); $i++) {
                    $this->_cells[$i]=substr($word->getLabel(),$j,1);
                    $j++;
                    }
                break;

            case Word::VERTICAL:
                for($i=$word->getStart(); $j<strlen($word->getLabel()); $i+=$this->_size) {
                    $this->_cells[$i]=substr($word->getLabel(),$j,1);
                    $j++;
                    }
                break;


            } // switch

        // Ajout du mot à la liste
        $this->_wordsList[]=$word;

        } // addWord()        

    } // class Grid
?>

class.word.php

Code: Select all

<?php
//----------------------------------------------------------------------
//  AUTHOR	: Jean-Francois GAZET
//  WEB		: http://www.jeffprod.com
//  TWITTER	: @JeffProd
//  MAIL	: jeffgazet@gmail.com
//  LICENCE	: GNU GENERAL PUBLIC LICENSE Version 2, June 1991
//----------------------------------------------------------------------

class Word {
    
    const HORIZONTAL = 0;
    const VERTICAL = 1;
    const DIAGONAL_LEFT_TO_RIGHT = 2;
    const DIAGONAL_RIGHT_TO_LEFT = 3;
    
    private $_orientation; // orientation du mot
    private $_label; // intitulé du mot
    private $_reversed; // libellé inversé ou non (true,false)
    private $_start; // index de la case de départ
    private $_end; // index de la case d'arrivée
        
    public function __construct($start,$end,$orientation,$label,$reversed) {
        $this->_start=$start;
        $this->_end=$end;
		$this->_orientation=$orientation;
        $this->_label=$label;
        $this->_reversed=$reversed;
		}    
       
    public function setStart($start) {
        $this->_start=$start;
        }
        
    public function setEnd($end) {
        $this->_end=$end;
        }
        
    public function setLabel($label) {
        $this->_label=$label;
        }      
        
    public function setReverse($reverse) {
        $this->_reversed=$reverse;
        }  
      
    public function getStart() {
        return $this->_start;
        }

    public function getEnd() {
        return $this->_end;
        }
        
    public function getLabel() {
        return $this->_label;
        }        
        
    public function isReversed() {
        return $this->_reversed;
        }    

    public function getOrientation() {
        return $this->_orientation;
        }
        
    } // class Word
?>

index.php

Code: Select all

<?php
//----------------------------------------------------------------------
//  AUTHOR	: Jean-Francois GAZET
//  WEB		: http://www.jeffprod.com
//  TWITTER	: @JeffProd
//  MAIL	: jeffgazet@gmail.com
//  LICENCE	: GNU GENERAL PUBLIC LICENSE Version 2, June 1991
//----------------------------------------------------------------------

require_once 'class.grid.php';
require_once 'class.word.php';

$grid=new Grid();
$grid->gen();
echo $grid->render();
echo "Words to find (".$grid->getNbWords().") :\n";
echo $grid->getWordsList("\n");
?>

words.zip

Posted: **Tue Nov 03, 2020 2:43 pm**

Даже няма да си направя труда да разбера кода. Написан е все едно е книга написана без препинателни знаци. Още малко да го беше минал и през minifier.

web-tourist.net

Скрипт/код/база данни за кръстословица

Re: Скрипт/код/база данни за кръстословица

Re: Скрипт/код/база данни за кръстословица

Re: Скрипт/код/база данни за кръстословица

Re: Скрипт/код/база данни за кръстословица