The Einstein puzzle solver I have been developing
works dramatically faster if the clues are provided in
certain orders. I am not sure if there is an ideal order,
but I have developed a heurisic for ordering the clues,
which typically number in the twenties (ie, there are about
24 clues in a typical puzzle). On the chance that some folks
might enjoy the challenge of coding such a heuristic, or of
suggesting an approach, I am posting this description. I
have no solution myself, but I am optimistic about the
heuristic.
There are 5 rule types, 0 1 2 3 4, as signalled by
the first character of any clue -- an example list of clues
is at the bottom of this post. Many puzzles have no type 0
clues, and some have no type 1 clues. In all rule types
except type 0, all of the characters after the first (the
type character) are individual puzzle markers; type zero
clues have only one marker following the 0 (the final
character determines the column to place the marker into on
the Einstein board). So all type 4 clues have 3 markers, all
type 0 clues have 1 marker, and the other types have 2
markers per clue. The markers in each clue can appear only
once, or not at all, in any one clue.
The first clues in any sorted list of clues should
be type 0 (and their markers are always placed on the game
board first immediately and automatically), sorting order
among them is irrelevant, as far as I can tell, except that
later clues will be best given sorting priority based on the
commonness of their markers with all the clues that
precede them, including type 0 markers.
After type zero clues, the sorting order is
1 2 4 3: type 1 clues are next most important; type 3
cluess are next, and so on. (Actually it is not entirely
clear that type 4's should be given priority over 3's.)
But more important than the sorting order of clue
types, is the priority that should be given to clues whose
markers have appeared in clues already in the (evolving)
sorted list of clues. So for example, if a type 4 rule
(which always contains 3 markers), has all three of its
markers already in the clue list, then it should be next in
the list. When ranking earlier markers, the marker appearing
in more clues ranks higher. A yet-to-be-ranked clue with
more markers already appearing in previous clues, has
priority over another with fewer of its markers appearing
earlier, regardless of in how many earlier clues the markers
appear.
This paragraph describes other facts which further
limit the makeup of clue pairs, but may not be relevant to
this sorting problem. Types 1 2 and 3 clues all always have
2 markers, but because of other things that determine clues,
the following type pairs cannot contain identical clue
markers: 12 13. But types 2 and 3 could conceivably have
identical markers and types 3 and 4 can have up to 2
identical markers.
I hope I have given all the necessary facts, but my
track record is not good. So feel free to complain, or
request clarification.
Below is a sample unsorted list of clues.
clues=: ];._2 noun define
0b1
0r0
4=$*
4*4#
3fv
4#dv
35A
4%eD
3rt
4^V+
2+s
2u2
2$F
2v]
3%5
1u3
1Ca
1t#
11B
15/
)
--
(B=)
PS. If you are familiar with the Einstein puzzle you will
not likely recognize the clues as given here because my
marker symbols are not traditional because the real markers
require unicode characters, which I am as yet unable to use
in this context. My Einstein solver is under development and
can be seen at this link.
http://www.jsoftware.com/jwiki/BrianSchott/code/EinsteinSolver
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
