RE: [Flashcoders] Crossword generator advice

2009-06-02 Thread Paul Steven 
Sorry to drag this one out but I have one last question.

I implemented the recursive solution as Paul Andrews and Charles suggested
however I find that it can take up to 8 minutes to generate a solution
(which incidentally is pretty much the same amount of time my non recursive
implementation takes)

If I order my words from largest to smallest first this actually seems to
result in a longer time. I am thinking this is perhaps because one of the
longest words (tarragon) is at the bottom of the solution:
http://www.mediakitchen.co.uk/solution.gif

Anyway I do not mind it taking so long as a new crossword will only be
generated once a week. However I am curious as to whether this sounds like a
flaw in my code or if it is just the result of having to try so many
combinations to find the unique solution?

If I adjust my list of words into the order in which it looks like they
would be placed one at a time onto the grid, then the solution only takes
about 3 seconds to generate.

Because I know there is the possibility that having the list ordered in a
particular way can result in a super fast puzzle creation time, I am
wondering if it is worth just randomising the list every 10 seconds if a
solution has not been found?

Promise not to ask any more questions about this crossword generator after
this one:)

Thanks

Paul

-Original Message-
From: flashcoders-boun...@chattyfig.figleaf.com
[mailto:flashcoders-boun...@chattyfig.figleaf.com] On Behalf Of Paul Andrews
Sent: 01 June 2009 11:14
To: Flash Coders List
Subject: Re: [Flashcoders] Crossword generator advice

You should use recursion.

At each stage you should loop through the available words, trying to lay 
them onto the crossword area.

Paul

It goes a bit like this:

var wordList = [word1,word2,word3, ..   ];
var xwordSolution:XwordSolution;
var currentSolution= new XwordSolution(maxWidth, maxHeight); // emptyGrid

xwordSolution = layoutXword(wordList, currentSolution);

if (xwordSolution.isValid())
trace(Solved!)
else
trace(no solution found);

function layoutXword(words:Array, 
currentSolution:XwordSolution):XwordSolution
{
while (words.length  0){
currentWord = words.pop();

// horizontal

newSolution = layoutHorizontalWord(currentWord, currentSolution);
if (newSolution.isValid())
{
newSolution = layoutXword(words, newSolution );
if (newSolution.isValid())
return newSolution; // solved
}
// the horizontal layout wasn't possible, try vertical
newSolution = layoutVerticalWord(currentWord, currentSolution);
if (newSolution.isValid())
{
newSolution = layoutXword(words, newSolution );
if (newSolution.isValid())
return newSolution; // solved
}
// couldn't layout this word, try the next
}
// Couldn't layout any of the words - solution failed.
return newSolution; // this will be failed
}



















- Original Message - 
From: Paul Steven paul_ste...@btinternet.com
To: 'Flash Coders List' flashcoders@chattyfig.figleaf.com
Sent: Monday, June 01, 2009 10:33 AM
Subject: RE: [Flashcoders] Crossword generator advice


I am still struggling to find a solution to this crossword generator and
 could do with some advice on a possible solution I want to try.

 If I enter my list of 16 words in a particular order (an order based on 
 what
 looks like the order the solution would place them), the generator creates
 the puzzle in a matter of seconds.

 However if I enter them in a different order, the generator always breaks
 out of the loop by my exit condition (number of loops  5000). I am 
 assuming
 this is either due to an error in my code or due to the fact there are so
 many combinations to try.

 I am therefore thinking a possible solution is to try every permutation (I
 think this is the right word) of the 16 words. If I am correct there would
 be 240 possible permutations. ((X - 1) * X) where X is the number of items
 in the list.

 I am not sure however how to create the 240 variations of the list.

 Any advice on how to create these 240 permutations of the list would be 
 much
 appreciated.

 Thanks

 Paul

 ___
 Flashcoders mailing list
 Flashcoders@chattyfig.figleaf.com
 http://chattyfig.figleaf.com/mailman/listinfo/flashcoders 

___
Flashcoders mailing list
Flashcoders@chattyfig.figleaf.com
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders

___
Flashcoders mailing list
Flashcoders@chattyfig.figleaf.com
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders

RE: [Flashcoders] Crossword generator advice

2009-06-02 Thread Paul Steven 
Here is a link to the crossword generator in its current state.

http://www.mediakitchen.co.uk/crossword.html

Cheers

Paul

-Original Message-
From: flashcoders-boun...@chattyfig.figleaf.com
[mailto:flashcoders-boun...@chattyfig.figleaf.com] On Behalf Of Paul Steven
Sent: 02 June 2009 10:27
To: 'Flash Coders List'
Subject: RE: [Flashcoders] Crossword generator advice

Sorry to drag this one out but I have one last question.

I implemented the recursive solution as Paul Andrews and Charles suggested
however I find that it can take up to 8 minutes to generate a solution
(which incidentally is pretty much the same amount of time my non recursive
implementation takes)

If I order my words from largest to smallest first this actually seems to
result in a longer time. I am thinking this is perhaps because one of the
longest words (tarragon) is at the bottom of the solution:
http://www.mediakitchen.co.uk/solution.gif

Anyway I do not mind it taking so long as a new crossword will only be
generated once a week. However I am curious as to whether this sounds like a
flaw in my code or if it is just the result of having to try so many
combinations to find the unique solution?

If I adjust my list of words into the order in which it looks like they
would be placed one at a time onto the grid, then the solution only takes
about 3 seconds to generate.

Because I know there is the possibility that having the list ordered in a
particular way can result in a super fast puzzle creation time, I am
wondering if it is worth just randomising the list every 10 seconds if a
solution has not been found?

Promise not to ask any more questions about this crossword generator after
this one:)

Thanks

Paul

-Original Message-
From: flashcoders-boun...@chattyfig.figleaf.com
[mailto:flashcoders-boun...@chattyfig.figleaf.com] On Behalf Of Paul Andrews
Sent: 01 June 2009 11:14
To: Flash Coders List
Subject: Re: [Flashcoders] Crossword generator advice

You should use recursion.

At each stage you should loop through the available words, trying to lay 
them onto the crossword area.

Paul

It goes a bit like this:

var wordList = [word1,word2,word3, ..   ];
var xwordSolution:XwordSolution;
var currentSolution= new XwordSolution(maxWidth, maxHeight); // emptyGrid

xwordSolution = layoutXword(wordList, currentSolution);

if (xwordSolution.isValid())
trace(Solved!)
else
trace(no solution found);

function layoutXword(words:Array, 
currentSolution:XwordSolution):XwordSolution
{
while (words.length  0){
currentWord = words.pop();

// horizontal

newSolution = layoutHorizontalWord(currentWord, currentSolution);
if (newSolution.isValid())
{
newSolution = layoutXword(words, newSolution );
if (newSolution.isValid())
return newSolution; // solved
}
// the horizontal layout wasn't possible, try vertical
newSolution = layoutVerticalWord(currentWord, currentSolution);
if (newSolution.isValid())
{
newSolution = layoutXword(words, newSolution );
if (newSolution.isValid())
return newSolution; // solved
}
// couldn't layout this word, try the next
}
// Couldn't layout any of the words - solution failed.
return newSolution; // this will be failed
}



















- Original Message - 
From: Paul Steven paul_ste...@btinternet.com
To: 'Flash Coders List' flashcoders@chattyfig.figleaf.com
Sent: Monday, June 01, 2009 10:33 AM
Subject: RE: [Flashcoders] Crossword generator advice


I am still struggling to find a solution to this crossword generator and
 could do with some advice on a possible solution I want to try.

 If I enter my list of 16 words in a particular order (an order based on 
 what
 looks like the order the solution would place them), the generator creates
 the puzzle in a matter of seconds.

 However if I enter them in a different order, the generator always breaks
 out of the loop by my exit condition (number of loops  5000). I am 
 assuming
 this is either due to an error in my code or due to the fact there are so
 many combinations to try.

 I am therefore thinking a possible solution is to try every permutation (I
 think this is the right word) of the 16 words. If I am correct there would
 be 240 possible permutations. ((X - 1) * X) where X is the number of items
 in the list.

 I am not sure however how to create the 240 variations of the list.

 Any advice on how to create these 240 permutations of the list would be 
 much
 appreciated.

 Thanks

 Paul

 ___
 Flashcoders mailing list
 Flashcoders@chattyfig.figleaf.com
 http://chattyfig.figleaf.com/mailman/listinfo/flashcoders 

___
Flashcoders mailing list
Flashcoders@chattyfig.figleaf.com
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders

___
Flashcoders mailing list
Flashcoders@chattyfig.figleaf.com
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders

Re: [Flashcoders] Crossword generator advice

2009-06-02 Thread Paul Andrews 

Paul Steven wrote:

Here is a link to the crossword generator in its current state.

http://www.mediakitchen.co.uk/crossword.html

Cheers

Paul

-Original Message-
From: flashcoders-boun...@chattyfig.figleaf.com
[mailto:flashcoders-boun...@chattyfig.figleaf.com] On Behalf Of Paul Steven
Sent: 02 June 2009 10:27
To: 'Flash Coders List'
Subject: RE: [Flashcoders] Crossword generator advice

Sorry to drag this one out but I have one last question.

I implemented the recursive solution as Paul Andrews and Charles suggested
however I find that it can take up to 8 minutes to generate a solution
(which incidentally is pretty much the same amount of time my non recursive
implementation takes)
  
I think there's a problem in the algorithm again or you have a very 
inefficient placement checker.


A definite improvement to my suggestion would be to have a two stage 
placement algorithm - first of all only laying out words if they overlap 
another word, then if no solution is found by laying out the word as an 
overlap, it would then attempt a disconnected placement. I think that 
would improve things.


It's difficullt to know why it takes so long without seeing the code.

Paul



If I order my words from largest to smallest first this actually seems to
result in a longer time. I am thinking this is perhaps because one of the
longest words (tarragon) is at the bottom of the solution:
http://www.mediakitchen.co.uk/solution.gif

Anyway I do not mind it taking so long as a new crossword will only be
generated once a week. However I am curious as to whether this sounds like a
flaw in my code or if it is just the result of having to try so many
combinations to find the unique solution?

If I adjust my list of words into the order in which it looks like they
would be placed one at a time onto the grid, then the solution only takes
about 3 seconds to generate.

Because I know there is the possibility that having the list ordered in a
particular way can result in a super fast puzzle creation time, I am
wondering if it is worth just randomising the list every 10 seconds if a
solution has not been found?

Promise not to ask any more questions about this crossword generator after
this one:)

Thanks

Paul

-Original Message-
From: flashcoders-boun...@chattyfig.figleaf.com
[mailto:flashcoders-boun...@chattyfig.figleaf.com] On Behalf Of Paul Andrews
Sent: 01 June 2009 11:14
To: Flash Coders List
Subject: Re: [Flashcoders] Crossword generator advice

You should use recursion.

At each stage you should loop through the available words, trying to lay 
them onto the crossword area.


Paul

It goes a bit like this:

var wordList = [word1,word2,word3, ..   ];
var xwordSolution:XwordSolution;
var currentSolution= new XwordSolution(maxWidth, maxHeight); // emptyGrid

xwordSolution = layoutXword(wordList, currentSolution);

if (xwordSolution.isValid())
trace(Solved!)
else
trace(no solution found);

function layoutXword(words:Array, 
currentSolution:XwordSolution):XwordSolution

{
while (words.length  0){
currentWord = words.pop();

// horizontal

newSolution = layoutHorizontalWord(currentWord, currentSolution);
if (newSolution.isValid())
{
newSolution = layoutXword(words, newSolution );
if (newSolution.isValid())
return newSolution; // solved
}
// the horizontal layout wasn't possible, try vertical
newSolution = layoutVerticalWord(currentWord, currentSolution);
if (newSolution.isValid())
{
newSolution = layoutXword(words, newSolution );
if (newSolution.isValid())
return newSolution; // solved
}
// couldn't layout this word, try the next
}
// Couldn't layout any of the words - solution failed.
return newSolution; // this will be failed
}



















- Original Message - 
From: Paul Steven paul_ste...@btinternet.com

To: 'Flash Coders List' flashcoders@chattyfig.figleaf.com
Sent: Monday, June 01, 2009 10:33 AM
Subject: RE: [Flashcoders] Crossword generator advice


  

I am still struggling to find a solution to this crossword generator and
could do with some advice on a possible solution I want to try.

If I enter my list of 16 words in a particular order (an order based on 
what

looks like the order the solution would place them), the generator creates
the puzzle in a matter of seconds.

However if I enter them in a different order, the generator always breaks
out of the loop by my exit condition (number of loops  5000). I am 
assuming

this is either due to an error in my code or due to the fact there are so
many combinations to try.

I am therefore thinking a possible solution is to try every permutation (I
think this is the right word) of the 16 words. If I am correct there would
be 240 possible permutations. ((X - 1) * X) where X is the number of items
in the list.

I am not sure however how to create the 240 variations of the list.

Any advice on how to create these 240 permutations of the list would be 
much

appreciated.

Thanks

Paul

RE: [Flashcoders] Crossword generator advice

2009-06-02 Thread Paul Steven 
Thanks Paul for your reply.

You may be right about my placement checker. What I currently do is as
follows:

Starting with first char of word I want to place, loop through the
characters of each word that is already on the puzzle and see if a match can
be found. If a match is found then I calculate where the new word would
appear on the grid based on crossing the existing word where they characters
match. 

I then check if there are any words in the way or the new word goes off the
grid.
I also check that the new word is not adjacent to another word

My code does not allow words to be added unless they cross another word so
perhaps allowing disconnected placement would speed things up. I will give
it a try.

Thanks again for your help on this.

Paul





-Original Message-
From: flashcoders-boun...@chattyfig.figleaf.com
[mailto:flashcoders-boun...@chattyfig.figleaf.com] On Behalf Of Paul Andrews
Sent: 02 June 2009 11:54
To: Flash Coders List
Subject: Re: [Flashcoders] Crossword generator advice

Paul Steven wrote:
 Here is a link to the crossword generator in its current state.

 http://www.mediakitchen.co.uk/crossword.html

 Cheers

 Paul

 -Original Message-
 From: flashcoders-boun...@chattyfig.figleaf.com
 [mailto:flashcoders-boun...@chattyfig.figleaf.com] On Behalf Of Paul
Steven
 Sent: 02 June 2009 10:27
 To: 'Flash Coders List'
 Subject: RE: [Flashcoders] Crossword generator advice

 Sorry to drag this one out but I have one last question.

 I implemented the recursive solution as Paul Andrews and Charles suggested
 however I find that it can take up to 8 minutes to generate a solution
 (which incidentally is pretty much the same amount of time my non
recursive
 implementation takes)
   
I think there's a problem in the algorithm again or you have a very 
inefficient placement checker.

A definite improvement to my suggestion would be to have a two stage 
placement algorithm - first of all only laying out words if they overlap 
another word, then if no solution is found by laying out the word as an 
overlap, it would then attempt a disconnected placement. I think that 
would improve things.

It's difficullt to know why it takes so long without seeing the code.

Paul


 If I order my words from largest to smallest first this actually seems to
 result in a longer time. I am thinking this is perhaps because one of the
 longest words (tarragon) is at the bottom of the solution:
 http://www.mediakitchen.co.uk/solution.gif

 Anyway I do not mind it taking so long as a new crossword will only be
 generated once a week. However I am curious as to whether this sounds like
a
 flaw in my code or if it is just the result of having to try so many
 combinations to find the unique solution?

 If I adjust my list of words into the order in which it looks like they
 would be placed one at a time onto the grid, then the solution only takes
 about 3 seconds to generate.

 Because I know there is the possibility that having the list ordered in a
 particular way can result in a super fast puzzle creation time, I am
 wondering if it is worth just randomising the list every 10 seconds if a
 solution has not been found?

 Promise not to ask any more questions about this crossword generator after
 this one:)

 Thanks

 Paul

 -Original Message-
 From: flashcoders-boun...@chattyfig.figleaf.com
 [mailto:flashcoders-boun...@chattyfig.figleaf.com] On Behalf Of Paul
Andrews
 Sent: 01 June 2009 11:14
 To: Flash Coders List
 Subject: Re: [Flashcoders] Crossword generator advice

 You should use recursion.

 At each stage you should loop through the available words, trying to lay 
 them onto the crossword area.

 Paul

 It goes a bit like this:

 var wordList = [word1,word2,word3, ..   ];
 var xwordSolution:XwordSolution;
 var currentSolution= new XwordSolution(maxWidth, maxHeight); // emptyGrid

 xwordSolution = layoutXword(wordList, currentSolution);

 if (xwordSolution.isValid())
 trace(Solved!)
 else
 trace(no solution found);

 function layoutXword(words:Array, 
 currentSolution:XwordSolution):XwordSolution
 {
 while (words.length  0){
 currentWord = words.pop();

 // horizontal

 newSolution = layoutHorizontalWord(currentWord, currentSolution);
 if (newSolution.isValid())
 {
 newSolution = layoutXword(words, newSolution );
 if (newSolution.isValid())
 return newSolution; // solved
 }
 // the horizontal layout wasn't possible, try vertical
 newSolution = layoutVerticalWord(currentWord, currentSolution);
 if (newSolution.isValid())
 {
 newSolution = layoutXword(words, newSolution );
 if (newSolution.isValid())
 return newSolution; // solved
 }
 // couldn't layout this word, try the next
 }
 // Couldn't layout any of the words - solution failed.
 return newSolution; // this will be failed
 }



















 - Original Message - 
 From: Paul Steven paul_ste...@btinternet.com
 To: 'Flash Coders List' flashcoders@chattyfig.figleaf.com
 Sent: Monday, June 01, 2009

Re: [Flashcoders] Crossword generator advice

2009-06-02 Thread Paul Andrews 

Off the top of my head..

For a horizontal overlap of a word, the new word can only be placed in a 
very few places - no further left than the leftmost position of the 
wordlaready placed and no further right than the new word can be placed 
without going off the grid, or not overlapping the rightmost position of 
the placed word. Similarly for vertical positions. This drastically 
reduces your placement options.


for a connected only crossword, the overlap must be as above and for 
every placed word where an overlap occurs, characters must match with 
the new word where they overlap.


Essentially we have:

For each already placed word
   if new word can overlap
try placement for valid positions of new world
for each placement compare overlap charaters for equality.

Maybe this should now be off-list - it has nothing to do with flash!

Paul




Paul Steven wrote:

Thanks Paul for your reply.

You may be right about my placement checker. What I currently do is as
follows:

Starting with first char of word I want to place, loop through the
characters of each word that is already on the puzzle and see if a match can
be found. If a match is found then I calculate where the new word would
appear on the grid based on crossing the existing word where they characters
match. 


I then check if there are any words in the way or the new word goes off the
grid.
I also check that the new word is not adjacent to another word

My code does not allow words to be added unless they cross another word so
perhaps allowing disconnected placement would speed things up. I will give
it a try.

Thanks again for your help on this.

Paul
  

___
Flashcoders mailing list
Flashcoders@chattyfig.figleaf.com
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders

Re: [Flashcoders] Crossword generator advice

2009-06-02 Thread Karl DeSaulniers 
You may want to also set something to read how many of those letters  
are in the word that match the letter your using in the one your  
placing.

This may give you a few more options on placement.

Karl

On Jun 2, 2009, at 6:34 AM, Paul Andrews wrote:


Off the top of my head..

For a horizontal overlap of a word, the new word can only be placed  
in a very few places - no further left than the leftmost position  
of the wordlaready placed and no further right than the new word  
can be placed without going off the grid, or not overlapping the  
rightmost position of the placed word. Similarly for vertical  
positions. This drastically reduces your placement options.


for a connected only crossword, the overlap must be as above and  
for every placed word where an overlap occurs, characters must  
match with the new word where they overlap.


Essentially we have:

For each already placed word
   if new word can overlap
try placement for valid positions of new world
for each placement compare overlap charaters for equality.

Maybe this should now be off-list - it has nothing to do with flash!

Paul




Paul Steven wrote:

Thanks Paul for your reply.

You may be right about my placement checker. What I currently do  
is as

follows:

Starting with first char of word I want to place, loop through the
characters of each word that is already on the puzzle and see if a  
match can
be found. If a match is found then I calculate where the new word  
would
appear on the grid based on crossing the existing word where they  
characters

match.
I then check if there are any words in the way or the new word  
goes off the

grid.
I also check that the new word is not adjacent to another word

My code does not allow words to be added unless they cross another  
word so
perhaps allowing disconnected placement would speed things up. I  
will give

it a try.

Thanks again for your help on this.

Paul


___
Flashcoders mailing list
Flashcoders@chattyfig.figleaf.com
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders


Karl DeSaulniers
Design Drumm
http://designdrumm.com

___
Flashcoders mailing list
Flashcoders@chattyfig.figleaf.com
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders

RE: [Flashcoders] Crossword generator advice

2009-06-01 Thread Paul Steven 
I am still struggling to find a solution to this crossword generator and
could do with some advice on a possible solution I want to try.

If I enter my list of 16 words in a particular order (an order based on what
looks like the order the solution would place them), the generator creates
the puzzle in a matter of seconds.

However if I enter them in a different order, the generator always breaks
out of the loop by my exit condition (number of loops  5000). I am assuming
this is either due to an error in my code or due to the fact there are so
many combinations to try. 

I am therefore thinking a possible solution is to try every permutation (I
think this is the right word) of the 16 words. If I am correct there would
be 240 possible permutations. ((X - 1) * X) where X is the number of items
in the list.

I am not sure however how to create the 240 variations of the list.

Any advice on how to create these 240 permutations of the list would be much
appreciated.

Thanks

Paul

___
Flashcoders mailing list
Flashcoders@chattyfig.figleaf.com
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders

Re: [Flashcoders] Crossword generator advice

2009-06-01 Thread Paul Andrews 

You should use recursion.

At each stage you should loop through the available words, trying to lay 
them onto the crossword area.


Paul

It goes a bit like this:

var wordList = [word1,word2,word3, ..   ];
var xwordSolution:XwordSolution;
var currentSolution= new XwordSolution(maxWidth, maxHeight); // emptyGrid

xwordSolution = layoutXword(wordList, currentSolution);

if (xwordSolution.isValid())
trace(Solved!)
else
trace(no solution found);

function layoutXword(words:Array, 
currentSolution:XwordSolution):XwordSolution

{
while (words.length  0){
currentWord = words.pop();

// horizontal

newSolution = layoutHorizontalWord(currentWord, currentSolution);
if (newSolution.isValid())
{
   newSolution = layoutXword(words, newSolution );
   if (newSolution.isValid())
   return newSolution; // solved
}
// the horizontal layout wasn't possible, try vertical
newSolution = layoutVerticalWord(currentWord, currentSolution);
if (newSolution.isValid())
{
   newSolution = layoutXword(words, newSolution );
   if (newSolution.isValid())
   return newSolution; // solved
}
// couldn't layout this word, try the next
}
// Couldn't layout any of the words - solution failed.
return newSolution; // this will be failed
}



















- Original Message - 
From: Paul Steven paul_ste...@btinternet.com

To: 'Flash Coders List' flashcoders@chattyfig.figleaf.com
Sent: Monday, June 01, 2009 10:33 AM
Subject: RE: [Flashcoders] Crossword generator advice



I am still struggling to find a solution to this crossword generator and
could do with some advice on a possible solution I want to try.

If I enter my list of 16 words in a particular order (an order based on 
what

looks like the order the solution would place them), the generator creates
the puzzle in a matter of seconds.

However if I enter them in a different order, the generator always breaks
out of the loop by my exit condition (number of loops  5000). I am 
assuming

this is either due to an error in my code or due to the fact there are so
many combinations to try.

I am therefore thinking a possible solution is to try every permutation (I
think this is the right word) of the 16 words. If I am correct there would
be 240 possible permutations. ((X - 1) * X) where X is the number of items
in the list.

I am not sure however how to create the 240 variations of the list.

Any advice on how to create these 240 permutations of the list would be 
much

appreciated.

Thanks

Paul

___
Flashcoders mailing list
Flashcoders@chattyfig.figleaf.com
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders 


___
Flashcoders mailing list
Flashcoders@chattyfig.figleaf.com
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders

Re: [Flashcoders] Crossword generator advice

2009-06-01 Thread Paul Andrews 
I've realised that there needs to be further loops around the layout code. 
For the crossword grid a viable set of horizontal  layout positions may 
start at a given (x,y) position and the solution should search in terms of 
increasing x, then y, so the code might then go something like this..


layoutFrom=Point(0,0); // top left

while  (layoutFrom!=null)
{
   newSolution = layoutHorizontalWord(layFrom, currentWord, 
currentSolution);

   if (newSolution.isValid())
   {
   newSolution = layoutXword(words, newSolution );
   if (newSolution.isValid())
   return newSolution; // solved
}
   layoutFrom= newSolution.getNextPosition(); // returns the next x,y 
position after the last position used, or null if none left.

}

Paul





- Original Message - 
From: Paul Andrews p...@ipauland.com

To: Flash Coders List flashcoders@chattyfig.figleaf.com
Sent: Monday, June 01, 2009 11:14 AM
Subject: Re: [Flashcoders] Crossword generator advice



You should use recursion.

At each stage you should loop through the available words, trying to lay 
them onto the crossword area.


Paul

It goes a bit like this:

var wordList = [word1,word2,word3, ..   ];
var xwordSolution:XwordSolution;
var currentSolution= new XwordSolution(maxWidth, maxHeight); // emptyGrid

xwordSolution = layoutXword(wordList, currentSolution);

if (xwordSolution.isValid())
trace(Solved!)
else
trace(no solution found);

function layoutXword(words:Array, 
currentSolution:XwordSolution):XwordSolution

{
while (words.length  0){
currentWord = words.pop();

// horizontal

newSolution = layoutHorizontalWord(currentWord, currentSolution);
if (newSolution.isValid())
{
   newSolution = layoutXword(words, newSolution );
   if (newSolution.isValid())
   return newSolution; // solved
}
// the horizontal layout wasn't possible, try vertical
newSolution = layoutVerticalWord(currentWord, currentSolution);
if (newSolution.isValid())
{
   newSolution = layoutXword(words, newSolution );
   if (newSolution.isValid())
   return newSolution; // solved
}
// couldn't layout this word, try the next
}
// Couldn't layout any of the words - solution failed.
return newSolution; // this will be failed
}



















- Original Message - 
From: Paul Steven paul_ste...@btinternet.com

To: 'Flash Coders List' flashcoders@chattyfig.figleaf.com
Sent: Monday, June 01, 2009 10:33 AM
Subject: RE: [Flashcoders] Crossword generator advice



I am still struggling to find a solution to this crossword generator and
could do with some advice on a possible solution I want to try.

If I enter my list of 16 words in a particular order (an order based on 
what
looks like the order the solution would place them), the generator 
creates

the puzzle in a matter of seconds.

However if I enter them in a different order, the generator always breaks
out of the loop by my exit condition (number of loops  5000). I am 
assuming

this is either due to an error in my code or due to the fact there are so
many combinations to try.

I am therefore thinking a possible solution is to try every permutation 
(I
think this is the right word) of the 16 words. If I am correct there 
would
be 240 possible permutations. ((X - 1) * X) where X is the number of 
items

in the list.

I am not sure however how to create the 240 variations of the list.

Any advice on how to create these 240 permutations of the list would be 
much

appreciated.

Thanks

Paul

___
Flashcoders mailing list
Flashcoders@chattyfig.figleaf.com
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders


___
Flashcoders mailing list
Flashcoders@chattyfig.figleaf.com
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders 


___
Flashcoders mailing list
Flashcoders@chattyfig.figleaf.com
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders

Re: [Flashcoders] Crossword generator advice

2009-06-01 Thread Charles Parcell 
As Paul has stated, recursion is the answer to building this generator
correctly.

But just as a sanity check, have you traced out the combinations that your
currect generator is attempting? That may put some light on where it was
breaking. If for nothing else, it will help you understand where the logic
broke down. Learning from our mistakes is always helpful.

Charles P.



On Mon, Jun 1, 2009 at 6:59 AM, Paul Andrews p...@ipauland.com wrote:

 I've realised that there needs to be further loops around the layout code.
 For the crossword grid a viable set of horizontal  layout positions may
 start at a given (x,y) position and the solution should search in terms of
 increasing x, then y, so the code might then go something like this..

 layoutFrom=Point(0,0); // top left

 while  (layoutFrom!=null)
 {
   newSolution = layoutHorizontalWord(layFrom, currentWord,
 currentSolution);
   if (newSolution.isValid())
   {
   newSolution = layoutXword(words, newSolution );
   if (newSolution.isValid())
   return newSolution; // solved
}
   layoutFrom= newSolution.getNextPosition(); // returns the next x,y
 position after the last position used, or null if none left.
 }

 Paul





 - Original Message - From: Paul Andrews p...@ipauland.com
 To: Flash Coders List flashcoders@chattyfig.figleaf.com
 Sent: Monday, June 01, 2009 11:14 AM
 Subject: Re: [Flashcoders] Crossword generator advice


  You should use recursion.

 At each stage you should loop through the available words, trying to lay
 them onto the crossword area.

 Paul

 It goes a bit like this:

 var wordList = [word1,word2,word3, ..   ];
 var xwordSolution:XwordSolution;
 var currentSolution= new XwordSolution(maxWidth, maxHeight); // emptyGrid

 xwordSolution = layoutXword(wordList, currentSolution);

 if (xwordSolution.isValid())
 trace(Solved!)
 else
 trace(no solution found);

 function layoutXword(words:Array,
 currentSolution:XwordSolution):XwordSolution
 {
 while (words.length  0){
 currentWord = words.pop();

 // horizontal

 newSolution = layoutHorizontalWord(currentWord, currentSolution);
 if (newSolution.isValid())
 {
   newSolution = layoutXword(words, newSolution );
   if (newSolution.isValid())
   return newSolution; // solved
 }
 // the horizontal layout wasn't possible, try vertical
 newSolution = layoutVerticalWord(currentWord, currentSolution);
 if (newSolution.isValid())
 {
   newSolution = layoutXword(words, newSolution );
   if (newSolution.isValid())
   return newSolution; // solved
 }
 // couldn't layout this word, try the next
 }
 // Couldn't layout any of the words - solution failed.
 return newSolution; // this will be failed
 }



















 - Original Message - From: Paul Steven 
 paul_ste...@btinternet.com
 To: 'Flash Coders List' flashcoders@chattyfig.figleaf.com
 Sent: Monday, June 01, 2009 10:33 AM
 Subject: RE: [Flashcoders] Crossword generator advice


  I am still struggling to find a solution to this crossword generator and
 could do with some advice on a possible solution I want to try.

 If I enter my list of 16 words in a particular order (an order based on
 what
 looks like the order the solution would place them), the generator
 creates
 the puzzle in a matter of seconds.

 However if I enter them in a different order, the generator always breaks
 out of the loop by my exit condition (number of loops  5000). I am
 assuming
 this is either due to an error in my code or due to the fact there are so
 many combinations to try.

 I am therefore thinking a possible solution is to try every permutation
 (I
 think this is the right word) of the 16 words. If I am correct there
 would
 be 240 possible permutations. ((X - 1) * X) where X is the number of
 items
 in the list.

 I am not sure however how to create the 240 variations of the list.

 Any advice on how to create these 240 permutations of the list would be
 much
 appreciated.

 Thanks

 Paul

 ___
 Flashcoders mailing list
 Flashcoders@chattyfig.figleaf.com
 http://chattyfig.figleaf.com/mailman/listinfo/flashcoders


 ___
 Flashcoders mailing list
 Flashcoders@chattyfig.figleaf.com
 http://chattyfig.figleaf.com/mailman/listinfo/flashcoders


 ___
 Flashcoders mailing list
 Flashcoders@chattyfig.figleaf.com
 http://chattyfig.figleaf.com/mailman/listinfo/flashcoders

___
Flashcoders mailing list
Flashcoders@chattyfig.figleaf.com
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders

RE: [Flashcoders] Crossword generator advice

2009-06-01 Thread Paul Steven 
Thanks for all the new advice. Yes I figured a recursive solution was
required and even though my code doesn't technically recurse, it more or
less does the same thing.

Anyway I have just figured out the problem with my code after painstakingly
tracing variables for the last few days.

I was not accounting for the fact a word can be placed either across or
down in my backtracking code. So words were being crossed off the list
without giving them a second chance at having a stab at trying all
combinations that occurred from placing it in the alternative orientation
(assuming this was a valid positioning).

I am extremely pleased to have cracked this and will celebrate with a cold
beer in the garden. I will also come back and look implementing a recursive
solution - thought the word recursion hurts my head:)

Cheers

Paul

Thanks again to Paul and Charles for their help in my times of need.

___
Flashcoders mailing list
Flashcoders@chattyfig.figleaf.com
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders

RE: [Flashcoders] Crossword generator advice

2009-05-31 Thread Paul Steven 
Just to add more information to how I am currently trying to achieve this.

I basically start with the first word in the list and place it in the top
left position 0,0. I then attempt to add the next word in the list by
finding a character in the first word that is the same as one of the
characters in this new word. If it fails to add this next word, it puts this
word to the back of the list and tries the next word. If at any point, it is
no longer able to add one of the remaining unplaced words, it back tracks
and changes the previously added word to a different one. So in theory it
should attempt to find a solution by trying every single word in the top
left 0,0 position, then attempting to add the others where they can fit. The
complete crossword solution has the word Quantity in the top left going
across so in theory a solution should be possible with this word at this
position and this orientation.

Hopefully someone can shed some light on a solution.

Many thanks

Paul

-Original Message-
From: flashcoders-boun...@chattyfig.figleaf.com
[mailto:flashcoders-boun...@chattyfig.figleaf.com] On Behalf Of Paul Steven
Sent: 31 May 2009 10:02
To: 'Flash Coders List'
Subject: [Flashcoders] Crossword generator advice

I am creating a crossword generator where you can enter the size of the grid
and a list of words but for the life of me cannot get it to generate a
puzzle with all the words in my list. This list of words is from a crossword
that I know is possible. Now either my generator is not up to scratch or the
process of creating a crossword is very complex and will require so many
iterations that it would take a long time to work out a solution.

Here is the list of words I am trying to generate the crossword with. The
size of the grid is 9 x 9. I have tried several online crossword generators
and none of them are able to generate a puzzle of this size with these
words. The most words I have been able to generate a puzzle with is 11
words. However I know for a fact it is possible as I have an actual
crossword with these 16 words. I would therefore appreciate any advice.
Perhaps someone has a crossword generator they can try these 16 words in?

quantity
alb
iliad
epee
jinx
glass
inn
tarragon
quake
amble
twin
yearn
pilot
icing
xenon
user

Thanks in advance

Paul

___
Flashcoders mailing list
Flashcoders@chattyfig.figleaf.com
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders

___
Flashcoders mailing list
Flashcoders@chattyfig.figleaf.com
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders

RE: [Flashcoders] Crossword generator advice

2009-05-31 Thread Paul Steven 
Further to my last post, here is a link to the solution to the crossword 

http://www.mediakitchen.co.uk/solution.gif

Before anyone asks, I have tried the crossword generator in the Advanced
Lingo for Games book and unfortunately it is unable to create a puzzle with
these 16 words.

quantity
alb
iliad
epee
jinx
glass
inn
tarragon
quake
amble
twin
yearn
pilot
icing
xenon
user

Looking forward to hearing if anyone is able to generate a 9x9 puzzle with
these words.

Thanks

Paul



-Original Message-
From: flashcoders-boun...@chattyfig.figleaf.com
[mailto:flashcoders-boun...@chattyfig.figleaf.com] On Behalf Of Paul Steven
Sent: 31 May 2009 10:10
To: 'Flash Coders List'
Subject: RE: [Flashcoders] Crossword generator advice

Just to add more information to how I am currently trying to achieve this.

I basically start with the first word in the list and place it in the top
left position 0,0. I then attempt to add the next word in the list by
finding a character in the first word that is the same as one of the
characters in this new word. If it fails to add this next word, it puts this
word to the back of the list and tries the next word. If at any point, it is
no longer able to add one of the remaining unplaced words, it back tracks
and changes the previously added word to a different one. So in theory it
should attempt to find a solution by trying every single word in the top
left 0,0 position, then attempting to add the others where they can fit. The
complete crossword solution has the word Quantity in the top left going
across so in theory a solution should be possible with this word at this
position and this orientation.

Hopefully someone can shed some light on a solution.

Many thanks

Paul

-Original Message-
From: flashcoders-boun...@chattyfig.figleaf.com
[mailto:flashcoders-boun...@chattyfig.figleaf.com] On Behalf Of Paul Steven
Sent: 31 May 2009 10:02
To: 'Flash Coders List'
Subject: [Flashcoders] Crossword generator advice

I am creating a crossword generator where you can enter the size of the grid
and a list of words but for the life of me cannot get it to generate a
puzzle with all the words in my list. This list of words is from a crossword
that I know is possible. Now either my generator is not up to scratch or the
process of creating a crossword is very complex and will require so many
iterations that it would take a long time to work out a solution.

Here is the list of words I am trying to generate the crossword with. The
size of the grid is 9 x 9. I have tried several online crossword generators
and none of them are able to generate a puzzle of this size with these
words. The most words I have been able to generate a puzzle with is 11
words. However I know for a fact it is possible as I have an actual
crossword with these 16 words. I would therefore appreciate any advice.
Perhaps someone has a crossword generator they can try these 16 words in?

quantity
alb
iliad
epee
jinx
glass
inn
tarragon
quake
amble
twin
yearn
pilot
icing
xenon
user

Thanks in advance

Paul

___
Flashcoders mailing list
Flashcoders@chattyfig.figleaf.com
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders

___
Flashcoders mailing list
Flashcoders@chattyfig.figleaf.com
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders

___
Flashcoders mailing list
Flashcoders@chattyfig.figleaf.com
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders

Re: [Flashcoders] Crossword generator advice

2009-05-31 Thread Paul Andrews 

There is a flaw in your logic.

It may be that multiple words fit a given situation, and  so it's necessary 
(with such a simple algorithm) to backtrack and look for another word to fit 
once you are unable to fit another word from your list - so the real problem 
is saving where you are in the list of possible combinations as you go 
along.


For example, in quantity there are two t s, so there are two possibilities 
for fitting a word. You may go with tarragon for the first t but in 
practice it may only be possible to have a solution with tarragon as the 
second t. You must be able to backtrack your choice of tarragon as a 
solution for the first t and go with twin instead. You must be able to 
do this at every stage. Once you can your software should work.


Paul


- Original Message - 
From: Paul Steven paul_ste...@btinternet.com

To: 'Flash Coders List' flashcoders@chattyfig.figleaf.com
Sent: Sunday, May 31, 2009 10:09 AM
Subject: RE: [Flashcoders] Crossword generator advice



Just to add more information to how I am currently trying to achieve this.

I basically start with the first word in the list and place it in the top
left position 0,0. I then attempt to add the next word in the list by
finding a character in the first word that is the same as one of the
characters in this new word. If it fails to add this next word, it puts 
this
word to the back of the list and tries the next word. If at any point, it 
is

no longer able to add one of the remaining unplaced words, it back tracks
and changes the previously added word to a different one. So in theory it
should attempt to find a solution by trying every single word in the top
left 0,0 position, then attempting to add the others where they can fit. 
The

complete crossword solution has the word Quantity in the top left going
across so in theory a solution should be possible with this word at this
position and this orientation.

Hopefully someone can shed some light on a solution.

Many thanks

Paul

-Original Message-
From: flashcoders-boun...@chattyfig.figleaf.com
[mailto:flashcoders-boun...@chattyfig.figleaf.com] On Behalf Of Paul 
Steven

Sent: 31 May 2009 10:02
To: 'Flash Coders List'
Subject: [Flashcoders] Crossword generator advice

I am creating a crossword generator where you can enter the size of the 
grid

and a list of words but for the life of me cannot get it to generate a
puzzle with all the words in my list. This list of words is from a 
crossword
that I know is possible. Now either my generator is not up to scratch or 
the

process of creating a crossword is very complex and will require so many
iterations that it would take a long time to work out a solution.

Here is the list of words I am trying to generate the crossword with. The
size of the grid is 9 x 9. I have tried several online crossword 
generators

and none of them are able to generate a puzzle of this size with these
words. The most words I have been able to generate a puzzle with is 11
words. However I know for a fact it is possible as I have an actual
crossword with these 16 words. I would therefore appreciate any advice.
Perhaps someone has a crossword generator they can try these 16 words in?

quantity
alb
iliad
epee
jinx
glass
inn
tarragon
quake
amble
twin
yearn
pilot
icing
xenon
user

Thanks in advance

Paul

___
Flashcoders mailing list
Flashcoders@chattyfig.figleaf.com
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders

___
Flashcoders mailing list
Flashcoders@chattyfig.figleaf.com
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders 


___
Flashcoders mailing list
Flashcoders@chattyfig.figleaf.com
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders

RE: [Flashcoders] Crossword generator advice

2009-05-31 Thread Paul Steven 
Thanks Paul

My code should backtrack in the situation you mention. So for example if it
fits tarragon on the first t but then continues to not be able to find a
solution with tarragon in this position, it will backtrack so that it
changes tarragon to the second t. However I still can't find a solution
with 16 words. There may be some other flaws in my logic preventing this. I
was wondering if in order to find a solution it will take thousands of
attempts to find a solution? I have a counter that when reaches 5000, it
breaks out of the loop trying to find the solution so I am effectively
trying 5000 combinations - perhaps there is an equation to calculate how
many combinations there are?

I would be interested if anyone else can solve this puzzle with an
alternative crossword generator?

Thanks

Paul

-Original Message-
From: flashcoders-boun...@chattyfig.figleaf.com
[mailto:flashcoders-boun...@chattyfig.figleaf.com] On Behalf Of Paul Andrews
Sent: 31 May 2009 12:07
To: Flash Coders List
Subject: Re: [Flashcoders] Crossword generator advice

There is a flaw in your logic.

It may be that multiple words fit a given situation, and  so it's necessary 
(with such a simple algorithm) to backtrack and look for another word to fit

once you are unable to fit another word from your list - so the real problem

is saving where you are in the list of possible combinations as you go 
along.

For example, in quantity there are two t s, so there are two possibilities

for fitting a word. You may go with tarragon for the first t but in 
practice it may only be possible to have a solution with tarragon as the 
second t. You must be able to backtrack your choice of tarragon as a 
solution for the first t and go with twin instead. You must be able to 
do this at every stage. Once you can your software should work.

Paul


- Original Message - 
From: Paul Steven paul_ste...@btinternet.com
To: 'Flash Coders List' flashcoders@chattyfig.figleaf.com
Sent: Sunday, May 31, 2009 10:09 AM
Subject: RE: [Flashcoders] Crossword generator advice


 Just to add more information to how I am currently trying to achieve this.

 I basically start with the first word in the list and place it in the top
 left position 0,0. I then attempt to add the next word in the list by
 finding a character in the first word that is the same as one of the
 characters in this new word. If it fails to add this next word, it puts 
 this
 word to the back of the list and tries the next word. If at any point, it 
 is
 no longer able to add one of the remaining unplaced words, it back tracks
 and changes the previously added word to a different one. So in theory it
 should attempt to find a solution by trying every single word in the top
 left 0,0 position, then attempting to add the others where they can fit. 
 The
 complete crossword solution has the word Quantity in the top left going
 across so in theory a solution should be possible with this word at this
 position and this orientation.

 Hopefully someone can shed some light on a solution.

 Many thanks

 Paul

 -Original Message-
 From: flashcoders-boun...@chattyfig.figleaf.com
 [mailto:flashcoders-boun...@chattyfig.figleaf.com] On Behalf Of Paul 
 Steven
 Sent: 31 May 2009 10:02
 To: 'Flash Coders List'
 Subject: [Flashcoders] Crossword generator advice

 I am creating a crossword generator where you can enter the size of the 
 grid
 and a list of words but for the life of me cannot get it to generate a
 puzzle with all the words in my list. This list of words is from a 
 crossword
 that I know is possible. Now either my generator is not up to scratch or 
 the
 process of creating a crossword is very complex and will require so many
 iterations that it would take a long time to work out a solution.

 Here is the list of words I am trying to generate the crossword with. The
 size of the grid is 9 x 9. I have tried several online crossword 
 generators
 and none of them are able to generate a puzzle of this size with these
 words. The most words I have been able to generate a puzzle with is 11
 words. However I know for a fact it is possible as I have an actual
 crossword with these 16 words. I would therefore appreciate any advice.
 Perhaps someone has a crossword generator they can try these 16 words in?

 quantity
 alb
 iliad
 epee
 jinx
 glass
 inn
 tarragon
 quake
 amble
 twin
 yearn
 pilot
 icing
 xenon
 user

 Thanks in advance

 Paul

 ___
 Flashcoders mailing list
 Flashcoders@chattyfig.figleaf.com
 http://chattyfig.figleaf.com/mailman/listinfo/flashcoders

 ___
 Flashcoders mailing list
 Flashcoders@chattyfig.figleaf.com
 http://chattyfig.figleaf.com/mailman/listinfo/flashcoders 

___
Flashcoders mailing list
Flashcoders@chattyfig.figleaf.com
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders

Re: [Flashcoders] Crossword generator advice

2009-05-31 Thread Paul Andrews 

I suspect that the algorithm is wrong.

For example quantity top left, alb will only fit quantity in one place and 
there is only one other a candidate amble. Very quickly your choices 
will be reduced due to placement, so 5,000 attempts seems excessive.


Sadly I have a ton of other things to do or I'd have a go myself.

Paul
- Original Message - 
From: Paul Steven paul_ste...@btinternet.com

To: 'Flash Coders List' flashcoders@chattyfig.figleaf.com
Sent: Sunday, May 31, 2009 12:17 PM
Subject: RE: [Flashcoders] Crossword generator advice



Thanks Paul

My code should backtrack in the situation you mention. So for example if 
it

fits tarragon on the first t but then continues to not be able to find a
solution with tarragon in this position, it will backtrack so that it
changes tarragon to the second t. However I still can't find a 
solution
with 16 words. There may be some other flaws in my logic preventing this. 
I

was wondering if in order to find a solution it will take thousands of
attempts to find a solution? I have a counter that when reaches 5000, it
breaks out of the loop trying to find the solution so I am effectively
trying 5000 combinations - perhaps there is an equation to calculate how
many combinations there are?

I would be interested if anyone else can solve this puzzle with an
alternative crossword generator?

Thanks

Paul

-Original Message-
From: flashcoders-boun...@chattyfig.figleaf.com
[mailto:flashcoders-boun...@chattyfig.figleaf.com] On Behalf Of Paul 
Andrews

Sent: 31 May 2009 12:07
To: Flash Coders List
Subject: Re: [Flashcoders] Crossword generator advice

There is a flaw in your logic.

It may be that multiple words fit a given situation, and  so it's 
necessary
(with such a simple algorithm) to backtrack and look for another word to 
fit


once you are unable to fit another word from your list - so the real 
problem


is saving where you are in the list of possible combinations as you go
along.

For example, in quantity there are two t s, so there are two 
possibilities


for fitting a word. You may go with tarragon for the first t but in
practice it may only be possible to have a solution with tarragon as the
second t. You must be able to backtrack your choice of tarragon as a
solution for the first t and go with twin instead. You must be able to
do this at every stage. Once you can your software should work.

Paul


- Original Message - 
From: Paul Steven paul_ste...@btinternet.com

To: 'Flash Coders List' flashcoders@chattyfig.figleaf.com
Sent: Sunday, May 31, 2009 10:09 AM
Subject: RE: [Flashcoders] Crossword generator advice


Just to add more information to how I am currently trying to achieve 
this.


I basically start with the first word in the list and place it in the top
left position 0,0. I then attempt to add the next word in the list by
finding a character in the first word that is the same as one of the
characters in this new word. If it fails to add this next word, it puts
this
word to the back of the list and tries the next word. If at any point, it
is
no longer able to add one of the remaining unplaced words, it back tracks
and changes the previously added word to a different one. So in theory it
should attempt to find a solution by trying every single word in the top
left 0,0 position, then attempting to add the others where they can fit.
The
complete crossword solution has the word Quantity in the top left going
across so in theory a solution should be possible with this word at this
position and this orientation.

Hopefully someone can shed some light on a solution.

Many thanks

Paul

-Original Message-
From: flashcoders-boun...@chattyfig.figleaf.com
[mailto:flashcoders-boun...@chattyfig.figleaf.com] On Behalf Of Paul
Steven
Sent: 31 May 2009 10:02
To: 'Flash Coders List'
Subject: [Flashcoders] Crossword generator advice

I am creating a crossword generator where you can enter the size of the
grid
and a list of words but for the life of me cannot get it to generate a
puzzle with all the words in my list. This list of words is from a
crossword
that I know is possible. Now either my generator is not up to scratch or
the
process of creating a crossword is very complex and will require so many
iterations that it would take a long time to work out a solution.

Here is the list of words I am trying to generate the crossword with. The
size of the grid is 9 x 9. I have tried several online crossword
generators
and none of them are able to generate a puzzle of this size with these
words. The most words I have been able to generate a puzzle with is 11
words. However I know for a fact it is possible as I have an actual
crossword with these 16 words. I would therefore appreciate any advice.
Perhaps someone has a crossword generator they can try these 16 words in?

quantity
alb
iliad
epee
jinx
glass
inn
tarragon
quake
amble
twin
yearn
pilot
icing
xenon
user

Thanks in advance

Paul

Re: [Flashcoders] Crossword generator advice

2009-05-31 Thread Charles Parcell 
Two suggestions.

1) Order your list of words from longest to shortest. Longer words have more
letters to build off of for future word placement. Longer words are also
harder to place within the grid size as additional words are added.

2) Starting your first word in the upper left limits how additional words
are chained off of it. Specifically, you are limiting the generator to only
matching the first letter of the second word to be placed. As an alternative
you could place your first word (horizontally or vertically, try both) in
the middle of your grid. This will allow for middle letters to be matched
with the first word.

Even better would be to have a floating grid. Start placing words allowing
the range of X and Y to adjust but maintaining the maximum X and Y of your
target grid.  For example, lets say your first word is 8 characters long and
your second word is 8 characters long as well. Your second word would cross
the first word at position 5 or the first word and position 2 of the second
word.  Now if the first word were placed in the top left or the middle of
the 9x9 grid, this match is not possible. If your generator could shift to
allow for these words to fit within the constraints of your 9x9 range, you
would be more likely to find a larger range of possible board layouts.  In
the case above, lets say the first word was placed horizontally in the
middle of the grid on row 5. The result would be that the starting word
would slide from row 5 up to row 3 to allow the second word to run from row
2 through row 9.

Obviously this sliding around the grid would likely only happen within the
first 2-6 placements (assuming that you were placing longer words first). By
this point your would run out of range to slide your grid around. Meaning
you would have met your X and Y bounds by sliding around your grid.

Charles P.


On Sun, May 31, 2009 at 7:36 AM, Paul Andrews p...@ipauland.com wrote:

 I suspect that the algorithm is wrong.

 For example quantity top left, alb will only fit quantity in one place and
 there is only one other a candidate amble. Very quickly your choices
 will be reduced due to placement, so 5,000 attempts seems excessive.

 Sadly I have a ton of other things to do or I'd have a go myself.

 Paul
 - Original Message - From: Paul Steven 
 paul_ste...@btinternet.com
 To: 'Flash Coders List' flashcoders@chattyfig.figleaf.com
 Sent: Sunday, May 31, 2009 12:17 PM

 Subject: RE: [Flashcoders] Crossword generator advice


  Thanks Paul

 My code should backtrack in the situation you mention. So for example if
 it
 fits tarragon on the first t but then continues to not be able to find a
 solution with tarragon in this position, it will backtrack so that it
 changes tarragon to the second t. However I still can't find a
 solution
 with 16 words. There may be some other flaws in my logic preventing this.
 I
 was wondering if in order to find a solution it will take thousands of
 attempts to find a solution? I have a counter that when reaches 5000, it
 breaks out of the loop trying to find the solution so I am effectively
 trying 5000 combinations - perhaps there is an equation to calculate how
 many combinations there are?

 I would be interested if anyone else can solve this puzzle with an
 alternative crossword generator?

 Thanks

 Paul

 -Original Message-
 From: flashcoders-boun...@chattyfig.figleaf.com
 [mailto:flashcoders-boun...@chattyfig.figleaf.com] On Behalf Of Paul
 Andrews
 Sent: 31 May 2009 12:07
 To: Flash Coders List
 Subject: Re: [Flashcoders] Crossword generator advice

 There is a flaw in your logic.

 It may be that multiple words fit a given situation, and  so it's
 necessary
 (with such a simple algorithm) to backtrack and look for another word to
 fit

 once you are unable to fit another word from your list - so the real
 problem

 is saving where you are in the list of possible combinations as you go
 along.

 For example, in quantity there are two t s, so there are two
 possibilities

 for fitting a word. You may go with tarragon for the first t but in
 practice it may only be possible to have a solution with tarragon as the
 second t. You must be able to backtrack your choice of tarragon as a
 solution for the first t and go with twin instead. You must be able to
 do this at every stage. Once you can your software should work.

 Paul


 - Original Message - From: Paul Steven 
 paul_ste...@btinternet.com
 To: 'Flash Coders List' flashcoders@chattyfig.figleaf.com
 Sent: Sunday, May 31, 2009 10:09 AM
 Subject: RE: [Flashcoders] Crossword generator advice


  Just to add more information to how I am currently trying to achieve
 this.

 I basically start with the first word in the list and place it in the top
 left position 0,0. I then attempt to add the next word in the list by
 finding a character in the first word that is the same as one of the
 characters in this new word. If it fails to add this next word, it puts
 this
 word to the back

RE: [Flashcoders] Crossword generator advice

2009-05-31 Thread Paul Steven 
Thanks Paul

Yes I suspect my algorithm is incorrect as I have tried 20,000 loops and it
still can't find a solution with all 16 words. I was just thinking as none
of the online crossword generators are able to find a solution that it
perhaps is more complex than meets the eye.

Cheers

Paul

-Original Message-
From: flashcoders-boun...@chattyfig.figleaf.com
[mailto:flashcoders-boun...@chattyfig.figleaf.com] On Behalf Of Paul Andrews
Sent: 31 May 2009 12:37
To: Flash Coders List
Subject: Re: [Flashcoders] Crossword generator advice

I suspect that the algorithm is wrong.

For example quantity top left, alb will only fit quantity in one place and 
there is only one other a candidate amble. Very quickly your choices 
will be reduced due to placement, so 5,000 attempts seems excessive.

Sadly I have a ton of other things to do or I'd have a go myself.

Paul
- Original Message - 
From: Paul Steven paul_ste...@btinternet.com
To: 'Flash Coders List' flashcoders@chattyfig.figleaf.com
Sent: Sunday, May 31, 2009 12:17 PM
Subject: RE: [Flashcoders] Crossword generator advice


 Thanks Paul

 My code should backtrack in the situation you mention. So for example if 
 it
 fits tarragon on the first t but then continues to not be able to find a
 solution with tarragon in this position, it will backtrack so that it
 changes tarragon to the second t. However I still can't find a 
 solution
 with 16 words. There may be some other flaws in my logic preventing this. 
 I
 was wondering if in order to find a solution it will take thousands of
 attempts to find a solution? I have a counter that when reaches 5000, it
 breaks out of the loop trying to find the solution so I am effectively
 trying 5000 combinations - perhaps there is an equation to calculate how
 many combinations there are?

 I would be interested if anyone else can solve this puzzle with an
 alternative crossword generator?

 Thanks

 Paul

 -Original Message-
 From: flashcoders-boun...@chattyfig.figleaf.com
 [mailto:flashcoders-boun...@chattyfig.figleaf.com] On Behalf Of Paul 
 Andrews
 Sent: 31 May 2009 12:07
 To: Flash Coders List
 Subject: Re: [Flashcoders] Crossword generator advice

 There is a flaw in your logic.

 It may be that multiple words fit a given situation, and  so it's 
 necessary
 (with such a simple algorithm) to backtrack and look for another word to 
 fit

 once you are unable to fit another word from your list - so the real 
 problem

 is saving where you are in the list of possible combinations as you go
 along.

 For example, in quantity there are two t s, so there are two 
 possibilities

 for fitting a word. You may go with tarragon for the first t but in
 practice it may only be possible to have a solution with tarragon as the
 second t. You must be able to backtrack your choice of tarragon as a
 solution for the first t and go with twin instead. You must be able to
 do this at every stage. Once you can your software should work.

 Paul


 - Original Message - 
 From: Paul Steven paul_ste...@btinternet.com
 To: 'Flash Coders List' flashcoders@chattyfig.figleaf.com
 Sent: Sunday, May 31, 2009 10:09 AM
 Subject: RE: [Flashcoders] Crossword generator advice


 Just to add more information to how I am currently trying to achieve 
 this.

 I basically start with the first word in the list and place it in the top
 left position 0,0. I then attempt to add the next word in the list by
 finding a character in the first word that is the same as one of the
 characters in this new word. If it fails to add this next word, it puts
 this
 word to the back of the list and tries the next word. If at any point, it
 is
 no longer able to add one of the remaining unplaced words, it back tracks
 and changes the previously added word to a different one. So in theory it
 should attempt to find a solution by trying every single word in the top
 left 0,0 position, then attempting to add the others where they can fit.
 The
 complete crossword solution has the word Quantity in the top left going
 across so in theory a solution should be possible with this word at this
 position and this orientation.

 Hopefully someone can shed some light on a solution.

 Many thanks

 Paul

 -Original Message-
 From: flashcoders-boun...@chattyfig.figleaf.com
 [mailto:flashcoders-boun...@chattyfig.figleaf.com] On Behalf Of Paul
 Steven
 Sent: 31 May 2009 10:02
 To: 'Flash Coders List'
 Subject: [Flashcoders] Crossword generator advice

 I am creating a crossword generator where you can enter the size of the
 grid
 and a list of words but for the life of me cannot get it to generate a
 puzzle with all the words in my list. This list of words is from a
 crossword
 that I know is possible. Now either my generator is not up to scratch or
 the
 process of creating a crossword is very complex and will require so many
 iterations that it would take a long time to work out a solution.

 Here is the list of words I am trying to generate

RE: [Flashcoders] Crossword generator advice

2009-05-31 Thread Paul Steven 
Thanks Charles for the great suggestions.

I will implement your suggestions but am still curious as to why my code
doesn't work. Without ordering the list or starting the first word
elsewhere, the one solution I am aware of for these 16 words has the word
QUANTITY top left - hence my reasoning for trying this. I am not sure if
standard crosswords always have the first word top left or not.

Anyway as Paul Andrews suggests, my algorithm must be incorrect so I need to
go through this with a fine tooth comb and see where any why it is failing. 

Thanks for your advice

Paul

-Original Message-
From: flashcoders-boun...@chattyfig.figleaf.com
[mailto:flashcoders-boun...@chattyfig.figleaf.com] On Behalf Of Charles
Parcell
Sent: 31 May 2009 15:19
To: Flash Coders List
Subject: Re: [Flashcoders] Crossword generator advice

Two suggestions.

1) Order your list of words from longest to shortest. Longer words have more
letters to build off of for future word placement. Longer words are also
harder to place within the grid size as additional words are added.

2) Starting your first word in the upper left limits how additional words
are chained off of it. Specifically, you are limiting the generator to only
matching the first letter of the second word to be placed. As an alternative
you could place your first word (horizontally or vertically, try both) in
the middle of your grid. This will allow for middle letters to be matched
with the first word.

Even better would be to have a floating grid. Start placing words allowing
the range of X and Y to adjust but maintaining the maximum X and Y of your
target grid.  For example, lets say your first word is 8 characters long and
your second word is 8 characters long as well. Your second word would cross
the first word at position 5 or the first word and position 2 of the second
word.  Now if the first word were placed in the top left or the middle of
the 9x9 grid, this match is not possible. If your generator could shift to
allow for these words to fit within the constraints of your 9x9 range, you
would be more likely to find a larger range of possible board layouts.  In
the case above, lets say the first word was placed horizontally in the
middle of the grid on row 5. The result would be that the starting word
would slide from row 5 up to row 3 to allow the second word to run from row
2 through row 9.

Obviously this sliding around the grid would likely only happen within the
first 2-6 placements (assuming that you were placing longer words first). By
this point your would run out of range to slide your grid around. Meaning
you would have met your X and Y bounds by sliding around your grid.

Charles P.


On Sun, May 31, 2009 at 7:36 AM, Paul Andrews p...@ipauland.com wrote:

 I suspect that the algorithm is wrong.

 For example quantity top left, alb will only fit quantity in one place and
 there is only one other a candidate amble. Very quickly your choices
 will be reduced due to placement, so 5,000 attempts seems excessive.

 Sadly I have a ton of other things to do or I'd have a go myself.

 Paul
 - Original Message - From: Paul Steven 
 paul_ste...@btinternet.com
 To: 'Flash Coders List' flashcoders@chattyfig.figleaf.com
 Sent: Sunday, May 31, 2009 12:17 PM

 Subject: RE: [Flashcoders] Crossword generator advice


  Thanks Paul

 My code should backtrack in the situation you mention. So for example if
 it
 fits tarragon on the first t but then continues to not be able to find
a
 solution with tarragon in this position, it will backtrack so that it
 changes tarragon to the second t. However I still can't find a
 solution
 with 16 words. There may be some other flaws in my logic preventing this.
 I
 was wondering if in order to find a solution it will take thousands of
 attempts to find a solution? I have a counter that when reaches 5000, it
 breaks out of the loop trying to find the solution so I am effectively
 trying 5000 combinations - perhaps there is an equation to calculate how
 many combinations there are?

 I would be interested if anyone else can solve this puzzle with an
 alternative crossword generator?

 Thanks

 Paul

 -Original Message-
 From: flashcoders-boun...@chattyfig.figleaf.com
 [mailto:flashcoders-boun...@chattyfig.figleaf.com] On Behalf Of Paul
 Andrews
 Sent: 31 May 2009 12:07
 To: Flash Coders List
 Subject: Re: [Flashcoders] Crossword generator advice

 There is a flaw in your logic.

 It may be that multiple words fit a given situation, and  so it's
 necessary
 (with such a simple algorithm) to backtrack and look for another word to
 fit

 once you are unable to fit another word from your list - so the real
 problem

 is saving where you are in the list of possible combinations as you go
 along.

 For example, in quantity there are two t s, so there are two
 possibilities

 for fitting a word. You may go with tarragon for the first t but in
 practice it may only be possible to have a solution with tarragon

RE: [Flashcoders] Crossword generator advice

2009-05-31 Thread Paul Steven 
Bit of a breakthrough - if I order the words in my initial list in the order
that the words appear in the crossword solution, my algorithm finds the
solution. Unfortunately though when in a different order, it doesn't work.


___
Flashcoders mailing list
Flashcoders@chattyfig.figleaf.com
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders