User:Brian Schott/code/EinsteinSolver
Einstein Puzzle Solver
File:Einsteinsolver.ijs
File:Einsteinsolverloopless.ijs
According to Wikipedia WikiPedia:Zebra_Puzzle the Einstein puzzle is patterned after the Zebra puzzle, but is played on a 6 by 6 board containing rowwise symbols and in some ways resembles Sudoku. A completed puzzle looks like the following one, but with each row permuted according to the clues provided.
123456 ABCDEF ⅠⅡⅢⅣⅤⅥ ⚀⚁⚂⚃⚄⚅ ∆∇◻◇∧∨ +-÷=×√
Versions of the puzzle have been mentioned in the J forum for Windows [1] and for Macintosh [2].
Clues and their coding
The puzzle starts with a nearly empty board and some clues as to the positional relations between or among the puzzle "markers" or "icons" on the finished board. There are two classes of clues and in the latter class there are three distinct types of clues:
vertical clues in pairs:
Two marker icons are displayed in each clue. The clue tells that the two markers are in the same column and you know what row each icon belongs in because each icon only goes in one predetermined row.
horizontal clues come in pairs except one type that comes in triplets:
One of the pair type rules shows two icons and informs you that those two icons must appear in adjacent columns in the final puzzle board, but you cannot be sure which icon will be on the left or right from their order in the clue. Similarly, the triplet type clues present adjacent icons, but there are three icons instead of two. In the case of the triplet clues you can be sure the three icons are either in the order shown or in the reverse of the order shown, but not which one. Finally, the last type of horizontal clue contains just two icons, and limits the left to right order of the icons in the final puzzle board, but does not imply any adjacency between the icons.
In some puzzles you are also told at the beginning where a few of the icons reside exactly and those icons are typically placed for you by the computer program. In the script provided here, these exact positions are also provided as clues so that the script verb can be naturally dyadic.
Because the unicode glyphs are difficult to manage, the current script substitutes the following ascii characters which are not as pleasant.
number=: '123456' alpha=: 'ABCDEF' greek=: 'abcdef' chess=: 'rstuvw' poly=: '^V#$[]' math=: '+-%*=/' icons=: ;:'number alpha greek chess poly math' ".&>icons 123456 ABCDEF abcdef rstuvw ^V#$[] +-%*=/
As described elsewhere there are various clues provided and typically those clues are shown with coloring and positioning to simplify their use. To make the clues easier to enter into the J verb einstein they are coded in ascii, suggested by the following noun clues. Each clue begins with -- is prefixed by -- a single ordinal number (or 0).
clues=: ];._2 noun define 0+1 11A 2+= 3+- 41BC )
The zeroth clue 0+1 is of type 0 (it is an "exact" fact and should not be called a clue, really). The clue says that a plus sign goes in column 1. It needn't say what row the icon belongs in because all such math symbols are in the bottom row of all boards.
The first clue 11A is an "order" clue, as signalled by the leading 1 and informs us that the numeral 1 and the capital letter A are in the same column (in their respective rows).
The second clue 2+= is an "order" rule requiring the plus sign to be to the left of the equals sign. Coincidentally here the two icons would be literally next to one another because they are in the same row, but that is unusual for a clue.
The third clue 3+- is an adjacency clue, referred to as adj2 to distinguish it from the last clue type, adj3. This clue limits the plus and minus signs icons to being in columns next to one another, but in either +- or -+ order.
The fourth clue 41BC is an adjacency clue, referred to as adj3. This clue restricts the icons to being either 1BC or CB1 on the board. Notice that the three icons may be all be in one row, or in two rows as here, or in three different rows.
The einstein script attempts to solve puzzles in a very brute force way by generating potential board results pbsr from a list of existing potential boards pbs, starting with a rank 3 board provided as its left hand argument, which is usually 1 6 6$' '. If the noun clues above is supplied to einstein with a typical 6 by 6 board of spaces, 56 potential boards result. Many more clues would be required to produce a unique solution board. In fact einstein does not necessarily produce a single resulting board, but likely produces a single completed board (one with no remaining spaces) among other boards.
#boards einstein clues
56
_16]\;/ boards einstein clues
┌──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┐
│1 │1 │1 │1 │1 │1 │1 │ 1 │ 1 │ 1 │ 1 │ 1 │ 1 │ 1 │ 1 │ 1 │
│ABC │ABC │ABC │ABC │ABC │ABC │ABC │ ABC │ ABC │ ABC │ ABC │ ABC │ ABC │ ABC │ ABC │CBA │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
│-+= │ +-= │-+ = │ +- = │-+ = │ +- =│-+ =│-+= │ +-= │-+ = │ +- = │-+ = │ +- =│-+ =│-+= │-+= │
├──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┤
│ 1 │ 1 │ 1 │ 1 │ 1 │ 1 │ 1 │ 1 │ 1 │ 1 │ 1 │ 1 │ 1 │ 1 │ 1 │ 1 │
│ ABC │CBA │ ABC │CBA │ ABC │CBA │ ABC │CBA │ ABC │CBA │ ABC │CBA │ ABC│ CBA │ ABC│ CBA │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
│ +-= │ +-= │-+ = │-+ = │ +- = │ +- = │-+ = │-+ = │ +- =│ +- =│-+ =│-+ =│-+= │-+= │ +-= │ +-= │
├──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┤
│ 1 │ 1 │ 1 │ 1 │ 1 │ 1 │ 1 │ 1 │ 1 │ 1 │ 1 │ 1 │ 1 │ 1 │ 1 │ 1 │
│ ABC│ CBA │ ABC│ CBA │ ABC│ CBA │ ABC│ CBA │ ABC│ CBA │ CBA │ CBA │ CBA │ CBA │ CBA │ CBA │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
│-+ = │-+ = │ +- = │ +- = │-+ = │-+ = │ +- =│ +- =│-+ =│-+ =│-+= │ +-= │-+ = │ +- = │-+ = │ +- =│
├──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┤
│ 1 │ 1│ 1│ 1│ 1│ 1│ 1│ 1│ │ │ │ │ │ │ │ │
│ CBA │ CBA│ CBA│ CBA│ CBA│ CBA│ CBA│ CBA│ │ │ │ │ │ │ │ │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
│-+ =│-+= │ +-= │-+ = │ +- = │-+ = │ +- =│-+ =│ │ │ │ │ │ │ │ │
└──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┘
Real puzzles usually require multiple passes through einstein so that commonly it is employed in an infinite iteration as follows (typically it takes only two iterations).
#z=: einstein&clues^:_ boards
Processing approach
einstein processes each clue in a while. loop and inside of that it processes each existing potential board in another while. loop. The internal loop is controlled by select. which chooses its case. using the type of clue presented, so there are 5 major banks of code. Internal to each code block another select. is based upon the number of icons in the clue which match the icons in the potential boards pbs currently being processed. At the bottom of each pass of boards for a clue, pbsr replaces pbs.
I am considering removing some of the for. loops and other repetitious code, but that is not a high priority.
I am more interested in a way to use unicode characters instead of ascii characters in the clues, which means in the processing as well, but I need suggestions on introducing unicode.
I am also considering adding a user interface that allows for clicking and dragging.
Any other comments would be most welcome.
Sample clue sets
A couple of sample clue sets are provided below. Resequencing of the clues can effect the amount of processing required quite dramatically.
clues=: ];._2 noun define 0b1 0r0 3rt 1t# 4*4# 4#dv 4=$* 3fv 2v] 4%eD 35A 3%5 15/ 4^V+ 2+s 2u2 2$F 1u3 1Ca 11B ) clues=: ];._2 noun define 0D4 0]5 44ta 3w1 2A$ 2rV 4=3v 4EAv 3Bd 4f1^ 3=+ 4%#a 3d5 2-] 4V%/ 261 3#w 41db 2BF 4vus 1a- 1=c 1A% )
The following J code produced the canonical final puzzle board shown above, but does not solve any puzzle.
roman0=: 16b2160
dice0=: 16b2680
poly0=: 16b2206 16b2207 16b25fb 16b25c7 16b2227 16b2228
math0=: 0 1 2 4 3 5{16b002b 16b002d 16b00f7 16b00d7 16b003d 16b221a
t=: 4&u: NB. unicode from hex
seq6=: +&0 1 2 3 4 5
number=: '123456'
alpha=: 'ABCDEF'
roman=: t seq6 roman0
dice=: t seq6 dice0
poly=: t poly0
math=: t math0
chess=: t chess0
icons=: ;:'number alpha roman dice poly math'
".&>icons
123456
ABCDEF
ⅠⅡⅢⅣⅤⅥ
⚀⚁⚂⚃⚄⚅
∆∇◻◇∧∨
+-÷=×√
Of course a real puzzle would result in a permutation of each of the rows in the canonical display above, and the objective is to discover the correct permutations.
Clue sorting
Sorting the clues can improve processing speed. At one time I thought dramatic speed enhancements could be achieved and so I developed a primitive way to sort clues, only to discover that so far the differential is slight, and rather that some coding bugs were causing most of the problem. In any case, below I am posting the code.
NB. einsteinsolvercluesorter.ijs
NB. 2/14/10
types=: {."1 clues
masktypes=: 1 1 1,~'01' e. types
cluegroups=: ~.types
NB. this para produces sorted trimmed type groups
righttrim=: masktypes#2 1 1 1 0
rtrim=: -righttrim/:cluegroups
typegroups=: masktypes expand rtrim}."1 each ({."1@] </.])clues
typeorder=: masktypes#0 1 4 3 2
s=: typegroups{~"."0 cluegroups/:typeorder
NB. this para produces sorted whole trimmed type groups
wholerighttrim=: masktypes#1 1 1 1 0
wholertrim=: -(masktypes expand wholerighttrim){~"."0 cluegroups
wholetypegroups=: wholertrim}."1 each ({."1@] </.])clues
swhole=: (masktypes expand wholetypegroups){~"."0 cluegroups/:typeorder
NB. this para computes a markers frequency count
t=: ;<"1&.> s NB. boxed clue markers
f=: (\: {:"1)@(~. ,. ":@#/.~);, each}."1 &.> s NB. marker freq counts
b=: </."1/ |.|:f NB. markers boxed by freq count
fb=: +/+/"1 (|.@(>:@i.@#)*])(}.each t) e. &>"_ 0 b NB. clue rank order
NB. this para enables type 0 clues to be first, regardless
zerocluemask=: '0'={.&>t
cluemask=: '0'~:{.&>t
nonzerocluesingroups=: ((\:~@]) </. (]\:~i.@#))cluemask#fb
twhole=: (<"1 ;swhole)/:cluemask NB. zero clues to front
NB. this para collects information to sort clues
cluesingroups=: (<i. +/zerocluemask),(+/zerocluemask)+ each nonzerocluesingroups
cluesortorder=: typeorder i.".@{.&> twhole
order=: ;cluesingroups /: each cluesingroups{each"0 1 <cluesortorder
clues2=: >order {twhole
NB. the global list `clues` is sorted in the global list `clues2`
NB. when this script is run
NB. the script attempts to sort according to the hueristic
NB. I described and revised in the jforums
NB. http://www.jsoftware.com/pipermail/programming/2010-February/018476.html
There seems to be some confusion in the code above between a "dice" (shown) and "chess" (not shown) set of icons. -- Devon McCormick <<DateTime(2010-02-17T17:48:30-0200)>>