Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- % Stan Wagon Problem of the Week #1258. A Self-Descriptive Crossword
- %
- % Each of the entries in this crossword grid describes the number of times that the letter named appears in the completed grid. For example, if the grid had a single Z, then one of the entries would be "ONE Z", with a space after "ONE". Plurals are indicated by S, as in THIRTEEN ES. Spaces are counted here, so if there were nineteen spaces, then one entry would be "NINETEEN S" with TWO spaces after the word. These conditions uniquely determine all entries. Fill in the grid so that it describes itself.
- %
- % Source. Lee Sallows, Nijmegen, The Netherlands
- %
- % Text users: Art at <http://stanwagon.com/public/POWARCHIVE/1258SallowsCrosswordArt.jpg>
- %
- % Issue: Just left of center top is a down-sequence of two squares. That cannot and does not count as an answer. Lee has come up with a version that eliminates this blemish, but that version will appear in the Amer. Math. Monthly, so I will not show it here. The blemish makes no difference to the solving experience.
- %
- %
- % 1
- % 2 3 4 5 6 7 8 9 10 11
- % 12 13 14 15 16
- % 17 18 19
- % 20 21 22 23 24 25 26
- % 27 28 29 30 31 32 33 34 35
- % 36 37 38 39
- % 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
- % 56 57 58
- % 59 60
- % 61 62 63 64 65 66 67 68 69 70 71 72
- % 73 74 75
- % 76 77
- % 78
- % 79 80 81 82 83 84 85 86 87 88
- % 89
- % 90
- %
- % To solve the problem with Clingo, enter: clingo < crossword.lp
- %
- % There are two solutions. One looks like this:
- %
- % S
- % F I F T E E N S S
- % O N E X
- % O T
- % N T W O W S
- % S E V E N F S O
- % O F
- % T H R E E U S S E V E N O S
- % R S U
- % R
- % F O U R T E E N S
- % S I I
- % N S
- % E
- % F I F T E E N E S
- % N
- % S
- %
- % The other is the same, except with the letter E & S interchanged
- % in the two FIFTEEN rows.
- % entry(E, C) :- Cell C is in entry E.
- entry(1, (1;3;16;18;21;34)).
- entry(2, (2;3;4;5;6;7;8;9;10;11)).
- entry(12, (12;13;14;15;16)).
- entry(17, (17;20;28;36;41)).
- entry(19, (19;25;35;38;50;57)).
- entry(21, (21;22;23;24;25;26)).
- entry(27, (27;28;29;30;31;32;33;34)).
- entry(33, (33;37;46;56;59;64;73)).
- entry(39, (39;54;58;60;72;75;77)).
- entry(40, (40;41;42;43;44;45;46;47)).
- entry(48, (48;49;50;51;52;53;54;55)).
- entry(61, (61;62;63;64;65;66;67;68;69;70;71)).
- entry(68, (68;74;76;78;86;89;90)).
- entry(79, (79;80;81;82;83;84;85;86;87;88)).
- % entry(E) :- E is an entry (a sequene of cells to be filled in).
- entry(X) :-entry(X, _).
- % entrylen(E, N) :- entry E has N cells.
- entrylen(E, N) :- N = #count { C : entry(E, C) }, entry(E).
- % entry(E, N, C) :- cell C is the Nth cell in entry E.
- entry(E, N+1, C) :- N = #count { D : entry(E, D), D < C }, entry(E, C).
- % Define the letters used in the spelling of each number word.
- #script (python)
- def word(n, s):
- terms = []
- for i, c in enumerate(s.string):
- terms.append((n.number, i+1, c))
- return terms
- #end.
- number(@word(1, "ONE")).
- number(@word(2, "TWO")).
- number(@word(3, "THREE")).
- number(@word(4, "FOUR")).
- number(@word(5, "FIVE")).
- number(@word(6, "SIX")).
- number(@word(7, "SEVEN")).
- number(@word(8, "EIGHT")).
- number(@word(9, "NINE")).
- number(@word(10, "TEN")).
- number(@word(10, "TEN")).
- number(@word(11, "ELEVEN")).
- number(@word(12, "TWELVE")).
- number(@word(13, "THIRTEEN")).
- number(@word(14, "FOURTEEN")).
- number(@word(15, "FIFTEEN")).
- number(@word(16, "SIXTEEN")).
- number(@word(17, "SEVENTEEN")).
- number(@word(18, "EIGHTEEN")).
- number(@word(19, "NINETEEN")).
- number(@word(20, "TWENTY")).
- % num(N, I, L) :- letter L is the Ith letter in the word for number N.
- % Example: num(2, 1, "T"), because "T" is the 1st letter of "TWO", the word for number 2.
- num(N, I, L) :- number((N, I, L)).
- % num(N): N is a number of times some letter can occur in the crossword.
- num(N) :- num(N, _, _).
- % numlen(N, M) :- the word for number N has M letters.
- numlen(N, M) :- M = #count { I : num(N,I,_) }, num(N).
- % letter(L) :- L is a letter used in the crossword.
- letter(L) :- num(_, _, L).
- letter(" ").
- % fill(E, N, L) :- Entry E consists of the word for number N followed by a
- % space followed by letter L followed by the letter "S".
- % Fill each entry with an arbitrary number and letter (e.g. "TWO ES").
- 1 { fill(E, N, L) : num(N), letter(L) } 1 :- entry(E).
- % Each entry must be exactly the right length for its contents.
- :- N > 1, fill(E, N, L), entrylen(E, M), numlen(N, K), M != K + 3.
- :- N = 1, fill(E, N, L), entrylen(E, M), numlen(N, K), M != K + 2.
- % cell(C, L) :- cell C contains letter L.
- cell(C, M) :- fill(E, N, _), entry(E, X, C), num(N, X, M).
- % Fill in the space after the count.
- cell(C, " ") :- fill(E, N, _), numlen(N, M), entry(E, M+1, C).
- % Fill in the letter after the space.
- cell(C, L) :- fill(E, N, L), numlen(N, M), entry(E, M+2, C).
- % Fill in the trailing "S" if the number is plural.
- cell(C, "S") :- fill(E, N, _), numlen(N, M), entry(E, M+3, C), N > 1.
- % Don't write two different letters into the same cell.
- :- cell(C, L1), cell(C, L2), L1 < L2.
- % occur(L, N) :- letter L occurs N times in the grid (N > 0).
- occur(L, N) :- N = #count { C : cell(C, L) }, letter(L), N > 0.
- % If a letter occurs in the grid, and there is an entry reflecting its count, those two counts must be equal.
- :- occur(L, N), fill(_, M, L), M != N.
- % Show the contents of each cell.
- #show cell/2.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
