using System.Collections.Generic;
public class CrosswordsAlgorithm
public List<CrossedWord> CrToShow = new List<CrossedWord>();
float crosswordLength = float.MaxValue;
int WordsPlaced = 0, crosswordMinX = 0, crosswordMinY = 0;
Random random = new Random();
public void GenerateCrossWords(List<string> words)
List<CrossedWord> fixedwordsList = new List<CrossedWord>();
foreach (string word in words)
fixedwordsList.Add(new CrossedWord(word, "0"));
List<CrossedWord> CrossWordsToKeep = new List<CrossedWord>();
crosswordLength = float.MaxValue;
for (int gen = 0; gen < fixedwordsList.Count; gen++)
List<CrossedWord> allWords = new List<CrossedWord>(fixedwordsList);
for (int j = allWords.Count - 1; j > 0; j--)
int r = random.Next(0, j + 1);
CrossedWord tmp = allWords[r];
allWords[r] = allWords[j];
List<CrossedWord> finalWords = new List<CrossedWord>();
finalWords.Add(new CrossedWord(allWords[0]));
int minX = 0, maxX = finalWords[0].Size - 1, minY = 0, maxY = 0;
int maxLoop = (int)(allWords.Count * allWords.Count);
for (; 0 != allWords.Count && z < maxLoop; z++)
CrossedWord currentWordToPlace = new CrossedWord(allWords[i]);
Tile BestStartingPosition = new Tile(0, 0);
CrossedWord.Direction BestDirection = CrossedWord.Direction.Horizontal;
float score = float.MaxValue;
for (int j = 0; j < finalWords.Count; j++)
CrossedWord currentWordPlaced = finalWords[j];
currentWordToPlace.WordDirection = currentWordPlaced.WordDirection == CrossedWord.Direction.Horizontal ? CrossedWord.Direction.Vertical : CrossedWord.Direction.Horizontal;
List<Tile>[] intersectionForEachLetter = currentWordPlaced.SimilarLetterTiles(currentWordToPlace);
for (int k = 0; k < intersectionForEachLetter.Length; k++)
for (int l = 0; l < intersectionForEachLetter[k].Count; l++)
Tile currentCommonTile = intersectionForEachLetter[k][l];
if (currentWordPlaced.WordDirection == CrossedWord.Direction.Horizontal)
currentWordToPlace.StartingPosition = new Tile(currentCommonTile.X, currentCommonTile.Y - k);
currentWordToPlace.StartingPosition = new Tile(currentCommonTile.X - k, currentCommonTile.Y);
bool bCanBePlaced = true;
for (int m = 0; m < finalWords.Count && bCanBePlaced; m++)
int ca = finalWords[m].CanAccept(currentWordToPlace);
if (bCanBePlaced && iCanBePlaced > 0)
int crossedNumber = (0 - iCanBePlaced);
float tmpScore = random.Next(0, 10) + crossedNumber * 100;
BestStartingPosition = currentWordToPlace.StartingPosition;
BestDirection = currentWordToPlace.WordDirection;
currentWordToPlace.StartingPosition = BestStartingPosition;
currentWordToPlace.WordDirection = BestDirection;
finalWords.Add(currentWordToPlace);
for (int j = finalWords.Count - 1; j > 0; j--)
int r = random.Next(0, j + 1);
CrossedWord tmp = finalWords[r];
finalWords[r] = finalWords[j];
minX = Math.Min(minX, currentWordToPlace.StartingPosition.X);
minY = Math.Min(minY, currentWordToPlace.StartingPosition.Y);
maxX = Math.Max(maxX, currentWordToPlace.WordDirection == CrossedWord.Direction.Horizontal ? currentWordToPlace.StartingPosition.X + currentWordToPlace.Size - 1 : currentWordToPlace.StartingPosition.X);
maxY = Math.Max(maxY, currentWordToPlace.WordDirection == CrossedWord.Direction.Vertical ? currentWordToPlace.StartingPosition.Y + currentWordToPlace.Size - 1 : currentWordToPlace.StartingPosition.Y);
i = (i + 1) % allWords.Count;
float newLength = (float)Math.Sqrt((maxX - minX) * (maxX - minX) + (maxY - minY) * (maxY - minY));
int currentWordsPlaced = finalWords.Count;
if (newLength - (currentWordsPlaced - WordsPlaced) * 4 < crosswordLength && WordsPlaced < currentWordsPlaced)
CrossWordsToKeep = finalWords;
crosswordLength = newLength;
WordsPlaced = currentWordsPlaced;
for (int r = 0; r < CrossWordsToKeep.Count; r++)
CrossWordsToKeep[r].StartingPosition.X += Math.Abs(crosswordMinX);
CrossWordsToKeep[r].StartingPosition.Y += Math.Abs(crosswordMinY);
CrToShow = CrossWordsToKeep;
public Tile(int x, int y) {
public override bool Equals(Object obj) {
if (obj == null) return false;
Tile otherTile = obj as Tile;
return this.X == otherTile.X && this.Y == otherTile.Y;
public override int GetHashCode() {
public bool Equals(Tile t) {
return this.X == t.X && this.Y == t.Y;
public class CrossedWord : IComparable
private Tile _startingPosition;
private Direction _wordDirection;
set {this._word = value;}
set {this._clue = value;}
get{return this._word.Length;}
public Tile StartingPosition
get{return this._startingPosition;}
set{this._startingPosition = value;}
public Direction WordDirection
get{return this._wordDirection;}
set{this._wordDirection = value;}
public CrossedWord(string word, string clue){
this.WordDirection = Direction.Horizontal;
this.StartingPosition = new Tile(0,0);
public CrossedWord(CrossedWord previous){
this.Word = previous.Word;
this.Clue = previous.Clue;
this.WordDirection = previous.WordDirection;
this.StartingPosition = new Tile(previous.StartingPosition.X, previous.StartingPosition.Y);
public int CompareTo(object obj)
if(obj == null) return 1;
CrossedWord otherCrossWord = obj as CrossedWord;
if(otherCrossWord != null)
return this.Size.CompareTo(otherCrossWord.Size);
throw new ArgumentException("Object is not a CrossedWord");
public char LetterOnTile(Tile t)
switch(this.WordDirection)
case Direction.Horizontal : return this.Word[t.X - this.StartingPosition.X];
case Direction.Vertical : return this.Word[t.Y - this.StartingPosition.Y];
public Tile TileAtWordPosition(int pos)
if(pos >= 0 && pos < this.Size)
switch(this.WordDirection)
case Direction.Horizontal : return new Tile(this.StartingPosition.X + pos, this.StartingPosition.Y);
case Direction.Vertical : return new Tile(this.StartingPosition.X, this.StartingPosition.Y + pos);
default : throw new MissingMemberException("This Word has no direction");
throw new ArgumentOutOfRangeException();
public bool isWordOverTile(Tile t)
return (this.WordDirection == Direction.Horizontal && t.Y == this.StartingPosition.Y && t.X >= this.StartingPosition.X && t.X < this.StartingPosition.X + this.Size)
|| (this.WordDirection == Direction.Vertical && t.X == this.StartingPosition.X && t.Y >= this.StartingPosition.Y && t.Y < this.StartingPosition.Y + this.Size) ;
public List<Tile>[] SimilarLetterTiles(CrossedWord c)
List<Tile>[] tilesForEachLetter = new List<Tile>[c.Size];
for(int i = 0; i< c.Size ; i++)
List<Tile> TilesForCurrentLetter = new List<Tile>();
for(int j = 0; j<this.Size; j++)
if(c.Word[i] == this.Word[j])
TilesForCurrentLetter.Add(this.TileAtWordPosition(j));
tilesForEachLetter[i] = TilesForCurrentLetter;
return tilesForEachLetter;
public int CanAccept(CrossedWord c)
if(this.WordDirection == Direction.Horizontal && c.WordDirection == Direction.Horizontal )
if( Math.Abs(c.StartingPosition.Y - this.StartingPosition.Y) > 1 )
if( Math.Abs(c.StartingPosition.Y - this.StartingPosition.Y) <= 1 && (this.StartingPosition.X > c.StartingPosition.X + c.Size || this.StartingPosition.X + this.Size < c.StartingPosition.X))
if(this.WordDirection == Direction.Vertical && c.WordDirection == Direction.Vertical )
if( Math.Abs(c.StartingPosition.X - this.StartingPosition.X) > 1 )
if ( Math.Abs(c.StartingPosition.X - this.StartingPosition.X) <= 1 && (this.StartingPosition.Y > c.StartingPosition.Y + c.Size || this.StartingPosition.Y + this.Size < c.StartingPosition.Y))
if(this.WordDirection == Direction.Horizontal && c.WordDirection == Direction.Vertical)
Tile potentialIntersection = new Tile(c.StartingPosition.X, this.StartingPosition.Y);
char instanceChar = this.LetterOnTile(potentialIntersection);
char otherChar = c.LetterOnTile(potentialIntersection);
if(this.isWordOverTile(potentialIntersection) && c.isWordOverTile(potentialIntersection) && instanceChar == otherChar)
else if(instanceChar == '0' && (potentialIntersection.X < this.StartingPosition.X - 1 || potentialIntersection.X > this.StartingPosition.X + this.Size))
if(this.WordDirection == Direction.Vertical && c.WordDirection == Direction.Horizontal)
Tile potentialIntersection = new Tile(this.StartingPosition.X, c.StartingPosition.Y);
char instanceChar = this.LetterOnTile(potentialIntersection);
char otherChar = c.LetterOnTile(potentialIntersection);
if(this.isWordOverTile(potentialIntersection) && c.isWordOverTile(potentialIntersection) && instanceChar == otherChar)
else if(instanceChar == '0' && (potentialIntersection.Y < this.StartingPosition.Y - 1 || potentialIntersection.Y > this.StartingPosition.Y + this.Size))