Може би ще помогне, ако гледаш малко по-абстрактно на нещата (думи и позиции вместо букви и двумерен масив).
Виж това: 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, определена подредба на списъка с думи, и др.), които отхвърлят лоши решения по-рано. Това, което описах, може да се разшири (например, при лошо частично решение да не се отхвърля думата, а да се пробва друга позиция, ако съществуват няколко пресечни точки).
Скрипт/код/база данни за кръстословица
-
Revelation
- Web-tourist
- Posts: 921
- Joined: Sun Mar 24, 2013 1:23 pm
Re: Скрипт/код/база данни за кръстословица
Правил съм подобно нещо. Не нормална кръстословица с въпроси, а такава с разбъркани думи, които трябва да се открият по хоризонтал, вертикал и диагонал (в двете посоки).
Пресичането го правя чрез рекурсия като тествам всяка една посока и минавам през всяка една буква на думата. Когато буквата стъпе на празен квадрат я слагам там и продължавам по избраната посока докато всички букви стъпят. Ако пресека квадрат, който вече има буква там, проверявам дали буквите съвпадат. Ако съвпадат - чудесно, продължавам напред - ако не съвпадат, значи тази посока не е правилната и я записвам като fail. И така през всяка една посока (напред и обратно). Ако всички посоки не стават, взимам нови стартови координати и правя същото.
Тествал съм с много думи и съм нямал проблем. С известни промени може да се направи да генерира и нормална кръстословица.
Със сигурност може да се направи по-добре, но нямах толкова време, а след това не ми се занимаваше.
Пресичането го правя чрез рекурсия като тествам всяка една посока и минавам през всяка една буква на думата. Когато буквата стъпе на празен квадрат я слагам там и продължавам по избраната посока докато всички букви стъпят. Ако пресека квадрат, който вече има буква там, проверявам дали буквите съвпадат. Ако съвпадат - чудесно, продължавам напред - ако не съвпадат, значи тази посока не е правилната и я записвам като fail. И така през всяка една посока (напред и обратно). Ако всички посоки не стават, взимам нови стартови координати и правя същото.
Тествал съм с много думи и съм нямал проблем. С известни промени може да се направи да генерира и нормална кръстословица.
Със сигурност може да се направи по-добре, но нямах толкова време, а след това не ми се занимаваше.
Re: Скрипт/код/база данни за кръстословица
class.grid.php
class.word.php
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
//----------------------------------------------------------------------
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
?>
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
?>
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");
?>
You do not have the required permissions to view the files attached to this post.
-
Revelation
- Web-tourist
- Posts: 921
- Joined: Sun Mar 24, 2013 1:23 pm
Re: Скрипт/код/база данни за кръстословица
Даже няма да си направя труда да разбера кода. Написан е все едно е книга написана без препинателни знаци. Още малко да го беше минал и през minifier.