This article explains how to model a logic grid puzzle in the JavaScript programming language.
Table of Contents
Introduction
This article explains how to model a logic grid puzzle in the JavaScript programming language. Logic grid puzzles, also known as logic puzzles or logic problems can be found in magazines by Dell Magazines and Penny Press. The Mystery Master website at http://www.mysterymaster.com is devoted to writing software that can solve logic puzzles. Think "Skynet", but without the intent of eliminating mankind. This article will focus on the logic puzzle "Five Houses". Earlier versions of this two-star puzzle have been called "Einstein's Riddle" or the "Zebra Puzzle". This version of the puzzle appeared in a column by the very cerebral Marilyn vos Savant. Please look at this logic puzzle before continuing. You should have basic knowledge of JavaScript, know some of the newer constructs, and understand how classes work in JavaScript.
JavaScript
JavaScript is the client-side language of the web. I don't think it is the best language, but there have been improvements over the years. I wish it was strongly-typed, had better scoping rules (public, private, etc.), but I guess I could use TypeScript. It can't do some of the nice things I can do in C# like initialize an object when I instantiate it. It doesn't have the null-coalescing operator ??. It is also very fragile - your IDE and/or browser may not pick up your mistakes. But enough complaining... Here are some of the things I do like.
- The
"use strict";
option. - Define a constant with the
const
keyword. - Avoid the hoisting of variables with the
let
keyword. - The
addEventListener
method so the method the event calls can be local. - The ability to return closures - functions that refer to local variables. See the sections on Smart Links and Smart Rules for more on closures.
- The ability to store/retrieve information in local storage.
What is a Logic Puzzle
A logic puzzle is a story of mystery. But you are not only its reader, you are its most important character - the detective! And as with any detective worth their spyglass, you must solve the mystery. Most logic puzzles have properties such as its title, author, and number of stars. One star means the puzzle is easy, and five stars means it is very difficult. Each puzzle also has a humorous image. While these properties are important, they won't help you solve a logic puzzle. What does help are the clues of the puzzle. The clues are usually given in a numbered list, but sometimes they can also be in the introduction. The properties, introduction, and list of clues are the text of the logic puzzle.
Note: If you wanted to solve a logic puzzle on your own, you have the following tools at your disposal: the Chart and the Grids. Both of these forms will be discussed in a future article.
To model a logic puzzle, the text of the logic puzzle must be parsed into specific types of data. Everything that is essential to solving a logic puzzle must be captured by this data. There is one important thing to remember as you go forward:
All of the relationships between the nouns in a logic puzzle must be expressed as either facts or rules.
Please read the text of the puzzle with the following questions in mind.
- What are the objects in the puzzle? These are the nouns.
- What are the relationships between the nouns? These are expressed by the verbs and links.
- What are the facts? These combine the nouns, verbs, and links into static statements.
- What are the rules? These are conditional statements. Not all puzzles have rules, including this one.
We need data structures to store each type of data, and when we talk data structures in a world of OOP, we're talking classes. And what should we name a class that stores all of the data for a logic puzzle? Why Puzzle of course!
Puzzle
The Puzzle
class is the parent class of every puzzle module. This class performs many duties. It has methods to load data into an array for each type of object. It has a method to validate the data. And it needs to make that data available to the classes that view and solve the puzzle.
The Puzzle Class
"use strict";
function Puzzle() {
this.myName = null;
this.myTitle = null;
this.nounTypes = [];
this.verbs = [];
this.links = [];
this.facts = [];
this.rules = [];
this.maxNounTypes = 0;
this.maxNouns = 0;
this.maxLinks = 0;
this.maxFacts = 0;
this.maxRules = 0;
this.isValid = false;
this.toString = function () {
return this.myTitle === null ? "Puzzle" : this.myTitle;
};
this.asString = function () { return this.toString(); };
this.addNounType = function (name) {
let nounType = new NounType(this.nounTypes.length, name);
this.nounTypes.push(nounType);
this.maxNounTypes = this.nounTypes.length;
if (nounType.num === 1) this.maxNouns = nounType.nouns.length;
return nounType;
};
this.addLink = function (name, nounType) {
let link = new Link(this.links.length, name, nounType);
this.links.push(link);
this.maxLinks = this.links.length;
return link;
};
function getClueNumMsg(clueNum, name) {
if (clueNum === null || clueNum.length < 1) return name;
let i = name.length - 1;
if (i < 0) return name;
let eos = name[i];
let txt = "";
if (clueNum[0] === 'A') {
let tmp = clueNum.length > 1 ? " " + clueNum.substring(1) : "";
txt = "analysis" + tmp;
}
else if (clueNum[0] === '0') {
txt = "intro";
}
else {
let tmp = clueNum.indexOf(",") > -1 ? "s" : "";
txt = "clue" + tmp + " " + clueNum;
}
let msg = name.substring(0, i) + " (" + txt + ")" + eos;
return msg;
}
this.addFact = function (clueNum, nounA, verb, link,
nounB = null, name = null, initEnabled = true) {
if (nounB === null)
this.addFacts1(clueNum, nounA, verb, link, name, initEnabled);
else
this.addFacts2(clueNum, nounA, verb, link, nounB, name, initEnabled);
};
this.addRule = function (clueNum, name, nouns = null, initEnabled = true) {
let msg = getClueNumMsg(clueNum, name);
let rule = new Rule(this.rules.length, msg, nouns, initEnabled);
this.rules.push(rule);
this.maxRules = this.rules.length;
return rule;
};
this.getNounType = function (num) {
return this.nounTypes[num - 1];
};
this.getNoun = function (typeNum, num) {
return this.nounTypes[typeNum - 1].nouns[num - 1];
};
this.getVerb = function (num) {
return this.verbs[num + 1];
};
this.sayFact = function (noun1, verb, link, noun2) {
return "PARENT " + noun1.name + " " + verb.name + " " +
link.name + " " + noun2.name + ".";
};
this.getArrayExcept = function (nouns1, nouns2) {
let nouns = [];
for (let noun1 of nouns1) {
let found = false;
for (let noun2 of nouns2) {
if (noun1 === noun2) {
found = true;
break;
}
}
if (!found) nouns.push(noun1);
}
return nouns;
};
this.addOneFact = function (clueNum, noun1, verb, link,
noun2, name = null, initEnabled = true) {
let txt = name;
if (name === null || name.length < 1) {
txt = this.sayFact(noun1, verb, link, noun2);
}
let ok = true;
for (let oldFact of this.facts) {
if (oldFact.verb !== verb) continue;
if (oldFact.noun1 === noun1 && oldFact.link === link &&
oldFact.noun2 === noun2)
ok = false;
else if (oldFact.noun1 === noun2 && oldFact.link === link &&
oldFact.link.num === 0 && oldFact.noun2 === noun1)
ok = false;
if (!ok) {
console.log("Warning! This fact already exists: " +
oldFact.num + " " + oldFact.name);
return null;
}
}
let msg = getClueNumMsg(clueNum, txt);
let fact = new Fact(this.facts.length, msg,
noun1, verb, link, noun2, initEnabled);
this.facts.push(fact);
this.maxFacts = this.facts.length;
return fact;
};
this.addFacts1 = function (clueNum, nouns, verb, link,
name = null, initEnabled = true) {
for (let i = 0; i < nouns.length - 1; i++) {
let noun1 = nouns[i];
for (let j = i + 1; j < nouns.length; j++) {
let noun2 = nouns[j];
if (noun1 === noun2 || (link === With &&
noun1.type === noun2.type)) continue;
this.addOneFact(clueNum, noun1, verb,
link, noun2, name, initEnabled);
}
}
};
this.addFacts2 = function (clueNum, nounA, verb, link, nounB,
name = null, initEnabled = true) {
let nouns1 = Array.isArray(nounA) ? nounA : [nounA];
let nouns2 = Array.isArray(nounB) ? nounB : [nounB];
for (let noun1 of nouns1) {
for (let noun2 of nouns2) {
if (noun1 === noun2 || (link === With &&
noun1.type === noun2.type)) continue;
this.addOneFact(clueNum, noun1, verb, link, noun2, name, initEnabled);
}
}
};
this.addFactsInSequence = function (clueNum, nouns, verb,
link, name = null, initEnabled = true) {
for (let i = 0; i < nouns.length - 1; i++) {
this.addOneFact(clueNum, nouns[i], verb,
link, nouns[i + 1], name, initEnabled);
}
};
this.addFactsOneToOne = function (clueNum, nounA, verb,
link, nounB, name = null, initEnabled = true) {
let nouns1 = Array.isArray(nounA) ? nounA : nounA.nouns;
let nouns2 = Array.isArray(nounB) ? nounB : nounB.nouns;
let n = nouns1.length;
if (n !== nouns2.length) return;
for (let i = 0; i < n; i++) {
this.addOneFact(clueNum, nouns1[i], verb,
link, nouns2[i], name, initEnabled);
}
};
this.addFactsStartsWith = function
(clueNum, noun1, nounType2, flag, ch, name = null, initEnabled = true) {
for (let noun2 of nounType2.nouns) {
if ((noun2.name[0] === ch) === flag) {
this.addOneFact(clueNum, noun1, IsNot, With, noun2, name, initEnabled);
}
}
};
this.addFactsIsNotFirstChar = function (clueNum, nounType1,
nounType2, flag, name = null, initEnabled = true) {
for (let noun1 of nounType1.nouns) {
for (let noun2 of nounType2.nouns) {
if ((noun1.name[0] === noun2.name[0]) === flag) {
this.addOneFact(clueNum, noun1, IsNot, With,
noun2, name, initEnabled);
}
}
}
};
this.addFactsNotConsecutive = function (clueNum, nouns, link,
name = null, initEnabled = true) {
let n = nouns.length;
let type = link.nounType;
let max = type.nouns.length;
if (2 * n - 1 === max) {
for (let noun of nouns) {
for (let i = 1; i < max; i += 2) {
let slot = type.nouns[i];
this.addOneFact
(clueNum, noun, IsNot, With, slot, name, initEnabled);
}
}
}
else {
for (let i1 = 0; i1 < n - 1; i1++) {
let noun1 = nouns[i1];
for (let i2 = i1 + 1; i2 < n; i2++) {
let noun2 = nouns[i2];
this.addOneFact(clueNum, noun1, IsNot,
link, noun2, name, initEnabled);
this.addOneFact(clueNum, noun2, IsNot, link,
noun1, name, initEnabled);
}
}
}
};
let viewer = null;
let solver = null;
this.validate = function (aviewer = null, asolver = null) {
viewer = aviewer;
solver = asolver;
if (this.myName == null || this.myName.length === 0)
throw new Error("The name of the puzzle must be given!");
if (this.myTitle == null || this.myTitle.length === 0)
throw new Error("The title of the puzzle must be given!");
this.maxNounTypes = this.nounTypes.length;
if (this.maxNounTypes < 2) throw new Error
("The puzzle must have at least two noun types!");
this.maxNouns = this.nounTypes[0].nouns.length;
if (this.maxNouns < 2) throw new Error
("The puzzle must have at least two nouns per type!");
for (let nounType of this.nounTypes) {
if (nounType.nouns.length !== this.maxNouns)
throw new Error("The puzzle must have the same number of nouns per type!");
}
this.verbs = [IsNot, Maybe, Is];
if (this.verbs.length !== Verb.MaxVerbs) throw new Error
("The puzzle must have exactly " + Verb.MaxVerbs + " verbs!");
this.maxLinks = this.links.length;
if (this.maxLinks < 1) throw new Error
("The puzzle must have be at least one link!");
if (this.links[0].nounType == null) this.links[0].nounType = this.nounTypes[0];
for (let link of this.links) {
if (link.nounType == null) {
throw new Error("Link " + link.num +
" must have a noun type!" + NL + link.name);
}
if (link.f == null) {
throw new Error("Link " + link.num +
" must have a function!" + NL + link.name);
}
link.update();
}
this.maxFacts = this.facts.length;
for (let fact of this.facts) {
if (fact.verb === Maybe) {
throw new Error("Fact " + fact.num +
" cannot use the possible verb!" + NL + fact.name);
}
if (fact.noun1 === fact.noun2) {
throw new Error("Fact " + fact.num +
" cannot have both nouns be the same!" + NL + fact.name);
}
let link = fact.link;
let type = link.nounType;
if (link.num < 1 && fact.noun1.type === fact.noun2.type) {
throw new Error("Fact " + fact.num +
" cannot state that two nouns of the same type are
[not] together!" + NL + fact.name);
}
if (fact.noun1.type === type && fact.noun2.type === type) {
throw new Error("Fact " + fact.num + " cannot have the link
and both nouns with the same type!" + NL + fact.name);
}
}
this.maxRules = this.rules.length;
for (let rule of this.rules) {
if (rule.f == null) {
throw new Error("Rule " + rule.num +
" must have a function!" + NL + rule.name);
}
}
if (this.facts.length < 1 && this.rules.length < 1) {
throw new Error("The puzzle must have at least one fact or rule!");
}
for (let nounType of this.nounTypes) {
for (let noun of nounType.nouns) {
noun.pairs = new Array(this.maxNounTypes);
for (let fact of this.facts) {
let link = fact.link;
if (link.num < 1) continue;
if (link.nounType === fact.noun1.type ||
link.nounType === fact.noun2.type) continue;
if (fact.noun1 === noun || fact.noun2 === noun) {
noun.facts.push(fact);
}
}
}
}
this.isValid = true;
this.maxGrids = this.maxNounTypes * (this.maxNounTypes - 1) / 2;
this.maxPairs = this.maxGrids * this.maxNouns;
this.maxMarks = this.maxPairs * this.maxNouns;
this.marks = new Array(this.maxMarks);
for (let i = 0; i < this.maxMarks; i++) { this.marks[i] = new Mark(i); }
grids = new Array(this.maxGrids);
for (let g = 0; g < this.maxGrids; g++) {
grids[g] = new Array(this.maxNouns);
for (let n1 = 0; n1 < this.maxNouns; n1++) {
grids[g][n1] = new Array(this.maxNouns);
for (let n2 = 0; n2 < this.maxNouns; n2++) {
grids[g][n1][n2] = null;
}
}
}
this.resetWork();
return 0;
};
this.resetWork = function () {
this.numPairs = 0;
for (let nounType of this.nounTypes) { nounType.reset(); }
this.numFacts = 0; this.numFactHits = 0;
for (let fact of this.facts) { fact.reset(); }
this.numRules = 0; this.numRuleHits = 0;
for (let rule of this.rules) { rule.reset(); }
this.numMarks = 0;
for (let mark of this.marks) { mark.reset(); }
this.numGuesses = 0;
for (let g = 0; g < this.maxGrids; g++) {
for (let n1 = 0; n1 < this.maxNouns; n1++) {
for (let n2 = 0; n2 < this.maxNouns; n2++) {
grids[g][n1][n2] = null;
}
}
}
};
this.answer = null;
this.isAnswer = function () {
if (this.answer === null) return true;
let nounType1 = this.nounTypes[0];
for (let noun1 of nounType1.nouns) {
for (let nounType2 of this.nounTypes) {
if (nounType2.num === 1) continue;
if ((Puzzle.getPairNounNum(noun1, nounType2) - 1)
!== this.answer[nounType2.num - 2][noun1.num - 1]) return false;
}
}
return true;
};
IsNot.name = "is not";
Maybe.name = "may be";
Is.name = "is";
With = this.addLink("with", null);
With.f = SmartLink.getIsWith();
this.numFacts = 0;
this.numFactHits = 0;
this.numRules = 0;
this.numRuleHits = 0;
this.numMarks = 0;
this.numPairs = 0;
this.numGuesses = 0;
this.maxMarks = 0;
this.maxPairs = 0;
this.maxGrids = 0;
this.marks = [];
this.getLastMark = function () {
return (this.numMarks > 0) ? this.marks[this.numMarks - 1] : null;
};
this.getLastUserMark = function () {
for (let i = this.numMarks; i > 0; i--) {
let mark = this.marks[i - 1];
if (mark.type === Mark.Type.User) return mark;
}
return null;
};
this.undoAssumption = function (callback = null) {
while (this.numMarks > 0) {
let mark = this.removeMark(callback);
if (mark.type === Mark.Type.Level) break;
}
};
this.undoUserMark = function (callback = null) {
let mark = this.getLastUserMark();
if (mark === null) return;
print("puzzle.undoUserMark The last mark you entered is " + mark);
while (this.numMarks > 0) {
mark = this.removeMark(callback);
if (mark.type === Mark.Type.User) break;
}
};
this.removeMark = function (callback = null) {
let mark = this.marks[this.numMarks - 1];
this.removeGridMark(mark);
if (mark.verb === Is) {
--this.numPairs;
mark.noun1.pairs[mark.noun2.type.num - 1] = null;
mark.noun2.pairs[mark.noun1.type.num - 1] = null;
}
mark.clearPlaceholders();
mark.undoDisabledFacts();
--this.numMarks;
if (callback !== null) callback(mark);
return mark;
};
this.addMarkByObjLit = function (obj) {
let mc = (solver !== null) ? "WW" : "UI";
let rs = 0;
let markType = Mark.Type.User;
if (obj.type != null) markType = Mark.getType(obj.type);
let levelNum = obj.levelNum == null ||
obj.levelNum < 1 ? Solver.MaxLevels : obj.levelNum;
let levelSub = obj.levelSub == null ? ' ' : obj.levelSub;
let refNum = obj.refNum == null ? levelNum : obj.refNum;
let refChar = obj.refChar == null ? levelSub : obj.refChar;
let noun1 = this.getNoun(obj.noun1TypeNum, obj.noun1Num);
let noun2 = this.getNoun(obj.noun2TypeNum, obj.noun2Num);
let verb = this.getVerb(obj.verbNum);
let reason = obj.reason == null ? "" : obj.reason;
let facts = [];
if (obj.facts != null) {
for (let inum of obj.facts) {
facts.push(this.facts[inum - 1]);
}
}
let lonerNum = obj.lonerNum == null ? -1 : obj.lonerNum;
let refMark = obj.refMark == null ||
obj.refMark === -1 ? null : this.marks[obj.refMark - 1];
let disabledFacts = [];
if (obj.disabledFacts != null) {
for (let inum of obj.disabledFacts) {
disabledFacts.push(this.facts[inum - 1]);
}
}
if (solver !== null)
rs = solver.addMark(levelNum, levelSub, markType,
refNum, refChar, noun1, verb, noun2, reason,
facts, lonerNum, refMark);
else
rs = this.addMark(levelNum, levelSub, markType,
refNum, refChar, noun1, verb, noun2, reason,
facts, lonerNum, refMark, disabledFacts);
return rs;
};
this.addMark = function (levelNum, levelSub, markType, refNum, refChar, noun1,
verb, noun2, reason, facts = null, lonerNum = -1,
refMark = null, disabledFacts = null) {
let mc = (solver !== null) ? "WW" : "UI";
if (markType === Mark.Type.User) levelNum = Solver.MaxLevels;
let mark = this.marks[this.numMarks++];
mark.type = markType;
mark.reason = reason;
mark.levelNum = levelNum;
mark.levelSub = levelSub;
mark.refNum = refNum;
mark.refChar = refChar;
mark.noun1 = noun1;
mark.verb = verb;
mark.noun2 = noun2;
mark.facts = facts === null ? [] : facts;
mark.lonerNum = lonerNum;
mark.refMark = refMark;
mark.disabledFacts = [];
mark.guess = markType === Mark.Type.User ||
(markType === Mark.Type.Level && levelNum === Solver.MaxLevels);
if (mark.guess) ++this.numGuesses;
if (mark.verb === Is) {
++this.numPairs;
mark.noun1.pairs[mark.noun2.type.num - 1] = mark;
mark.noun2.pairs[mark.noun1.type.num - 1] = mark;
}
this.setGridMark(mark);
if (solver !== null) {
for (let fact of mark.facts) {
if (!fact.enabled) mark.disabledFacts.push(fact);
}
for (let fact of this.facts) {
if (!fact.enabled || fact.type !== 1 || mark.verb !== fact.verb ||
(mark.facts.length > 0 && mark.facts[0] === fact)) continue;
if ((mark.noun1 === fact.noun1 && mark.noun2 === fact.noun2) ||
(mark.noun1 === fact.noun2 && mark.noun2 === fact.noun1)) {
fact.enabled = false;
mark.disabledFacts.push(fact);
}
}
}
if (viewer !== null) {
if (disabledFacts !== null) {
for (let fact of disabledFacts) {
fact.enabled = false;
}
mark.disabledFacts = disabledFacts;
}
}
for (let fact of mark.facts) {
++fact.hits;
if (fact.hits === 1) ++this.numFacts;
++this.numFactHits;
if (viewer !== null) viewer.updateOnFact(fact);
}
if (mark.type === Mark.Type.Rule) {
let ruleNum = mark.refNum;
let rule = this.rules[ruleNum - 1];
++rule.hits;
if (rule.hits === 1) ++this.numRules;
++this.numRuleHits;
if (viewer) viewer.updateOnRule(rule);
}
if (viewer) viewer.updateOnMark(mark);
return mark;
};
let grids = [];
this.getGridMark = function (noun1, noun2) {
return this.getGridMark2(noun1.type.num, noun1.num, noun2.type.num, noun2.num);
};
this.getGridMark2 = function(t1, n1, t2, n2) {
if (t1 === t2) return null;
if (t1 < t2) {
let g = this.getGridNum(t1, t2);
return grids[g - 1][n1 - 1][n2 - 1];
}
else {
let g = this.getGridNum(t2, t1);
return grids[g - 1][n2 - 1][n1 - 1];
}
};
this.getGridVerb = function (noun1, noun2) {
if (noun1.type === noun2.type) return IsNot;
let mark = this.getGridMark(noun1, noun2);
return (mark === null) ? Maybe : mark.verb;
};
this.setGridMark = function (mark) {
this.setGridMark2(mark.noun1.type.num, mark.noun1.num,
mark.noun2.type.num, mark.noun2.num, mark);
};
this.removeGridMark = function (mark) {
this.setGridMark2(mark.noun1.type.num, mark.noun1.num,
mark.noun2.type.num, mark.noun2.num, null);
};
this.setGridMark2 = function (t1, n1, t2, n2, mark) {
if (t1 === t2) return;
if (t1 < t2) {
let g = this.getGridNum(t1, t2);
grids[g - 1][n1 - 1][n2 - 1] = mark;
}
else {
let g = this.getGridNum(t2, t1);
grids[g - 1][n2 - 1][n1 - 1] = mark;
}
};
this.isMark = function (noun1, verb, noun2) {
let mark = this.getGridMark(noun1, noun2);
let b = mark !== null && mark.verb === verb;
return b;
};
this.getNouns = function (noun1, nounType2) {
let nouns = [];
for (let noun2 of nounType2.nouns) {
if (this.getGridMark(noun1, noun2) === null) nouns.push(noun2);
}
return nouns;
};
this.getGridNum = function (t1, t2) {
return (t1 < t2) ? (t1 - 1) * this.maxNounTypes + t2 - t1 *
(t1 + 1) / 2 : (t2 - 1) * this.maxNounTypes + t1 - t2 * (t2 + 1) / 2;
};
this.maybeRelated = function (noun1, link, noun2) {
let ok = false;
let type = link.nounType;
let slot1 = Puzzle.getPairNoun(noun1, type);
let slot2 = Puzzle.getPairNoun(noun2, type);
if (slot1 !== null && slot2 !== null) {
if (link.f(slot1, slot2) === Is) return true;
}
else if (slot1 !== null && slot2 === null) {
for (let slotB of type.nouns) {
if (this.getGridVerb(slotB, noun2) !== Maybe) continue;
if (link.f(slot1, slotB) === Is) return true;
}
}
else if (slot1 === null && slot2 !== null) {
for (let slotA of type.nouns) {
if (this.getGridVerb(slotA, noun1) !== Maybe) continue;
if (link.f(slotA, slot2) === Is) return true;
}
}
else {
for (let slotA of type.nouns) {
if (this.getGridVerb(slotA, noun1) !== Maybe) continue;
for (let slotB of type.nouns) {
if (this.getGridVerb(slotB, noun2) !== Maybe) continue;
if (link.f(slotA, slotB) === Is) return true;
}
}
}
return ok;
};
this.canBeWith = function (noun1, noun2) {
let rs = false;
let noun;
let oldMark = this.getGridMark(noun1, noun2);
if (oldMark !== null && oldMark.verb === IsNot) return rs;
noun = Puzzle.getPairNoun(noun1, noun2.type);
if (noun !== null && noun !== noun2) return rs;
noun = Puzzle.getPairNoun(noun2, noun1.type);
if (noun !== null && noun !== noun1) return rs;
return true;
};
this.canBeLinked = function (noun1, link, slot2, i) {
let slots = link.nounType.nouns;
for (let slot1 of slots) {
let verb = (i !== 1) ? link.f(slot1, slot2) : link.f(slot2, slot1);
if (verb === Is && this.canBeWith(slot1, noun1)) return true;
}
return false;
};
this.getCommonNoun = function (noun1, noun2, nounType3) {
for (let noun3 of nounType3.nouns) {
if (this.canBeWith(noun1, noun3) && this.canBeWith(noun2, noun3))
return noun3;
}
return null;
};
}
Puzzle.getPairNoun = function (noun1, nounType2) {
let mark = noun1.pairs[nounType2.num - 1];
if (mark === null) return null;
return mark.noun1 === noun1 ? mark.noun2 : mark.noun1;
};
Puzzle.getPairNounNum = function (noun1, nounType2) {
let mark = noun1.pairs[nounType2.num - 1];
if (mark === null) return 0;
return mark.noun1 === noun1 ? mark.noun2.num : mark.noun1.num;
};
Puzzle.isPair = function (noun1, noun2) {
return Puzzle.getPairNoun(noun1, noun2.type) === noun2 ? true : false;
};
Puzzle Module
The puzzle module stores all of the data and functions necessary to solve it. In order to do this, this class must inherit from the base class Puzzle
. Below is the puzzle module for the logic puzzle "Five Houses". Please note that since all of the relationships in this puzzle can be represented by facts, there are no rules.
The FiveHouses Class
"use strict";
function FiveHouses() {
this.myName = "FiveHouses";
this.myTitle = "Five Houses";
let houses = this.addNounType("House");
let house1 = houses.addNoun("1st");
let house2 = houses.addNoun("2nd");
let house3 = houses.addNoun("3rd");
let house4 = houses.addNoun("4th");
let house5 = houses.addNoun("5th");
let colors = this.addNounType("Color");
let red = colors.addNoun("red");
let green = colors.addNoun("green");
let white = colors.addNoun("white");
let yellow = colors.addNoun("yellow");
let blue = colors.addNoun("blue");
let nationalities = this.addNounType("Nationality");
let englishman = nationalities.addNoun("Englishman");
let spaniard = nationalities.addNoun("Spaniard");
let ukrainian = nationalities.addNoun("Ukrainian");
let norwegian = nationalities.addNoun("Norwegian");
let japanese = nationalities.addNoun("Japanese man", "Japanese");
let hobbies = this.addNounType("Hobby");
let stamps = hobbies.addNoun("stamps");
let antiques = hobbies.addNoun("antiques");
let sings = hobbies.addNoun("singing");
let gardens = hobbies.addNoun("gardening");
let cooking = hobbies.addNoun("cooking");
let pets = this.addNounType("Pet");
let dogs = pets.addNoun("dogs");
let snails = pets.addNoun("snails");
let fox = pets.addNoun("fox");
let horse = pets.addNoun("horse");
let zebra = pets.addNoun("zebra");
let drinks = this.addNounType("Drink");
let coffee = drinks.addNoun("coffee");
let tea = drinks.addNoun("tea");
let milk = drinks.addNoun("milk");
let juice = drinks.addNoun("juice");
let water = drinks.addNoun("water");
let directlyRightOf = this.addLink("directly to the right of", houses);
directlyRightOf.f = SmartLink.getIsMoreBy(1);
let nextTo = this.addLink("next to", houses);
nextTo.f = SmartLink.getIsNextTo();
this.addFact("1", englishman, Is, With, red,
"The Englishman lives in the red house.");
this.addFact("2", spaniard, Is, With, dogs,
"The Spaniard owns dogs.");
this.addFact("3", coffee, Is, With, green,
"Coffee is drunk in the green house.");
this.addFact("4", ukrainian, Is, With, tea,
"The Ukrainian drinks tea.");
this.addFact("5", green, Is, directlyRightOf, white,
"The green house is directly to the right of the white one.");
this.addFact("6", stamps, Is, With, snails,
"The stamp collector owns snails.");
this.addFact("7", antiques, Is, With, yellow,
"The antiques collector lives in the yellow house.");
this.addFact("8", house3, Is, With, milk,
"The man in the middle house drinks milk.");
this.addFact("9", norwegian, Is, With, house1,
"The Norwegian lives in the first house.");
this.addFact("10", sings, Is, nextTo, fox,
"The man who sings lives next to the man with the fox.");
this.addFact("11", gardens, Is, With, juice,
"The man who gardens drinks juice.");
this.addFact("12", antiques, Is, nextTo, horse,
"The antiques collector lives next to the man with the horse.");
this.addFact("13", japanese, Is, With, cooking,
"The Japanese man's hobby is cooking.");
this.addFact("14", norwegian, Is, nextTo, blue,
"The Norwegian lives next to the blue house.");
this.answer = [ [ 3, 4, 0, 2, 1 ], [ 3, 2, 0, 1, 4 ],
[ 1, 2, 0, 3, 4 ], [ 2, 3, 1, 0, 4 ], [ 4, 1, 2, 3, 0 ] ];
}
FiveHouses.prototype = new Puzzle();
FiveHouses.prototype.constructor = FiveHouses;
puzzle = new FiveHouses();
Prototypal Inheritance
You can see that the name of the puzzle module class is FiveHouses
. So how does our child class inherit the powers of the Puzzle
class? The last three lines of every puzzle module performs "inheritance" for a prototype-based language. Note: The variable puzzle
was defined earlier as a global.
FiveHouses.prototype = new Puzzle();
FiveHouses.prototype.constructor = FiveHouses;
puzzle = new FiveHouses();
Here is a description of what each line does:
- Sets the
FiveHouses
class to inherit from the base class Puzzle
. Unfortunately, the constructor for the child class FiveHouses
is now set to the constructor of the parent class Puzzle
. - Sets the constructor for
FiveHouses
to its own constructor. - Instantiates (creates) an object of class
FiveHouses
, which inherits from Puzzle
, and invokes its own constructor.
I currently do not use the class
and constructor
keywords introduced in ECMAScript 2015. So when I say constructor, I really mean the function FiveHouses
that I treat as a class. Let's discuss each section you may see in a puzzle module.
Properties
Properties are the metadata of a logic puzzle. The only properties we care about are the puzzle's name and title. This information is set via the Puzzle
members myName
and myTitle
. I use these names instead of the more generic name
and title
to avoid naming collisions.
this.myName = "FiveHouses";
this.myTitle = "Five Houses";
Nouns
The nouns in a logic puzzle must be organized into categories. These categories are called noun types. A puzzle must have at least two noun types. The noun types for our example puzzle are: House, Color, Nationality, Hobby, Pet, and Drink. Note that the names of the noun types are singular, not plural. For this puzzle, there are five nouns for each type. Below is a table of the nouns, where the column header is the noun type. Please keep in mind that each noun type must have the same number of nouns, and there must be at least two nouns per noun type.
Nouns # | House | Color | Nationality | Hobby | Pet | Drink |
1 | 1st | Red | Englishman | Stamps | Dogs | Coffee |
2 | 2nd | Green | Spaniard | Antiques | Snails | Tea |
3 | 3rd | White | Ukrainian | Singing | Fox | Milk |
4 | 4th | Yellow | Norwegian | Gardening | Horse | Juice |
5 | 5th | Blue | Japanese | Cooking | Zebra | Water |
The first column (#) in this table shows the one-based number of the noun. Usually, the order of the nouns within a noun type is not important, but there is one major exception:
If a link references a noun type, then the nouns for that type must be in a logical order.
You'll understand why when you read the section on Links.
Placeholders
While most logic puzzles will give you all of the nouns in the puzzle, some very difficult puzzles may not give you all of the values of the nouns. This means the values must be calculated by one or more rules. Nouns where the initial value is unknown are called placeholders. Usually these values are numeric, such as the number of people who attended a talk in "Astrophysics Conference", or the age of a salesperson in "Dandy Salespeople".
The NounType Class
"use strict";
function NounType(num, name) {
this.num = num + 1;
this.name = name;
this.nouns = [];
this.toString = function () { return this.name; };
this.asString = function () {
return "num=" + Q + this.num + Q + " name=" + Q +
this.name + Q + " nouns=" + Helper.getArrayAsString(this.nouns);
};
this.addNoun = function (name, title) {
let noun = new Noun(this.nouns.length, this, name, title);
this.nouns.push(noun);
return noun;
};
this.getNoun = function (num) {
return this.nouns[num - 1];
};
this.reset = function () {
for (let noun of this.nouns) noun.reset();
};
}
The Noun Class
"use strict";
function Noun(num, type, name, title = null) {
this.num = num + 1;
this.type = type;
this.name = name;
this.title = title === null ? Helper.toTitleCase(name) : title;
this.pairs = [];
this.facts = [];
let oldName = this.name;
let oldTitle = this.title;
this.toString = function () { return this.name; };
this.asString = function () {
return "num=" + Q + this.num + Q + " type=" + Q + this.type + Q +
" name=" + Q + this.name + Q + " title=" + Q + this.title +
Q + " oldName=" + Q + oldName + Q + " oldTitle=" + Q + oldTitle +
Q + " pairs.length=" + Q + this.pairs.length + Q;
};
this.reset = function () {
this.resetValue();
for (let i = 0; i < this.pairs.length; i++) {
this.pairs[i] = null;
}
};
this.updateValue = function (value) {
this.name = value;
this.title = value;
};
this.resetValue = function () {
this.name = oldName;
this.title = oldTitle;
};
}
Adding Nouns
A noun type is created using the Puzzle
method addNounType
. The nouns for each noun type are created using the NounType
method addNoun
. Here is the code for the first noun type House
.
let houses = this.addNounType("House");
let house1 = houses.addNoun("1st");
let house2 = houses.addNoun("2nd");
let house3 = houses.addNoun("3rd");
let house4 = houses.addNoun("4th");
let house5 = houses.addNoun("5th");
Verbs
There are always three verbs in a logic puzzle. The three verbs are: the negative (false) verb, the possible (unknown) verb, and the positive (true) verb. Each verb has a brief text phrase for its name, and a character for its code. Our example logic puzzle has the following verbs.
Verbs # | Type | Name | Code |
-1 | Negative | is not | X |
0 | Possible | may be | |
1 | Positive | is | O |
Here is a brief description of each verb.
- The negative verb has the name "is not", and its code is the 'X' character.
- The possible verb has the name "may be", and its code is the blank character.
- The positive verb has the name "is", and its code is the 'O' character.
The tense for the names of the verbs can be present, past, or future, and only affects the negative and positive verbs. As a general rule, the names of the negative and positive verbs should come from the clues. Here is an example.
- The negative verb can be "is not", "was not", or "will not be".
- The positive verb can be "is", "was", or "will be".
The characters you see in the Grids form are given by the character for each verb. Before you begin solving a logic puzzle, each cell in the grids contains the possible verb, usually represented by a blank character. To solve a logic puzzle, each cell that contains the possible verb must be replaced by either the negative verb ('X'), or the positive verb ('O'). When all of the cells have been properly filled in, then you have the solution to the logic puzzle.
The Verb Class
"use strict";
function Verb(num, name, code, style = null) {
this.num = num;
this.type = Verb.Types[num + 1];
this.name = name;
this.code = code;
if (style === null) {
switch (this.num) {
case -1: style = "color:red;"; break;
case 1: style = "color:black;"; break;
}
}
this.style = style;
this.toString = function () { return this.name; };
this.asString = function () {
return "num=" + Q + this.num + Q + " type=" + Q + this.type +
Q + " name=" + Q + this.name + Q + " code=" + Q + this.code +
Q + " style=" + Q + this.style + Q;
};
this.getCode = function () {
return "<span style=\"" + this.style + "\">" + this.code + "</span>";
};
}
Verb.Types = ["Negative", "Possible", "Positive"];
Verb.MaxVerbs = Verb.Types.length;
let IsNot = new Verb(-1, "is not", "X");
let Maybe = new Verb(0, "may be", " ");
let Is = new Verb(1, "is", "O");
Adding Verbs
The three nouns are always defined for each puzzle module. These three global variables are: IsNot
, Maybe
, and Is
. Since the predefined attributes for these verbs are acceptable, this section is not needed for our puzzle module.
Note: I know I should avoid globals, but I also want to avoid having to prefix each class member with "this
". So this is my compromise.
Links
All of the relationships between two nouns in a puzzle must be expressed as verbs and links. When you examine the clues in a puzzle and the relationship is not obvious, this means the link is "with". For example, the first clue in our example puzzle states: "The Englishman lives in the red house." This clue can be expressed as a fact, where the first noun is "The Englishman", the verb is positive, and the link is "with". Anytime a clue states that one noun is or is not with another noun, just use the default link "with". In other words, the phrase "lives in" really means "with". The data for this fact could be interpreted as: fact(englishman, is, with, red).
For our example puzzle, there are three links: "with", "directly to the right of", and "next to". All of the links use the noun type House. To understand these links, draw a picture of the five houses in this puzzle. You want a picture of five numbered houses in a row, where the 1st house is on the far left, and the 5th house is on the far right. Assume each house is initially colorless.
With
The first clue in our logic puzzle states: "The Englishman lives in the red house." If a clue states that one noun is or is not with another noun, then the default link "with" is used. In less-than-stellar English, the first clue tells us "The Englishman is with the red house." The "with" link is a one-to-one relationship because it means that a noun is with itself. This link is automatically defined for you, and it defaults to the first noun type of the puzzle. For our puzzle, here are the only statements that are true:
- House 1 is with house 1
- House 2 is with house 2
- House 3 is with house 3
- House 4 is with house 4
- House 5 is with house 5
I highly recommend that if a noun type is referenced by the links, then it should be the first noun type you define. With that in mind, I should point out that a logic puzzle may have some links that reference one noun type, and other links that reference another noun type. For example "Small Town Motels" has seven links that reference three different noun types. Now that's a hard logic puzzle! In cases like this, have the most logical noun type be first.
Directly to the Right of
The second link given by the clues is "directly to the right of". This link is in clue 5 "The green house is directly to the right of the white one." Going back to our picture, this means only the following statements are true.
- House 2 is directly to the right of house 1
- House 3 is directly to the right of house 2
- House 4 is directly to the right of house 3
- House 5 is directly to the right of house 4
This type of link has a "one-to-one" relationship because exactly one house is directly to the right of another house.
Next To
The third link given by the clues is "next to". This link is in clues 10, 12, and 14. While some houses are only next to one house, other houses are between two houses. Therefore, this link is not "one-to-one". Can you determine all of the statements that are true for this link?
Comparisons
The "directly to the right of" link is a "more than" comparison because we want to see if noun A is higher than noun B. This comparison is done using the one-based number of the noun. To reduce the number of links in a logic puzzle, use either "more than" or "less than" comparisons, but not both. For example, if a fact stated "A is less than B", you can also say "B is more than A", and vice versa. Below are the links for our example puzzle. The first table displays the links. Here is a brief description for each column.
- # is the zero-based number of the link.
- Noun Type is the noun type referenced by the link.
- Name is the name of the link.
- 1:1 tells use if the link is one-to-one (checked) or not (unchecked).
The subsequent tables display the link grid for each link. This type of grid visually informs us the relationship between noun A (left-most column of row headers) and noun B (top-most row of column headers). If the intersecting cell has a 'O', then the relationship between noun A and noun B is true. If the intersecting cell has a 'X', then the relationship between noun A and noun B is false.
Links # | Noun Type | Name | 1:1 |
0 | House | with | ✓ |
1 | House | directly to the right of | ✓ |
2 | House | next to | |
with House | 1st | 2nd | 3rd | 4th | 5th |
1st | O | X | X | X | X |
2nd | X | O | X | X | X |
3rd | X | X | O | X | X |
4th | X | X | X | O | X |
5th | X | X | X | X | O |
directly to the right of House | 1st | 2nd | 3rd | 4th | 5th |
1st | X | X | X | X | X |
2nd | O | X | X | X | X |
3rd | X | O | X | X | X |
4th | X | X | O | X | X |
5th | X | X | X | O | X |
next to House | 1st | 2nd | 3rd | 4th | 5th |
1st | X | O | X | X | X |
2nd | O | X | O | X | X |
3rd | X | O | X | O | X |
4th | X | X | O | X | O |
5th | X | X | X | O | X |
The Link Class
"use strict";
function Link(num, name, nounType) {
this.num = num;
this.name = name;
this.nounType = nounType;
this.oneToOne = false;
this.f = null;
let ssNeg = true;
let ssPos = true;
this.toString = function () { return this.name; };
this.asString = function () {
return "num=" + Q + this.num + Q + " name=" + Q + this.name +
Q + " nounType=" + Q + this.nounType + Q + " oneToOne=" +
Q + this.oneToOne + Q + " ssNeg=" + Q + ssNeg + Q +
" ssPos=" + Q + ssPos + Q;
};
this.update = function () {
this.oneToOne = isOneToOne(this);
ssNeg = inSameSlot(this, IsNot);
ssPos = inSameSlot(this, Is);
};
this.canBeWith = function (verb) {
return verb.num < 0 ? ssNeg : ssPos;
};
function isOneToOne(link) {
let flag = false;
let slots = link.nounType.nouns;
for (let slot1 of slots) {
let cnt = 0;
for (let slot2 of slots) {
let verb = link.f(slot1, slot2);
if (verb.num === 1 && ++cnt > 1) return flag;
}
}
flag = true;
return flag;
}
function inSameSlot(link, verb) {
let slots = link.nounType.nouns;
for (let slot of slots) {
if (link.f(slot, slot) === verb) return true;
}
return false;
}
}
let With = null;
Adding Links
The first link "with" is defined as a global, so it is always available for each puzzle module. Each link is created via the Puzzle
method addLink
. Here is the code for the other links in our puzzle.
let directlyRightOf = this.addLink("directly to the right of", houses);
directlyRightOf.f = SmartLink.getIsMoreBy(1);
let nextTo = this.addLink("next to", houses);
nextTo.f = SmartLink.getIsNextTo();
Note: The function assigned to each link via the f
member is given by a method in the SmartLink
static class. See the section on Smart Links for more information. If you cannot find what you want in the SmartLink
class, you will need to "roll your own".
Facts
The facts are the static relationships between two nouns. An example is "A is next to B." A fact has the following form.
"Noun 1 Verb Link Noun 2.", where (1) the verb is positive or negative, and (2) the verb and link is the relationship between the two nouns.
The first clue in our example puzzle can be expressed directly as a fact: "The Englishman lives in the red house." In fact (pun intended), what makes this puzzle unique is that each clue is a fact. Here are the facts for this puzzle.
Facts # | X | Hits | Name |
1 | ✓ | 0 | The Englishman is in the red house (clue 1). |
2 | ✓ | 0 | The Spaniard's pet is dogs (clue 2). |
3 | ✓ | 0 | Coffee is drunk in the green house (clue 3). |
4 | ✓ | 0 | The Ukrainian's favorite drink is tea (clue 4). |
5 | ✓ | 0 | The green house is directly to the right of the white house (clue 5). |
6 | ✓ | 0 | The man who's hobby is stamps owns snails (clue 6). |
7 | ✓ | 0 | The man who's hobby is antiques is in the yellow house (clue 7). |
8 | ✓ | 0 | The man in the 3rd house drinks milk (clue 8). |
9 | ✓ | 0 | The Norwegian is in the 1st house (clue 9). |
10 | ✓ | 0 | The man who's hobby is singing is next to the man with the fox (clue 10). |
11 | ✓ | 0 | The man who's hobby is gardening drinks juice (clue 11). |
12 | ✓ | 0 | The man who's hobby is antiques is next to the man with the horse (clue 12). |
13 | ✓ | 0 | The Japanese man's hobby is cooking (clue 13). |
14 | ✓ | 0 | The Norwegian is next to the blue house (clue 14). |
Here is a brief description for each column.
- # is the one-based number of the fact.
- X tells you if the fact is enabled (checked) or disabled (unchecked).
- Hits is the number of times a fact is referenced.
- Name is the text of the fact.
Types of Facts
The types of facts are given below. While the first type of fact yields only one mark, the other types of facts usually produce more than one mark.
Type 1
A type 1 fact has the default link "with". Only a type 1 fact has "with" as the link. It is the easiest to process, and the easiest to notice when a mark contradicts it. Most of the facts in our example puzzle "Five Houses" are type 1 facts.
I must point out that both nouns in a type 1 fact cannot have the same noun type. Why? Because in any logic grid puzzle, two nouns of the same noun type can never be together! If you had the fact with two first names such as "Abe is with Bob", this would be a violation. And if you had the fact "Abe is not with Bob", this would simply be redundant.
Type 2
A type 2 fact has exactly one noun where its noun type matches the noun type of the link. It is slightly harder to process, and is harder to catch when a mark contradicts it. This puzzle, along with most puzzles, does not have this type of fact.
A logic puzzle that does have facts of type 2 is "Lucky Streets". In this puzzle, fact 15 states "She found the quarter earlier than Friday." This means the quarter was not found on Friday or Saturday. The quarter has the noun type "Coin", while the link "earlier than" and Friday both have the noun type "Day". In this puzzle, facts 16 and 17 are type 2 facts as well.
Again, I must point out that both nouns in a type 2 fact cannot have the same noun type. Why? Because this is like saying "Thursday is earlier than Friday." While this may be factually true, this is already defined within the link "earlier than".
Type 3
A type 3 fact has the same noun type for both nouns, but this noun type is different from the noun type of the link. A fact of type 3 from our example puzzle is fact 5: "The green house is directly to the right of the white one." The green house and the white house have the noun type "Color", and the link "directly to the right of" has the noun type "House".
Type 4
A type 4 fact is where the noun types for both nouns and the link are all different. From our example puzzle, facts 10, 12, and 14 are facts of type 4. Let's examine fact 10: "The man who sings lives next to the man with the fox." The man who sings has the noun type "Hobby". The link "next to" has the noun type "House". And the man with the fox has the noun type "Pet".
An important issue concerning logic puzzles has to do with whether two objects given in a clue are distinct, and therefore cannot be paired. For type 1 facts, the answer is explicitly given. For the other types of facts, usually the link will let you know whether this is true or not. If a fact states: "Abe is in a room next to the room the cat is in", then you know that Abe can never be in the same room as the cat.
But if the fact states: "Abe is in a room that is not next to the room the cat is in", it may be possible that Abe is in the same room as the cat. My suggestion is that if the clue does not say otherwise, assume that the two nouns given in the clue are distinct.
The Fact Class
"use strict";
function Fact(num, name, noun1, verb, link, noun2, initEnabled = true) {
this.num = num + 1;
this.type = 0;
this.name = name;
this.noun1 = noun1;
this.verb = verb;
this.link = link;
this.noun2 = noun2;
this.enabled = initEnabled === true;
this.hits = 0;
this.initEnabled = this.enabled;
if (link.num === 0)
this.type = 1;
else if (noun1.type === link.nounType || noun2.type === link.nounType)
this.type = 2;
else if (noun1.type === noun2.type)
this.type = 3;
else if (this.noun1.type !== noun2.type)
this.type = 4;
this.toString = function () { return this.name; };
this.asString = function () {
return "num=" + Q + this.num + Q + " type=" + Q + this.type +
Q + " noun1=" + Q + this.name + Q + " noun1=" +
Q + this.noun1 + Q + " verb=" + Q + this.verb +
Q + " link=" + Q + this.link + Q + " noun2=" +
Q + this.noun2 + Q + " enabled=" + Q + this.enabled +
Q + " hits=" + Q + this.hits + Q + " initEnabled=" +
Q + this.initEnabled + Q;
};
this.reset = function () {
this.enabled = this.initEnabled;
this.hits = 0;
};
this.msgBasedOn = function () { return "fact " + this.num; };
this.msgDisabled = function () { return "fact " + this.num + " is disabled."; };
}
Adding Facts
This logic puzzle is unique in that each clue corresponds to exactly one fact. This is usually not the case! Each fact is created via the Puzzle
method addFact
. Here is the first fact.
this.addFact("1", englishman, Is, With, red, "The Englishman lives in the red house.");
Note: As you can see in this fact, the variables Is
and With
do not need to be prefixed by the this
keyword because they are globals. I wish "this
" was not an issue.
This method appears very straightforward. But I must tell you this method has overloads where you can enter more than one fact at a time. So let's discuss what those overloads are in another article.
Validating Facts
Before the Mystery Master solves a logic puzzle, it first validates the logic puzzle by looking for various logic errors. The Puzzle
method that validates the puzzle is appropriately named validate
. Here are some reasons a fact is invalid.
- The fact's verb is the possible verb ("maybe"). It must be either the positive verb ("is") or the negative verb ("is not").
- Both nouns in the fact are the same. The nouns in a fact must be different.
- The fact's link is "with", but both nouns have the same type. This is like saying "Bob is not Abe", or "Abe is Bob". For logic grid puzzles, two nouns of the same type are never together anyway.
- The fact's link is not "with", but both nouns have the same type as the link. For example "The 2nd person in line is ahead of the 4th person in line.", may make sense, but this is a relationship, not a fact! This statement is exactly what the "ahead of" link is suppose to define.
Rules
A rule is a conditional relationship between two or more nouns such as "If A is next to B, then C is not next to D." Rules are needed when facts cannot represent the clues in a logic puzzle. Since our example puzzle does not have rules, below is the puzzle module for the puzzle "All Tired Out".
function AllTiredOut() {
"use strict";
this.myName = "AllTiredOut";
this.myTitle = "All Tired Out";
let slots = this.addNounType("Order");
let slot1 = slots.addNoun("1st");
let slot2 = slots.addNoun("2nd");
let slot3 = slots.addNoun("3rd");
let slot4 = slots.addNoun("4th");
let slot5 = slots.addNoun("5th");
let names = this.addNounType("Customer");
let ethan = names.addNoun("Ethan");
let grace = names.addNoun("Grace");
let jeff = names.addNoun("Jeff");
let lisa = names.addNoun("Lisa");
let marge = names.addNoun("Marge");
let wants = this.addNounType("Wanted");
let alignment = wants.addNoun("alignment");
let chains = wants.addNoun("chains");
let jack = wants.addNoun("jack");
let shocks = wants.addNoun("shock absorbers", "Shocks");
let tires = wants.addNoun("tires");
IsNot.name = "was not";
Is.name = "was";
let justAhead = this.addLink("just ahead of", slots);
justAhead.f = SmartLink.getIsLessBy(1);
let threeAhead = this.addLink("three places ahead of", slots);
threeAhead.f = SmartLink.getIsLessBy(3);
let nextTo = this.addLink("next to", slots);
nextTo.f = SmartLink.getIsNextTo();
this.sayFact = (noun1, verb, link, noun2) => {
let msg = noun1.name + " " + verb.name + " " + link.name + " " + noun2.name;
let lname = link === With ? " " : " " + link.name + " ";
switch (noun1.type.num) {
case 1:
msg = "The " + noun1.name + " person in line ";
switch (noun2.type.num) {
case 1: break;
case 2:
msg += verb.name + lname + noun2.name;
break;
case 3:
msg += (verb === Is ? "did" : "did not") +
" buy the " + noun2.name;
break;
}
break;
case 2:
msg = noun1.name + " ";
switch (noun2.type.num) {
case 1:
msg += verb.name + lname + "the " +
noun2.name + " person in line";
break;
case 2: break;
case 3:
if (link === With)
msg += (verb === Is ? "did" : "did not") +
" buy the " + noun2.name;
else
msg += verb.name + " " + link.name +
" the person who bought the " + noun2.name;
break;
}
break;
case 3:
msg = "The person who bought the " + noun1.name +
" " + verb.name + lname;
switch (noun2.type.num) {
case 1: break;
case 2:
msg += noun2.name;
break;
case 3:
msg += "the one who bought the " + noun2.name;
break;
}
break;
}
return msg + ".";
};
this.addFact("1", [ethan, slot3, chains], IsNot, With);
this.addFact("2", jack, Is, justAhead, lisa);
this.addFact("3", slot2, IsNot, With, [ ethan, jeff ]);
this.addFact("4", tires, Is, threeAhead, alignment);
this.addFact("6", jeff, Is, justAhead, shocks);
let rule1 = this.addRule("5", "Marge wasn't the second of the three women in line.");
rule1.f = SmartRule.getIsNotBetween(this, rule1, slots, marge, grace, lisa);
let rule2 = this.addRule("7", "Grace stood next to at least one man in line.");
rule2.f = SmartRule.getIsRelated(this, rule2, grace, nextTo, [ethan, jeff]);
this.answer = [ [ 4, 1, 2, 3, 0 ], [ 1, 4, 2, 3, 0 ] ];
}
AllTiredOut.prototype = new Puzzle();
AllTiredOut.prototype.constructor = AllTiredOut;
puzzle = new AllTiredOut();
In this puzzle module, you can see that I set the names for the verbs to be past tense.
IsNot.name = "was not";
Is.name = "was";
For this logic puzzle, clues 5 and 7 need to be expressed as rules. Here are the rules for this puzzle.
Rules # | X | Hits | Name |
1 | ✓ | 0 | Marge wasn't the second of the three women in line (clue 5). |
2 | ✓ | 0 | Grace stood next to at least one man in line (clue 7). |
Here is a brief description for each column:
- # is the one-based number of the rule.
- X tells you if the rule is enabled (checked) or disabled (unchecked).
- Hits is the number of times a rule is referenced.
- Name is the text of the rule.
The Rule Class
"use strict";
function Rule(num, name, nouns = null, initEnabled = true) {
this.num = num + 1;
this.name = name;
this.nouns = nouns === null ? [] : nouns;
this.enabled = initEnabled === true;
this.hits = 0;
this.initEnabled = this.enabled;
this.f = null;
this.toString = function () { return this.name; };
this.asString = function () {
return "num=" + Q + this.num + Q + " name=" + Q + this.name +
Q + " nouns=" + Helper.getArrayAsString(this.nouns) +
" enabled=" + Q + this.enabled + Q + " hits=" + Q +
this.hits + Q + " initEnabled=" + Q + this.initEnabled + Q;
};
this.reset = function () {
this.enabled = this.initEnabled;
this.hits = 0;
};
}
Adding Rules
Here are the rules that will satisfy clues 5 and 7.
let rule1 = this.addRule("5", "Marge wasn't the second of the three women in line.");
rule1.f = SmartRule.getIsNotBetween(this, rule1, slots, marge, grace, lisa);
let rule2 = this.addRule("7", "Grace stood next to at least one man in line.");
rule2.f = SmartRule.getIsRelated(this, rule2, grace, nextTo, [ethan, jeff]);
Rules, along with links, require programming. The function f
for each rule is provided by a method in the SmartRule
static class. See the section on Smart Rules for more information. A rule usually does something based on the marks, and returns a status code. The status code is either negative for a violation, or zero for success. A rule may perform one or more of the following tasks.
Enforce Violations
A violation occurs when a mark contradicts the clues of a puzzle. A mark that violates the clues is called a contradiction. This should only happen when assumptions are made. A violation means the program should undo the last assumption, and make another one. If an assumption was not made, this is a fatal logic error, and the program will stop solving the puzzle. In the puzzle "All Tired Out", if a mark created the situation where Grace was first and a woman was second, this mark would contradict the clues. When a rule encounters this, it must inform the program of the violation.
Trigger Marks
A rule that examines the current mark to enter additional marks is called a trigger. The status of a trigger is the status of the submitted mark. If there are no problems with the mark, the status is zero. If there is a problem with the mark, the status is negative, and is returned immediately. If the mark entered by a trigger is rejected, this is the same as a rule violation. If the trigger was successful, the current rule can continue, and additional rules can be invoked.
For the logic puzzle "All Tired Out", a rule must look for a situation such as "If no man can be 2nd in line, then Grace cannot be 1st in line." When this situation is found, the rule enters 'X' for 1st and Grace. In general, rule violations should be handled first, followed by triggers.
Updating Placeholders
Some logic puzzles may not give you all of the values of the nouns. This means the values must be calculated by a rule. Nouns where the initial value is unknown are called placeholders. Usually these values are numeric, such as the number of people who attended a talk in "Astrophysics Conference", or the age of a salesperson in "Dandy Salespeople". Rules that update placeholders can be quite complex.
To summarize, rules are laws that are specific to a logic puzzle. The laws for solving a logic puzzle will be discussed in a future article.
Solution
This is the encoded solution to the logic puzzle, but is optional. If you know the solution, you can encode it here. See if you can "decode" this.
this.answer = [ [ 3, 4, 0, 2, 1 ], [ 3, 2, 0, 1, 4 ],
[ 1, 2, 0, 3, 4 ], [ 2, 3, 1, 0, 4 ], [ 4, 1, 2, 3, 0 ] ];
Helper
The Helper
static class defines global variables and helpful methods. This class is referenced by several of my classes. Though global variables and methods are discouraged, below are some of the globals defined in this module.
Q
is the double quote character as a string. NL
is the new line character given by the escaped sequence "\n". print(msg)
is a method that prints the given message to the browser's console window.
The Helper Class
"use strict";
const Q = "\"";
const NL = "\n";
let MTN = "";
function print(msg) {
console.log(MTN + msg);
}
function Helper() {
throw new Error("Helper is a static class!");
}
Helper.getBoolean = function (val = false) {
if (typeof val === "boolean") return val;
if (Helper.isNumber(val)) return val !== 0;
if (typeof val !== "string") return false;
val = val.toLowerCase();
return val === "true";
};
Helper.isNumber = function (val) {
return typeof val === "number" && !isNaN(val);
};
Helper.toInt = function (str = null) {
return str === null ? 0 : parseInt(str);
};
Helper.isInt = function (str = null) {
if (str === null) return false;
let val = typeof str === 'string' ? parseInt(str) : str;
if (val !== val) return false;
return parseFloat(val) === parseInt(val);
};
Helper.isNotDivisibleBy = function (noun = null, num) {
if (noun === null || !Helper.isInt(noun.name)) return false;
let val = Helper.toInt(noun.name);
return val % num !== 0;
};
Helper.getTimestamp = function () {
let date = new Date();
return new Date(date.getTime()).toLocaleString() + " " + date.getMilliseconds();
};
Helper.formatDT = function (date) {
let yy = date.getFullYear();
let mm = date.getMonth() + 1;
let dd = date.getDate();
let hh = date.getHours();
let mi = date.getMinutes();
let ss = date.getSeconds();
let ms = date.getMilliseconds();
let msg = "" + yy + "-" + (mm <= 9 ? "0" + mm : mm) + "-" +
(dd <= 9 ? "0" + dd : dd) +
" " + (hh <= 9 ? "0" + hh : hh) + ":" + (mi <= 9 ? "0" + mi : mi) +
":" + (ss <= 9 ? "0" + ss : ss) + "." + (ms <= 9 ? "00" +
ms : (ms <= 99 ? "0" + ms : ms));
return msg;
};
Helper.getMsgElapsedTime = function (time1 = null, time2 = null) {
if (time1 === null || time2 === null) return "";
let elapsedTime = time2.getTime() - time1.getTime();
return "" + elapsedTime + " ms.";
};
Helper.getStartedMsg = function (time1) {
return "I started solving at " + Helper.formatDT(time1) + ".";
};
Helper.getStoppedMsg = function (time1, time2) {
return "I stopped solving at " + Helper.formatDT(time2) +
" in " + Helper.getMsgElapsedTime(time1, time2);
};
Helper.getSolutionMsg = function (time1, time2, numSolutions) {
return "I have " + (numSolutions === 1 ?
"a solution" : numSolutions + " solutions") + " at " +
Helper.formatDT(time2) + " in " + Helper.getMsgElapsedTime(time1, time2);
};
Helper.getMsgAsOneLine = function (msg, sep = " ") {
return msg.replace(NL, sep);
};
Helper.toTitleCase = function (str = null) {
if (str === null) return str;
let n = str.length;
if (n === 0) return str;
let seps = " \t-";
let flag = true;
let chars = Array.from(str);
for (let i = 0; i < n; i++) {
if (seps.indexOf(chars[i]) > -1)
flag = true;
else if (flag === true) {
chars[i] = chars[i].toUpperCase();
flag = false;
}
}
let res = chars.join("");
return res;
};
Helper.getArrayAsString = function (objs, sep0 = ",") {
let msg = "[", sep = "";
for (let obj of objs) {
msg += sep + obj.toString();
sep = sep0;
}
return msg + "]";
};
Helper.sayArray2D = function (a = null) {
let msg = "";
if (a === null) return msg;
for (let i1 = 0; i1 < a.length; i1++) {
let line = "", sep = "";
for (let i2 = 0; i2 < a[i1].length; i2++) {
line += sep + a[i1][i2];
sep = ",";
}
msg += line + NL;
}
print(msg);
};
Helper.getArray2D = function (d1, d2, v) {
if (v === undefined) v = 0;
let a = new Array(d1);
for (let i1 = 0; i1 < d1; i1++) {
a[i1] = new Array(d2);
for (let i2 = 0; i2 < d2; i2++) {
a[i1][i2] = v;
}
}
return a;
};
Helper.solveEquations = function (a) {
let n = a[0].length - 1;
let x = new Array(n);
for (let i = 0; i < n - 1; i++) {
let p = 0;
for (p = i; p < n; p++) {
if (a[p][i] !== 0) break;
}
if (p === n) return x;
if (p !== i) {
for (let c = 0; c < n + 1; c++) {
let m = a[p][c];
a[p][c] = a[i][c];
a[i][c] = m;
}
}
for (let j = i + 1; j < n; j++) {
let m = a[j][i] / a[i][i];
for (let c = 0; c < n + 1; c++) {
a[j][c] = a[j][c] - m * a[i][c];
}
}
}
if (a[n - 1][n - 1] === 0) return x;
x[n - 1] = a[n - 1][n] / a[n - 1][n - 1];
for (let i = n - 2; i >= 0; i--) {
let s = 0.0;
for (let j = i + 1; j < n; j++) {
s += a[i][j] * x[j];
}
x[i] = (a[i][n] - s) / a[i][i];
}
return x;
};
Helper.getChartAsText = function (puzzle, chartCol1, isSolution) {
let txt = "";
if (puzzle === null) return txt;
let caption = isSolution ? "Solution" : "Chart";
txt = caption + NL;
let t = chartCol1;
let nounTypes = puzzle.nounTypes;
let nounType1 = nounTypes[t];
let maxNounTypes = nounTypes.length;
let maxNouns = nounType1.nouns.length;
let w = 20;
let pad = " ".repeat(w);
let tmp;
let i = 0, j = 0, k = 0;
for (j = 0; j < maxNounTypes; j++) {
if (k === t)++k;
let nounType = (j === 0 ? nounType1 : nounTypes[k++]);
tmp = nounType.name + pad;
txt += tmp.substring(0, w);
}
txt += NL;
for (i = 0; i < maxNouns; i++) {
k = 0;
for (j = 0; j < maxNounTypes; j++) {
if (k === t) ++k;
let noun1 = nounType1.nouns[i];
tmp = " ";
if (j === 0)
tmp =noun1.title;
else {
let noun2 = Puzzle.getPairNoun(noun1, nounTypes[k]);
if (noun2 !== null) tmp = noun2.title;
++k;
}
tmp += pad;
txt += tmp.substring(0, w);
}
txt += NL;
}
return txt;
};
Smart Links
The SmartLink
static class defines methods that return a function for the links in a puzzle module.
The SmartLink Class
"use strict";
function SmartLink() {
throw new Error("SmartLink is a static class!");
}
SmartLink.getIsWith = function () {
return (noun1, noun2) => noun1.num === noun2.num ? Is : IsNot;
};
SmartLink.getIsLessThan = function (n = 0) {
return (noun1, noun2) => noun1.num < noun2.num - n ? Is : IsNot;
};
SmartLink.getIsLessBy = function (n) {
return (noun1, noun2) => noun1.num === noun2.num - n ? Is : IsNot;
};
SmartLink.getIsMoreThan = function (n = 0) {
return (noun1, noun2) => noun1.num > noun2.num + n ? Is : IsNot;
};
SmartLink.getIsMoreBy = function (n) {
return (noun1, noun2) => noun1.num === noun2.num + n ? Is : IsNot;
};
SmartLink.getIsNextTo = function () {
return (noun1, noun2) => (noun1.num === noun2.num - 1) ||
(noun1.num === noun2.num + 1) ? Is : IsNot;
};
SmartLink.getIsOffsetBy = function (n) {
return (noun1, noun2) => (noun1.num === noun2.num - n) ||
(noun1.num === noun2.num + n) ? Is : IsNot;
};
SmartLink.getIsOutsideOf = function (n) {
return (noun1, noun2) => (noun1.num < noun2.num - n) ||
(noun1.num > noun2.num + n) ? Is : IsNot;
};
SmartLink.getHasRatio = function (n1, n2) {
return (noun1, noun2) => (n1 * noun1.num === n2 * noun2.num) ? Is : IsNot;
};
Smart Rules
The SmartRule
static class defines methods that return a function for the rules in a puzzle module.
The SmartRule Class
"use strict";
function SmartRule() {
throw new Error("SmartRule is a static class!");
}
SmartRule.getMatchAtLeastOne = function (puzzle, rule, noun1, nouns2) {
function canBeWith2(noun1, nouns2) {
for (let noun2 of nouns2) {
if (noun1.type === noun2.type) continue;
if (Puzzle.getPairNounNum(noun1, noun2.type) === noun2.num) return true;
if (puzzle.canBeWith(noun1, noun2)) return true;
}
return false;
}
function isOnlyNoun(noun1, nouns2) {
let noun = null;
for (let noun2 of nouns2) {
if (noun1.type === noun2.type) continue;
if (Puzzle.getPairNoun(noun1, noun2.type) === noun2) return null;
if (!puzzle.canBeWith(noun1, noun2)) continue;
if (noun !== null) return null;
noun = noun2;
}
return noun;
}
function matchAtLeastOne(mark) {
let rs = 0;
if (!canBeWith2(noun1, nouns2)) return -1;
let noun2 = isOnlyNoun(noun1, nouns2);
if (noun2 !== null) {
let msg = noun1.name + " must be with " + noun2.name + ".";
rs = solver.addMarkByRule(mark, rule, ' ', noun1, Is, noun2, msg);
}
for (let nounType of puzzle.nounTypes) {
if (noun1.type === nounType) continue;
for (let nounX of nounType.nouns) {
if (puzzle.getGridVerb(noun1, nounX) === IsNot) continue;
let ok = false;
for (let noun of nouns2) {
if (noun.type === nounType || puzzle.getGridVerb(noun, nounX)
!== IsNot) {
ok = true;
break;
}
}
if (!ok) {
let msg = "SmartRule.matchAtLeastOne:
No item in list can be with " + nounX.name + ".";
rs = solver.addMarkByRule
(mark, rule, ' ', noun1, IsNot, nounX, msg);
if (rs !== 0) return rs;
}
}
}
return rs;
}
return matchAtLeastOne;
};
SmartRule.getMatchOneToExactlyOne = function (puzzle, rule, nouns1, nouns2) {
function getNumMatches(nouns1, nouns2) {
let cnt = 0;
for (let noun1 of nouns1) {
for (let noun2 of nouns2) {
if (noun2.type === noun1.type) continue;
if (Puzzle.isPair(noun1, noun2)) ++cnt;
}
}
return cnt;
}
function matchOneToExactlyOne(mark) {
let rs = 0;
let n1 = nouns1.length;
let n2 = nouns2.length;
let counts = new Array(n1);
let scanFlag = true;
let i1 = -1;
let i2 = -1;
for (let i = 0; i < n1; i++) {
let noun1 = nouns1[i];
counts[i] = 0;
for (let j = 0; j < n2; j++) {
let noun2 = nouns2[j];
if (noun2.type === noun1.type) continue;
if (Puzzle.isPair(noun1, noun2)) {
scanFlag = false;
break;
}
if (puzzle.canBeWith(noun1, noun2)) {
if (++counts[i] > 1) {
scanFlag = false;
break;
}
i2 = j;
}
}
if (!scanFlag) break;
if (counts[i] === 1) {
if (i1 !== -1) {
scanFlag = false;
break;
}
i1 = i;
}
}
if (scanFlag) {
if (i1 !== -1 && i2 !== -1) {
let noun1 = nouns1[i1];
let noun2 = nouns2[i2];
let msg = noun1.name + " must be with " + noun2.name + ".";
rs = solver.addMarkByRule(mark, rule, ' ', noun1, Is, noun2, msg);
if (rs !== 0) return rs;
}
else {
for (let i = 0; i < n1; i++) {
if (counts[i] !== 0) {
scanFlag = false;
break;
}
}
if (scanFlag) return -1;
}
}
if (getNumMatches(nouns1, nouns2) > 1) return -1;
return rs;
}
return matchOneToExactlyOne;
};
SmartRule.getMatchOneToOne = function (puzzle, rule, nouns1, nouns2) {
let listLength = nouns1.length;
let grid = Helper.getArray2D(listLength, listLength, null);
function matchOneToOne(mark) {
let rs = 0;
for (let row = 0; row < nouns1.length; row++) {
let noun1 = nouns1[row];
for (let col = 0; col < nouns2.length; col++) {
let noun2 = nouns2[col];
grid[row][col] = puzzle.getGridVerb(noun1, noun2);
if (noun1.type === noun2.type) grid[row][col] = IsNot;
}
}
for (let row = 0; row < nouns1.length; row++) {
let noun1 = nouns1[row];
let cnt = 0;
for (let col = 0; col < nouns2.length; col++) {
if (grid[row][col] === Is)++cnt;
}
if (cnt > 1) {
return 1;
}
if (cnt === 1) {
for (let col = 0; col < nouns2.length; col++) {
let noun2 = nouns2[col];
if (grid[row][col] !== Maybe) continue;
let msg = "Only one of each noun in list2
can be with one of each noun in list1.";
rs = solver.addMarkByRule
(mark, rule, 'a', noun1, IsNot, noun2, msg);
if (rs !== 0) return rs;
grid[row][col] = IsNot;
}
}
}
for (let col = 0; col < nouns2.length; col++) {
let noun2 = nouns2[col];
let cnt = 0;
for (let row = 0; row < nouns1.length; row++) {
if (grid[row][col] === Is) ++cnt;
}
if (cnt > 1) {
return 1;
}
if (cnt === 1) {
for (let row = 0; row < nouns1.length; row++) {
let noun1 = nouns1[row];
if (grid[row][col] !== Maybe) continue;
let msg = "Only one of each noun in list1
can be with one of each noun in list2.";
rs = solver.addMarkByRule
(mark, rule, 'b', noun1, IsNot, noun2, msg);
if (rs !== 0) return rs;
grid[row][col] = IsNot;
}
}
}
for (let row = 0; row < nouns1.length; row++) {
let noun1 = nouns1[row];
let i = -1;
let cnts = [0, 0, 0];
for (let col = 0; col < nouns2.length; col++) {
let verb = grid[row][col];
cnts[verb.num + 1] += 1;
if (verb.num === 0) i = col;
}
if (cnts[0] === listLength) {
return 1;
}
if (cnts[0] === listLength - 1 && cnts[1] === 1 && cnts[2] === 0) {
let noun2 = nouns2[i];
let msg = "Only one noun in list2 is available for noun1.";
rs = solver.addMarkByRule(mark, rule, 'c', noun1, Is, noun2, msg);
if (rs !== 0) return rs;
grid[row][i] = Is;
}
}
for (let col = 0; col < nouns2.length; col++) {
let noun2 = nouns2[col];
let i = -1;
let cnts = [0, 0, 0];
for (let row = 0; row < nouns1.length; row++) {
let verb = grid[row][col];
cnts[verb.num + 1] += 1;
if (verb.num === 0) i = row;
}
if (cnts[0] === listLength) {
return 1;
}
if (cnts[0] === listLength - 1 && cnts[1] === 1 && cnts[2] === 0) {
let noun1 = nouns1[i];
let msg = "Only one noun in list1 is available for noun2.";
rs = solver.addMarkByRule(mark, rule, 'd', noun1, Is, noun2, msg);
if (rs !== 0) return rs;
grid[i][col] = Is;
}
}
return rs;
}
return matchOneToOne;
};
SmartRule.getMatchOneList = function (puzzle, rule, nouns1, array2) {
function getListIndex(nounX, lists) {
let rs = -1;
let idx = rs;
for (let list of lists) {
++idx;
for (let noun of list) {
if (noun === nounX) return idx;
}
}
return rs;
}
function hasCoverage(nouns1, nouns2) {
let rs = true;
let n = nouns1.length;
let nouns = [];
let nbad = 0;
for (let noun1 of nouns1) {
let cnt = 0;
for (let noun2 of nouns2) {
let verb = puzzle.getGridVerb(noun1, noun2);
if (verb === Is) return rs;
if (verb === IsNot) continue;
++cnt;
if (!nouns.includes(noun2)) nouns.push(noun2);
}
if (cnt === 0) ++nbad;
}
rs = (nouns.length === 0 || nbad === n) || (nouns.length >= n && nbad === 0);
return rs;
}
function matchOneList(mark) {
let rs = 0;
if (mark.verb === Is) {
let nounX1 = null;
let nounX2 = null;
let idx2 = -1;
for (let noun of nouns1) {
if (mark.noun1 === noun) {
nounX1 = mark.noun1;
nounX2 = mark.noun2;
idx2 = getListIndex(nounX2, array2);
}
else if (mark.noun2 === noun) {
nounX1 = mark.noun2;
nounX2 = mark.noun1;
idx2 = getListIndex(nounX2, array2);
}
if (idx2 > -1) break;
}
if (idx2 > -1) {
let idx = -1;
for (let list2 of array2) {
if (++idx === idx2) continue;
for (let noun2 of list2) {
if (noun2 === nounX2) continue;
for (let noun1 of nouns1) {
if (noun1 === nounX1) continue;
let msg = noun1.name + " is not with " + noun2.name + ".";
rs = solver.addMarkByRule(mark, rule, 'a',
noun1, IsNot, noun2, msg);
if (rs !== 0) return rs;
}
}
}
}
}
for (let nouns2 of array2) {
if (hasCoverage(nouns1, nouns2)) continue;
for (let noun1 of nouns1) {
for (let noun2 of nouns2) {
let msg = noun1.name + " is not with " + noun2.name + ".";
rs = solver.addMarkByRule(mark, rule, 'a', noun1, IsNot, noun2, msg);
if (rs !== 0) return rs;
}
}
}
return rs;
}
return matchOneList;
};
SmartRule.getIsNotBetween = function (puzzle, rule, nounType, noun1, noun2, noun3) {
function isNotBetween(mark) {
let rs = 0;
let slotA = (noun1.type === nounType) ?
noun1.num : Puzzle.getPairNounNum(noun1, nounType);
let slotB = (noun2.type === nounType) ?
noun2.num : Puzzle.getPairNounNum(noun2, nounType);
let slotC = (noun3.type === nounType) ?
noun3.num : Puzzle.getPairNounNum(noun3, nounType);
if (slotA > 0 && slotB > 0 && slotC > 0) {
if (slotB < slotA && slotA < slotC) return -1;
if (slotC < slotA && slotA < slotB) return -1;
return rs;
}
let n = nounType.nouns.length;
let ch = ' ';
let noun = null;
let i1 = 0, i2 = 0;
if (slotA > 0 && slotB > slotA) {
ch = 'a'; noun = noun3; i1 = 0; i2 = slotA - 1;
}
if (slotB > 0 && slotA > slotB) {
ch = 'b'; noun = noun3; i1 = slotA; i2 = n;
}
else if (slotA > 0 && slotC > slotA) {
ch = 'c'; noun = noun2; i1 = 0; i2 = slotA - 1;
}
else if (slotC > 0 && slotA > slotC) {
ch = 'd'; noun = noun2; i1 = slotA; i2 = n;
}
else if (slotB > 0 && slotC > slotB) {
ch = 'e'; noun = noun1; i1 = slotB; i2 = slotC - 1;
}
else if (slotC > 0 && slotB > slotC) {
ch = 'f'; noun = noun1; i1 = slotC; i2 = slotB - 1;
}
let msg = noun1.name + " is not between " + noun2.name +
" and " + noun3.name + ".";
for (let i = i1; i < i2; i++) {
let slot = nounType.nouns[i];
if (puzzle.getGridVerb(noun, slot) === IsNot) continue;
rs = solver.addMarkByRule(mark, rule, ch, noun, IsNot, slot, msg);
if (rs !== 0) return rs;
}
return rs;
}
return isNotBetween;
};
SmartRule.getIsRelated = function (puzzle, rule, noun1, link, nouns2) {
function isRelated(mark) {
let rs = 0;
let slots = link.nounType;
let slot1 = (noun1.type === slots) ? noun1 : Puzzle.getPairNoun(noun1, slots);
if (slot1 !== null) {
let nounB, slotB;
let ok;
ok = false;
for (let noun2 of nouns2) {
let slot = (noun2.type === slots) ?
noun2 : Puzzle.getPairNoun(noun2, slots);
if (slot === null || link.f(slot1, slot) === Is) { ok = true; break; }
}
if (!ok) return -1;
ok = false;
for (let slot of slots.nouns) {
if (link.f(slot1, slot) !== Is) continue;
for (let noun of nouns2) {
nounB = Puzzle.getPairNoun(slot, noun.type);
if (nounB === null || nounB === noun) { ok = true; break; }
}
if (ok) break;
}
if (!ok) return -1;
ok = false;
for (let slot of slots.nouns) {
if (link.f(slot1, slot) !== Is) continue;
for (let noun of nouns2) {
if (puzzle.getGridVerb(slot, noun) !== IsNot) { ok = true; break; }
}
if (ok) break;
}
if (!ok) return -1;
nounB = null; slotB = null;
let cnt = 0;
for (let slot of slots.nouns) {
if (link.f(slot1, slot) !== Is) continue;
for (let noun of nouns2) {
let slotX = Puzzle.getPairNoun(noun, slots);
if (slotX === slot) {
cnt = 2;
break;
}
if (slotX !== null) continue;
if (puzzle.getGridVerb(noun, slot) === Maybe) {
if (++cnt > 1) break;
nounB = noun; slotB = slot;
}
}
if (cnt > 1) break;
}
if (cnt === 1) {
let msg = nounB.name + " must be with " + slotB.name + ".";
rs = solver.addMarkByRule(mark, rule, 'a', nounB, Is, slotB, msg);
if (rs !== 0) return rs;
}
}
if (slot1 === null) {
for (let slotX of slots.nouns) {
if (puzzle.getGridVerb(noun1, slotX) !== Maybe) continue;
let ok = false;
let msg = noun1.name + " is not with " + slotX.name + ".";
for (let slot2 of slots.nouns) {
if (link.f(slotX, slot2) !== Is) continue;
for (let noun2 of nouns2) {
if (puzzle.getGridVerb(noun2, slot2) !== IsNot) {
ok = true;
break;
}
}
if (ok) break;
}
if (!ok) {
rs = solver.addMarkByRule
(mark, rule, 'b', noun1, IsNot, slotX, msg);
if (rs !== 0) return rs;
}
}
}
return rs;
}
return isRelated;
};
SmartRule.getInOppositeGroup =
function (puzzle, rule, noun1, noun2, nounType, map, groupName, groupNames) {
function inOppositeGroup(mark) {
let rs = 0;
let nounA = (noun1.type === nounType) ?
noun1 : Puzzle.getPairNoun(noun1, nounType);
let nounB = (noun2.type === nounType) ?
noun2 : Puzzle.getPairNoun(noun2, nounType);
if (nounA === null && nounB === null) return rs;
let g1 = (nounA === null) ? -1 : map[nounA.num - 1];
let g2 = (nounB === null) ? -1 : map[nounB.num - 1];
if (nounA !== null && nounB !== null) {
return (g1 === g2) ? -1 : 0;
}
let msg = noun1.name + " and " + noun2.name +
" have the opposite " + groupName + ".";
for (let noun of nounType.nouns) {
if (nounA !== null && map[noun.num - 1] === g1) {
rs = solver.addMarkByRule(mark, rule, 'a', noun2, IsNot, noun, msg);
if (rs !== 0) return rs;
}
if (nounB !== null && map[noun.num - 1] === g2) {
rs = solver.addMarkByRule(mark, rule, 'b', noun1, IsNot, noun, msg);
if (rs !== 0) return rs;
}
}
return rs;
}
return inOppositeGroup;
};
SmartRule.getInSameGroup =
function (puzzle, rule, noun1, noun2, nounType, map, groupName, groupNames) {
function doListEliminator2(mark, rule, noun1, noun2, list1, list2, msg) {
let rs = 0;
for (let noun of list1) {
rs = solver.addMarkByRule(mark, rule, 'a', noun1, IsNot, noun, msg);
if (rs !== 0) return rs;
}
for (let noun of list2) {
rs = solver.addMarkByRule(mark, rule, 'b', noun2, IsNot, noun, msg);
if (rs !== 0) return rs;
}
return rs;
}
function inSameGroup(mark) {
let rs = 0;
let nounA = (noun1.type === nounType) ?
noun1 : Puzzle.getPairNoun(noun1, nounType);
let nounB = (noun2.type === nounType) ?
noun2 : Puzzle.getPairNoun(noun2, nounType);
let g1 = (nounA === null) ? -1 : map[nounA.num - 1];
let g2 = (nounB === null) ? -1 : map[nounB.num - 1];
if (nounA !== null && nounB !== null) {
return (g1 !== g2) ? -1 : 0;
}
let msg = noun1.name + " and " + noun2.name +
" have the same " + groupName + ".";
if (nounA !== null && nounB === null) {
for (let noun of nounType.nouns) {
if (map[noun.num - 1] === g1) continue;
rs = solver.addMarkByRule(mark, rule, 'a', noun2, IsNot, noun, msg);
if (rs !== 0) return rs;
}
}
if (nounA === null && nounB !== null) {
for (let noun of nounType.nouns) {
if (map[noun.num - 1] === g2) continue;
rs = solver.addMarkByRule(mark, rule, 'b', noun1, IsNot, noun, msg);
if (rs !== 0) return rs;
}
}
if (nounA !== null || nounB !== null) return rs;
let group1 = []; let group1Noun1 = []; let group1Noun2 = [];
let group2 = []; let group2Noun1 = []; let group2Noun2 = [];
for (let noun of nounType.nouns) {
let i = noun.num - 1;
let verb1 = puzzle.getGridVerb(noun, noun1);
if (verb1 === Maybe) {
if (map[i] === 0) group1Noun1.push(noun); else group2Noun1.push(noun);
}
let verb2 = puzzle.getGridVerb(noun, noun2);
if (verb2 === Maybe) {
if (map[i] === 0) group1Noun2.push(noun); else group2Noun2.push(noun);
}
if (verb1 === Maybe || verb2 === Maybe) {
if (map[i] === 0) group1.push(noun); else group2.push(noun);
}
}
if ((group1.length < 2 || group1Noun1.length < 1 ||
group1Noun2.length < 1) && group1.length > 0) {
msg = "There are not enough " + groupNames[0] +
" for " + noun1.name + " and " + noun2.name + ".";
rs = doListEliminator2
(mark, rule, noun1, noun2, group1Noun1, group1Noun2, msg);
if (rs !== 0) return rs;
}
if ((group2.length < 2 || group2Noun1.length < 1 ||
group2Noun2.length < 1) && group2.length > 0) {
msg = "There are not enough " + groupNames[1] +
" for " + noun1.name + " and " + noun2.name + ".";
rs = doListEliminator2
(mark, rule, noun1, noun2, group2Noun1, group2Noun2, msg);
if (rs !== 0) return rs;
}
return rs;
}
return inSameGroup;
};
Globals
Throughout this article, I kept apologizing about my use of globals, but some globals are unavoidable. Here are some examples.
viewer
is the Viewer object. Defined in head.php and instantiated in the puzzle's onload
event. solver
is the Solver object. Defined in head.php and WebWorker.js, but instantiated only by the Web Worker. puzzle
is the child (puzzle module) of the Puzzle object. Defined and instantiated in both head.php and WebWorker.js. - The puzzle module class. Example:
FiveHouses
. Loaded by head.php and WebWorker.js. - The common classes. Loaded by head.php and WebWorker.js.
Note: The files head.php and WebWorker.js will be discussed in a future article.
Conclusion
I hope you enjoyed reading this article. My motivation for writing this article is that you will try to model a logic puzzle on your own. Then together, we can find better ways to model and/or solve logic puzzles. Thank you!
History
- 13th July, 2017: Initial version