Model a Logic Puzzle in JavaScript |
---|
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 a basic knowledge of JavaScript, know some of the newer constructs, and understand how classes work in 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.
"use strict";
option.const
keyword.let
keyword.addEventListener
method so the method the event calls can be local.A logic puzzle is a story of mystery. But you are not only its reader, you are it's 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.
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!
The Puzzle
class is instantiated and populated by every puzzle module. 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.
import { Verb } from "./Verb.js"; import { NounType } from "./NounType.js"; import { Link } from "./Link.js"; import { Fact } from "./Fact.js"; import { Rule } from "./Rule.js"; import * as SmartLink from "./SmartLink.js"; import * as Helper from "./Helper.js"; export class Puzzle { constructor(name, title, rank, blurb, author = "", source = "", enabled = true) { this.name = null; this.title = null; this.rank = 0; this.blurb = null; this.author = ""; this.source = ""; this.enabled = true; this.answer = null; this.valid = false; this.numNouns = 0; this.nounTypes = []; this.verbs = [Verb.IsNot, Verb.Is, Verb.Maybe]; this.links = []; this.facts = []; this.rules = []; this.toString = () => this.name; this.asString = toString; this.sayFact = (noun1, verb, link, noun2) => noun1.name + " " + verb.name + " " + link.name + " " + noun2.name + "."; this.getNounType = (num) => this.nounTypes[num - 1]; this.getNoun = (typeNum, num) => this.nounTypes[typeNum - 1].nouns[num - 1]; this.getVerb = (num) => this.verbs[num]; this.name = name; this.title = title; this.rank = rank; this.blurb = blurb; this.author = author; this.source = source; this.enabled = enabled; } reset() { for (let nounType of this.nounTypes) { nounType.reset(); } for (let fact of this.facts) { fact.reset(); } for (let rule of this.rules) { rule.reset(); } } addNounType(name) { const nounType = Object.seal(new NounType(this.nounTypes.length + 1, name)); this.nounTypes.push(nounType); if (nounType.num === 1) { Link.With = this.addLink("with", nounType, SmartLink.getIsWith()); } return nounType; } addLink(name, nounType, getVerb = null) { const link = Object.seal(new Link(this.links.length, name, nounType, getVerb)); this.links.push(link); return link; } addFact(clueNum, nounA, verb, link, nounB = null, name = null, initEnabled = true) { const nouns1 = Array.isArray(nounA) ? nounA : [nounA]; if (nounB === null) this.addFacts1(clueNum, nouns1, verb, link, name, initEnabled); else { const nouns2 = Array.isArray(nounB) ? nounB : [nounB]; this.addFacts2(clueNum, nouns1, verb, link, nouns2, name, initEnabled); } } getClueNumAsString(clueNum, name) { if (clueNum === null || clueNum.length < 1) return name; const i = name.length - 1; if (i < 0) return name; const eos = name[i]; let txt = ""; if (clueNum[0] === 'A') { const tmp = clueNum.length > 1 ? " " + clueNum.substring(1) : ""; txt = "analysis" + tmp; } else if (clueNum[0] === '0') { txt = "intro"; } else { const tmp = clueNum.indexOf(",") > -1 ? "s" : ""; txt = "clue" + tmp + " " + clueNum; } const msg = name.substring(0, i) + " (" + txt + ")" + eos; return msg; } addOneFact(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(`puzzle.addOneFact Warning! This fact already exists: num=${oldFact.num} name="${oldFact.name}"`); return null; } } const msg = this.getClueNumAsString(clueNum, txt); const fact = Object.seal(new Fact(this.facts.length + 1, msg, noun1, verb, link, noun2, initEnabled)); this.facts.push(fact); return fact; } addFacts1(clueNum, nouns, verb, link, name = null, initEnabled = true) { for (let i = 0; i < nouns.length - 1; i++) { const noun1 = nouns[i]; for (let j = i + 1; j < nouns.length; j++) { const noun2 = nouns[j]; if (noun1 === noun2 || (link === Link.With && noun1.type === noun2.type)) continue; this.addOneFact(clueNum, noun1, verb, link, noun2, name, initEnabled); } } } addFacts2(clueNum, nouns1, verb, link, nouns2, name = null, initEnabled = true) { for (let noun1 of nouns1) { for (let noun2 of nouns2) { if (noun1 === noun2 || (link === Link.With && noun1.type === noun2.type)) continue; this.addOneFact(clueNum, noun1, verb, link, noun2, name, initEnabled); } } } addFactsInSequence(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); } } addFactsOneToOne(clueNum, nounA, verb, link, nounB, name = null, initEnabled = true) { const nouns1 = Array.isArray(nounA) ? nounA : nounA.nouns; const nouns2 = Array.isArray(nounB) ? nounB : nounB.nouns; const 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); } } addFactsStartsWith(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, Verb.IsNot, Link.With, noun2, name, initEnabled); } } } addFactsIsNotFirstChar(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, Verb.IsNot, Link.With, noun2, name, initEnabled); } } } } addFactsNotConsecutive(clueNum, nouns, link, name = null, initEnabled = true) { const n = nouns.length; const type = link.nounType; const max = type.nouns.length; if (2 * n - 1 === max) { for (let noun of nouns) { for (let i = 1; i < max; i += 2) { const slot = type.nouns[i]; this.addOneFact(clueNum, noun, Verb.IsNot, Link.With, slot, name, initEnabled); } } } else { for (let i1 = 0; i1 < n - 1; i1++) { const noun1 = nouns[i1]; for (let i2 = i1 + 1; i2 < n; i2++) { const noun2 = nouns[i2]; this.addOneFact(clueNum, noun1, Verb.IsNot, link, noun2, name, initEnabled); this.addOneFact(clueNum, noun2, Verb.IsNot, link, noun1, name, initEnabled); } } } } addRule(clueNum, name, nouns = [], initEnabled = true) { const msg = this.getClueNumAsString(clueNum, name); const rule = Object.seal(new Rule(this.rules.length + 1, msg, nouns, initEnabled)); this.rules.push(rule); return rule; } validate() { let rs = -1; this.valid = false; if (this.name === null || this.name.length === 0) return rs; if (this.title === null || this.title.length === 0) return rs; if (this.verbs.length !== Verb.MaxVerbs) return rs; if (this.nounTypes.length < 2) return rs; this.numNouns = this.nounTypes[0].nouns.length; for (let nounType of this.nounTypes) { if (nounType.nouns.length !== this.numNouns) return rs; for (let noun of nounType.nouns) { noun.pairs = []; for (let k = 0; k < this.nounTypes.length; k++) noun.pairs[k] = null; } } if (this.links.length < 1) return rs; for (let link of this.links) { link.setOneToOne(); if (link.getVerb === null) return rs; } for (let fact of this.facts) { if (fact.noun1 === null || fact.verb === null || fact.link === null || fact.noun2 === null) return rs; if (fact.noun1.type === null || fact.noun2.type === null) return rs; if (fact.noun1.type === fact.link.nounType && fact.noun2.type === fact.link.nounType) return rs; if (fact.num < 1) return rs; } for (let rule of this.rules) { if (rule.f === null) return rs; } if (this.facts.length + this.rules.length < 1) return rs; this.valid = true; this.reset(); return 0; } getEncodedAnswer() { const m = this.nounTypes.length - 1; const n = this.numNouns; const answer = Helper.getArray2D(m, n, 0); const nounType1 = this.nounTypes[0]; for (let noun1 of nounType1.nouns) { for (let nounType2 of this.nounTypes) { if (nounType2.num === 1) continue; const n2 = noun1.getPairNounNum(nounType2) - 1; answer[nounType2.num - 2][noun1.num - 1] = n2; } } const msg = Helper.getArray2DAsString(answer); console.log(msg); } isAnswer() { this.getEncodedAnswer(); if (this.answer === null) return true; const nounType1 = this.nounTypes[0]; for (let noun1 of nounType1.nouns) { for (let nounType2 of this.nounTypes) { if (nounType2.num === 1) continue; if ((noun1.getPairNounNum(nounType2) - 1) !== this.answer[nounType2.num - 2][noun1.num - 1]) return false; } } return true; } }
The puzzle module stores all of the data and functions necessary to solve it. 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.
Note: In most languages, the puzzle module class would inherit from the puzzle class. But to avoid using the "this" keyword, I decided to instantiate, populate, and return the puzzle object in each puzzle module.
import { Verb } from "../puzzle/Verb.js"; import { Link } from "../puzzle/Link.js"; import { Puzzle } from "../puzzle/Puzzle.js"; import * as Helper from "../puzzle/Helper.js"; import * as SmartLink from "../puzzle/SmartLink.js"; export function loader(solver) { const puzzle = new Puzzle("FiveHouses", "Five Houses", 2, "Wisteria Lane may have more intrigue, but these neighbors are puzzling.", "", "Marilyn vos Savant's column \"Ask Marilyn\""); puzzle.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]]; const houses = puzzle.addNounType("House"); const house1 = houses.addNoun("1st"); const house2 = houses.addNoun("2nd"); const house3 = houses.addNoun("3rd"); const house4 = houses.addNoun("4th"); const house5 = houses.addNoun("5th"); const colors = puzzle.addNounType("Color"); const red = colors.addNoun("red"); const green = colors.addNoun("green"); const white = colors.addNoun("white"); const yellow = colors.addNoun("yellow"); const blue = colors.addNoun("blue"); const nationalities = puzzle.addNounType("Nationality"); const englishman = nationalities.addNoun("Englishman"); const spaniard = nationalities.addNoun("Spaniard"); const ukrainian = nationalities.addNoun("Ukrainian"); const norwegian = nationalities.addNoun("Norwegian"); const japanese = nationalities.addNoun("Japanese man", "Japanese"); const hobbies = puzzle.addNounType("Hobby"); const stamps = hobbies.addNoun("stamps"); const antiques = hobbies.addNoun("antiques"); const sings = hobbies.addNoun("singing"); const gardens = hobbies.addNoun("gardening"); const cooking = hobbies.addNoun("cooking"); const pets = puzzle.addNounType("Pet"); const dogs = pets.addNoun("dogs"); const snails = pets.addNoun("snails"); const fox = pets.addNoun("fox"); const horse = pets.addNoun("horse"); const zebra = pets.addNoun("zebra"); const drinks = puzzle.addNounType("Drink"); const coffee = drinks.addNoun("coffee"); const tea = drinks.addNoun("tea"); const milk = drinks.addNoun("milk"); const juice = drinks.addNoun("juice"); const water = drinks.addNoun("water"); const directlyRightOf = puzzle.addLink("directly to the right of", houses, SmartLink.getIsMoreBy(1)); const nextTo = puzzle.addLink("next to", houses, SmartLink.getIsNextTo()); puzzle.sayFact = (noun1, verb, link, noun2) => { let msg = noun1.name + " " + verb.name + " " + link.name + " " + noun2.name; switch (noun1.type.num) { case 1: switch (noun2.type.num) { case 1: break; case 2: break; case 3: break; case 4: break; case 5: break; case 6: if (link === Link.With) msg = "The man in the " + noun1.name + " house " + (verb === Verb.Is ? "drinks" : "does not drink") + " " + noun2.name; break; } break; case 2: switch (noun2.type.num) { case 1: break; case 2: msg = "The " + noun1.name + " house " + verb.name + " " + link.name + " the " + noun2.name + " house"; break; case 3: break; case 4: break; case 5: break; case 6: break; } break; case 3: msg = "The " + noun1.name; switch (noun2.type.num) { case 1: if (link === Link.With) msg += " " + verb.name + " in the " + noun2.name + " house"; break; case 2: if (link === Link.With) msg += " " + verb.name + " in the " + noun2.name + " house"; else msg += " " + verb.name + " " + link.name + " the " + noun2.name + " house"; break; case 3: break; case 4: if (link === Link.With) msg += "'s hobby " + verb.name + " " + noun2.name; break; case 5: if (link === Link.With) msg += "'s pet " + verb.name + " " + noun2.name; break; case 6: if (link === Link.With) msg += "'s favorite drink" + " " + verb.name + " " + noun2.name; break; } break; case 4: msg = "The man who's hobby is " + noun1.name + " "; switch (noun2.type.num) { case 1: break; case 2: if (link === Link.With) msg += verb.name + " in the " + noun2.name + " house"; break; case 3: break; case 4: break; case 5: if (link === Link.With) msg += (verb === Verb.Is ? "owns" : "does not own") + " " + noun2.name; else msg += verb.name + " " + link.name + " the man with the " + noun2.name; break; case 6: msg += (verb === Verb.Is ? "drinks" : "does not drink") + " " + noun2.name; break; } break; case 5: switch (noun2.type.num) { case 1: break; case 2: break; case 3: break; case 4: break; case 5: break; case 6: break; } break; case 6: switch (noun2.type.num) { case 1: break; case 2: if (link === Link.With) msg = Helper.getFirstCap(noun1.name) + " " + verb.name + " drunk in the " + noun2.name + " house"; break; case 3: break; case 4: break; case 5: break; case 6: break; } break; } return msg + "."; }; puzzle.addFact("1", englishman, Verb.Is, Link.With, red); puzzle.addFact("2", spaniard, Verb.Is, Link.With, dogs); puzzle.addFact("3", coffee, Verb.Is, Link.With, green); puzzle.addFact("4", ukrainian, Verb.Is, Link.With, tea); puzzle.addFact("5", green, Verb.Is, directlyRightOf, white); puzzle.addFact("6", stamps, Verb.Is, Link.With, snails); puzzle.addFact("7", antiques, Verb.Is, Link.With, yellow); puzzle.addFact("8", house3, Verb.Is, Link.With, milk); puzzle.addFact("9", norwegian, Verb.Is, Link.With, house1); puzzle.addFact("10", sings, Verb.Is, nextTo, fox); puzzle.addFact("11", gardens, Verb.Is, Link.With, juice); puzzle.addFact("12", antiques, Verb.Is, nextTo, horse); puzzle.addFact("13", japanese, Verb.Is, Link.With, cooking); puzzle.addFact("14", norwegian, Verb.Is, nextTo, blue); return puzzle; }
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 when the puzzle is instantiated. I use the names myName
and myTitle
instead of the more generic name
and title
to avoid naming collisions.
let puzzle = new Puzzle("FiveHouses", "Five Houses");
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.
# | 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.
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".
import { Noun } from "./Noun.js"; export class NounType { constructor(num, name) { this.nouns = []; this.toString = () => this.name; this.asString = () => `{num:${this.num} name:"${this.name}" nouns:${this.nouns}}`; this.getNoun = (num) => this.nouns[num - 1]; this.num = num; this.name = name; } reset() { for (let noun of this.nouns) noun.reset(); } addNoun(name, title = null) { const noun = Object.seal(new Noun(this.nouns.length + 1, this, name, title)); this.nouns.push(noun); return noun; } }
import * as Helper from "./Helper.js"; export class Noun { constructor(num, type, name, title = null) { this.pairs = []; this.facts = []; this.toString = () => this.name; this.asString = () => `num:${this.num} type:"${this.type.name}" name:"${this.name}" title:"${this.title}" name0:"${this.name0}" title0:"${this.title0}" pairs.length:${this.pairs.length} facts.length:${this.facts.length}`; this.addNoun = (name, title) => this.type.addNoun(name, title); this.getPairNoun = (nounType) => this.pairs[nounType.num - 1]; this.isPair = (noun) => this.getPairNoun(noun.type) === noun ? true : false; if (title === null) title = Helper.toTitleCase(name); this.num = num; this.type = type; this.name0 = name; this.name = name; this.title0 = title; this.title = title; } reset() { const n = this.pairs.length; this.resetPlacer(); for (let i = 0; i < n; i++) this.pairs[i] = null; } getPairNounNum(nounType) { const noun = this.pairs[nounType.num - 1]; return noun === null ? 0 : noun.num; } resetPlacer() { this.name = this.name0; this.title = this.title0; } updatePlacer(name, title) { this.name = "" + name; this.title = "" + title; } }
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.
// Nouns. let houses = puzzle.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");
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.
# | 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 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 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.
export class Verb { constructor(num, name, code, style = null) { this.toString = () => this.name; this.asString = () => `{num:${this.num} name:"${this.name}" type:"${this.type}" code:"${this.code}" style:"${this.style}"}`; this.getCodeAsHtml = () => "<span style=\"" + this.style + "\">" + this.code + "</span>"; this.num = num; this.name = name; this.type = Verb.Types[num]; this.code = code; if (style === null) { switch (num) { case 0: this.style = "color:red;"; break; case 1: this.style = "color:black;"; break; case 2: this.style = "color:gray;"; break; } } } } Verb.Types = ["Negative", "Positive", "Possible"]; Verb.MaxVerbs = Verb.Types.length; Verb.IsNot = new Verb(0, "is not", "X"); Verb.Is = new Verb(1, "is", "O"); Verb.Maybe = new Verb(2, "maybe", " "); console.log(`Verb.IsNot=${Verb.IsNot.asString()}`); console.log(`Verb.Is =${Verb.Is.asString()}`); console.log(`Verb.Maybe=${Verb.Maybe.asString()}`);
The three nouns are always defined for each puzzle module. These three variables are "static" variables of the Verb class: Verb.IsNot
, Verb.Is
, and Verb.Maybe
. Since the predefined attributes for these verbs are acceptable, this section is not needed for our puzzle module.
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.
1st | 2nd | 3rd | 4th | 5th |
---|
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:
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.
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.
This type of link has a "one-to-one" relationship because exactly one house is directly to the right of another house.
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?
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.
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.
# | Noun Type | Name | 1:1 |
---|---|---|---|
0 | House | ||
1 | House | ||
2 | House |
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 |
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 |
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 |
import { Verb } from "./Verb.js"; export class Link { constructor(num, name, nounType, getVerb = null) { this.oneToOne = false; this.toString = () => this.name; this.asString = () => `{num:${this.num} name:"${this.name}" nounType:"${this.nounType}" oneToOne:${this.oneToOne}`; this.num = num; this.name = name; this.nounType = nounType; this.getVerb = getVerb; } setOneToOne() { this.oneToOne = false; for (let noun1 of this.nounType.nouns) { let cnt = 0; for (let noun2 of this.nounType.nouns) { const verb = this.getVerb(noun1, noun2); if (verb === Verb.Is && ++cnt > 1) return; } } this.oneToOne = true; } } Link.With = null;
The first link "with" is defined as a "static" variable of the Link class, 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 = puzzle.addLink("directly to the right of", houses); directlyRightOf.getVerb = SmartLink.getIsMoreBy(1); let nextTo = puzzle.addLink("next to", houses); nextTo.getVerb = SmartLink.getIsNextTo();
Note: The function assigned to each link via the getVerb
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".
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.
# | X | Hits | Name |
---|---|---|---|
1 | 0 | ||
2 | 0 | ||
3 | 0 | ||
4 | 0 | ||
5 | 0 | ||
6 | 0 | ||
7 | 0 | ||
8 | 0 | ||
9 | 0 | ||
10 | 0 | ||
11 | 0 | ||
12 | 0 | ||
13 | 0 | ||
14 | 0 |
Here is a brief description for each column.
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.
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.
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".
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".
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.
export class Fact { constructor(num, name, noun1, verb, link, noun2, initEnabled = true) { this.type = 0; this.hits = 0; this.toString = () => this.name; this.asString = () => `{num:${this.num} name:"${this.name}" type:"${this.type}" noun1:"${this.noun1}" verb:"${this.verb}" link:"${this.link}" noun2:"${this.noun2}" hits:${this.hits} enabled:${this.enabled} initEnabled:${this.initEnabled}}`; this.msgBasedOn = () => "fact " + this.num; this.msgDisabled = () => " Fact " + this.num + " is disabled."; this.num = num; this.name = name; this.noun1 = noun1; this.verb = verb; this.link = link; this.noun2 = noun2; this.enabled = initEnabled; this.initEnabled = initEnabled; 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 (noun1.type !== noun2.type) this.type = 4; } reset() { this.hits = 0; this.enabled = this.initEnabled; } ; }
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.
puzzle.addFact("1", englishman, Verb.Is, Link.With, red, "The Englishman lives in the red house.");
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.
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.
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".
import { Verb } from "../puzzle/Verb.js"; import { Link } from "../puzzle/Link.js"; import { Puzzle } from "../puzzle/Puzzle.js"; import * as SmartLink from "../puzzle/SmartLink.js"; import * as SmartRule from "../puzzle/SmartRule.js"; export function loader(solver) { const puzzle = new Puzzle("AllTiredOut", "All Tired Out", 3, "This puzzle won't \"shock\" you, but your brain may \"tire\" while solving it!", "Faith Johnson", "Dell Logic Puzzles April 1997"); puzzle.answer = [[4, 1, 2, 3, 0], [1, 4, 2, 3, 0]]; const slots = puzzle.addNounType("Order"); const slot1 = slots.addNoun("1st"); const slot2 = slots.addNoun("2nd"); const slot3 = slots.addNoun("3rd"); const slot4 = slots.addNoun("4th"); const slot5 = slots.addNoun("5th"); const names = puzzle.addNounType("Customer"); const ethan = names.addNoun("Ethan"); const grace = names.addNoun("Grace"); const jeff = names.addNoun("Jeff"); const lisa = names.addNoun("Lisa"); const marge = names.addNoun("Marge"); const wants = puzzle.addNounType("Wanted"); const alignment = wants.addNoun("alignment"); const chains = wants.addNoun("chains"); const jack = wants.addNoun("jack"); const shocks = wants.addNoun("shock absorbers", "Shocks"); const tires = wants.addNoun("tires"); Verb.IsNot.name = "was not"; Verb.Is.name = "was"; const justAhead = puzzle.addLink("just ahead of", slots, SmartLink.getIsLessBy(1)); const threeAhead = puzzle.addLink("three places ahead of", slots, SmartLink.getIsLessBy(3)); const nextTo = puzzle.addLink("next to", slots, SmartLink.getIsNextTo()); puzzle.sayFact = (noun1, verb, link, noun2) => { let msg = noun1.name + " " + verb.name + " " + link.name + " " + noun2.name; let lname = link === 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 === 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 === Link.With) msg += (verb === 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 + "."; }; puzzle.addFact("1", [ethan, slot3, chains], Verb.IsNot, Link.With); puzzle.addFact("2", jack, Verb.Is, justAhead, lisa); puzzle.addFact("3", slot2, Verb.IsNot, Link.With, [ethan, jeff]); puzzle.addFact("4", tires, Verb.Is, threeAhead, alignment); puzzle.addFact("6", jeff, Verb.Is, justAhead, shocks); const rule1 = puzzle.addRule("5", "Marge wasn't the second of the three women in line."); rule1.f = SmartRule.getIsNotBetween(solver, rule1, slots, marge, grace, lisa); const rule2 = puzzle.addRule("7", "Grace stood next to at least one man in line."); rule2.f = SmartRule.getIsRelated(solver, rule2, grace, nextTo, [ethan, jeff]); return puzzle; }
In this puzzle module, you can see that I set the names for the verbs to be past tense.
// Verbs. Verb.IsNot.name = "was not"; Verb.Is.name = "was";
For this logic puzzle, clues 5 and 7 need to be expressed as rules. Here are the rules for this puzzle.
# | X | Hits | Name |
---|---|---|---|
1 | 0 | ||
2 | 0 |
Here is a brief description for each column.
export class Rule { constructor(num, name, nouns = [], initEnabled = true) { this.f = null; this.hits = 0; this.toString = () => this.name; this.asString = () => `{num:${this.num} name:"${this.name}" nouns:"${this.nouns}" hits:${this.hits} enabled:${this.enabled} initEnabled:${this.initEnabled}}`; this.num = num; this.name = name; this.nouns = nouns; this.enabled = initEnabled; this.initEnabled = initEnabled; } reset() { this.hits = 0; this.enabled = this.initEnabled; } }
Here are the rules that will satisfy clues 5 and 7.
// Rules. let rule1 = puzzle.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 = puzzle.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.
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.
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.
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.
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" the following.
puzzle.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 ] ];
The Helper
static class defines helpful methods. This class is referenced by several of my classes.
export const isNumber = (val) => typeof val === "number" && !isNaN(val); export const isBoolean = (val) => typeof val === "boolean"; export function isInt(str) { const val = parseInt(str); return typeof val === 'number' && isFinite(val) && Math.floor(val) === val; } export function getBoolean(val) { if (typeof val === "boolean") return val; if (isNumber(val)) return val !== 0; if (typeof val !== "string") return false; val = val.toLowerCase(); return val === "true"; } export const toInt = (str) => str === null ? 0 : parseInt(str, 10); export function isNotDivisibleBy(noun, num) { if (noun === null || !isInt(noun.name)) return false; const val = toInt(noun.name); return val % num !== 0; } export const getFirstCap = (name) => name.charAt(0).toUpperCase() + name.slice(1); export const getMsgAsOneLine = (str, sep = " ") => str.replace("\n", sep); export const toTitleCase = (str) => str.replace(/\w\S*/g, function (txt) { return txt.charAt(0).toUpperCase() + txt.substr(1); }); export const getObjName = (obj) => obj ? obj.name : "(null)"; export function getArray2DAsString(a) { let str = ""; if (a === null) return str; str = "["; const n1 = a.length; for (let i1 = 0; i1 < n1; i1++) { let line = "[", sep = ""; const n2 = a[i1].length; for (let i2 = 0; i2 < n2; i2++) { line += sep + a[i1][i2]; sep = ","; } sep = (i1 < n1 - 1) ? "," : ""; str += line + "]" + sep; } str += "]"; return str; } export function getListExcept(list1, list2) { const list = []; for (let item1 of list1) { let found = false; for (let item2 of list2) { if (item1 === item2) { found = true; break; } } if (!found) list.push(item1); } return list; } export function getArray2D(d1, d2, v = 0) { const a = []; for (let i1 = 0; i1 < d1; i1++) { a[i1] = []; for (let i2 = 0; i2 < d2; i2++) { a[i1][i2] = v; } } return a; } export function getNounArray2D(d1, d2, v = null) { const a = []; for (let i1 = 0; i1 < d1; i1++) { a[i1] = []; for (let i2 = 0; i2 < d2; i2++) { a[i1][i2] = v; } } return a; } export function getVerbArray2D(d1, d2, v = null) { const a = []; for (let i1 = 0; i1 < d1; i1++) { a[i1] = []; for (let i2 = 0; i2 < d2; i2++) { a[i1][i2] = v; } } return a; } export function solveEquations(a) { const n = a[0].length - 1; console.log(`Helper.solveEquations n=${n}`); const x = []; for (let i = 0; i < n; i++) x[i] = 0; 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++) { const m = a[p][c]; a[p][c] = a[i][c]; a[i][c] = m; } } for (let j = i + 1; j < n; j++) { const 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; } export function formatDT(date) { const yy = date.getFullYear(); const mm = date.getMonth() + 1; const dd = date.getDate(); const hh = date.getHours(); const mi = date.getMinutes(); const ss = date.getSeconds(); const ms = date.getMilliseconds(); const 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; } export function getChartAsText(puzzle, chartCol1, isSolution) { let txt = ""; if (puzzle === null) return txt; txt = isSolution ? "Solution\n" : "Chart\n"; const t = chartCol1; const nounTypes = puzzle.nounTypes; const nounType1 = nounTypes[t]; const m = nounTypes.length; const n = nounType1.nouns.length; const w = 20; const pad = " ".repeat(w); let tmp; let i = 0, j = 0, k = 0; for (j = 0; j < m; j++) { if (k === t) ++k; const nounType = (j === 0 ? nounType1 : nounTypes[k++]); tmp = nounType.name + pad; txt += tmp.substring(0, w); } txt += "\n"; for (i = 0; i < n; i++) { k = 0; for (j = 0; j < m; j++) { if (k === t) ++k; const noun1 = nounType1.nouns[i]; tmp = " "; if (j === 0) tmp = noun1.title; else { const noun2 = noun1.getPairNoun(nounTypes[k]); if (noun2 !== null) tmp = noun2.title; ++k; } tmp += pad; txt += tmp.substring(0, w); } txt += "\n"; } return txt; }
The SmartLink
static class defines methods that return a function for the links in a puzzle module.
import { Verb } from "./Verb.js"; export function getIsWith() { return (noun1, noun2) => noun1.num === noun2.num ? Verb.Is : Verb.IsNot; } export function getIsLessThan(n = 0) { return (noun1, noun2) => noun1.num < noun2.num - n ? Verb.Is : Verb.IsNot; } export function getIsLessBy(n) { return (noun1, noun2) => noun1.num === noun2.num - n ? Verb.Is : Verb.IsNot; } export function getIsMoreThan(n = 0) { return (noun1, noun2) => noun1.num > noun2.num + n ? Verb.Is : Verb.IsNot; } export function getIsMoreBy(n) { return (noun1, noun2) => noun1.num === noun2.num + n ? Verb.Is : Verb.IsNot; } export function getIsNextTo() { return (noun1, noun2) => (noun1.num === noun2.num - 1) || (noun1.num === noun2.num + 1) ? Verb.Is : Verb.IsNot; } export function getIsOffsetBy(n) { return (noun1, noun2) => (noun1.num === noun2.num - n) || (noun1.num === noun2.num + n) ? Verb.Is : Verb.IsNot; } export function getIsOutsideOf(n) { return (noun1, noun2) => (noun1.num < noun2.num - n) || (noun1.num > noun2.num + n) ? Verb.Is : Verb.IsNot; } export function getHasRatio(n1, n2) { return (noun1, noun2) => (n1 * noun1.num === n2 * noun2.num) ? Verb.Is : Verb.IsNot; }
The SmartRule
static class defines methods that return a function for the rules in a puzzle module.
import { Verb } from "./Verb.js"; import * as Helper from "./Helper.js"; export function getMatchAtLeastOne(solver, rule, noun1, nouns2) { function canBeWith2(noun1, nouns2) { for (let noun2 of nouns2) { if (noun1.type === noun2.type) continue; if (noun1.getPairNounNum(noun2.type) === noun2.num) return true; if (solver.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 (noun1.getPairNoun(noun2.type) === noun2) return null; if (!solver.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; const noun2 = isOnlyNoun(noun1, nouns2); if (noun2 !== null) { const msg = noun1.name + " must be with " + noun2.name + "."; rs = solver.addMarkByRule(mark, rule, ' ', noun1, Verb.Is, noun2, msg); if (rs !== 0) return rs; } const puzzle = solver.puzzle; for (let nounType of puzzle.nounTypes) { if (noun1.type === nounType) continue; for (let nounX of nounType.nouns) { if (solver.getGridVerb(noun1, nounX) === Verb.IsNot) continue; let ok = false; for (let noun of nouns2) { if (noun.type === nounType || solver.getGridVerb(noun, nounX) !== Verb.IsNot) { ok = true; break; } } if (!ok) { const msg = "SmartRule.matchAtLeastOne: No item in list can be with " + nounX.name + "."; rs = solver.addMarkByRule(mark, rule, ' ', noun1, Verb.IsNot, nounX, msg); if (rs !== 0) return rs; } } } return rs; } return matchAtLeastOne; } export function getMatchOneToExactlyOne(solver, 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 (noun1.isPair(noun2)) ++cnt; } } return cnt; } function matchOneToExactlyOne(mark) { let rs = 0; const n1 = nouns1.length; const n2 = nouns2.length; const counts = new Array(n1); let scanFlag = true; let i1 = -1; let i2 = -1; for (let i = 0; i < n1; i++) { const noun1 = nouns1[i]; counts[i] = 0; for (let j = 0; j < n2; j++) { const noun2 = nouns2[j]; if (noun2.type === noun1.type) continue; if (noun1.isPair(noun2)) { scanFlag = false; break; } if (solver.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) { const noun1 = nouns1[i1]; const noun2 = nouns2[i2]; const msg = noun1.name + " must be with " + noun2.name + "."; rs = solver.addMarkByRule(mark, rule, ' ', noun1, Verb.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; } export function getMatchOneToOne(solver, rule, nouns1, nouns2) { const numNouns = nouns1.length; const grid = Helper.getVerbArray2D(numNouns, numNouns, null); function matchOneToOne(mark) { let rs = 0; let str = ""; for (let irow = 0; irow < numNouns; irow++) { const noun1 = nouns1[irow]; for (let icol = 0; icol < numNouns; icol++) { const noun2 = nouns2[icol]; const verb = solver.getGridVerb(noun1, noun2); str += verb.code; grid[irow][icol] = verb; } str += "\n"; } for (let irow = 0; irow < numNouns; irow++) { let cntO = 0; let cntX = 0; for (let icol = 0; icol < numNouns; icol++) { const verb = grid[irow][icol]; if (verb === Verb.Is) ++cntO; else if (verb === Verb.IsNot) ++cntX; } if (cntO > 1 || cntX === numNouns) return -1; } for (let icol = 0; icol < numNouns; icol++) { let cntO = 0; let cntX = 0; for (let irow = 0; irow < numNouns; irow++) { const verb = grid[irow][icol]; if (verb === Verb.Is) ++cntO; else if (verb === Verb.IsNot) ++cntX; } if (cntO > 1 || cntX === numNouns) return -1; } for (let irow = 0; irow < numNouns; irow++) { const noun1 = nouns1[irow]; let cntO = 0; for (let icol = 0; icol < numNouns; icol++) { if (grid[irow][icol] === Verb.Is) ++cntO; } if (cntO === 1) { for (let icol = 0; icol < numNouns; icol++) { const noun2 = nouns2[icol]; if (grid[irow][icol] !== Verb.Maybe) continue; grid[irow][icol] = Verb.IsNot; const msg = "Only one of each noun in list2 can be with one of each noun in list1."; rs = solver.addMarkByRule(mark, rule, 'a', noun1, Verb.IsNot, noun2, msg); if (rs !== 0) return rs; } } } for (let icol = 0; icol < numNouns; icol++) { const noun2 = nouns2[icol]; let cntO = 0; for (let irow = 0; irow < numNouns; irow++) { if (grid[irow][icol] === Verb.Is) ++cntO; } if (cntO === 1) { for (let irow = 0; irow < numNouns; irow++) { const noun1 = nouns1[irow]; if (grid[irow][icol] !== Verb.Maybe) continue; grid[irow][icol] = Verb.IsNot; const msg = "Only one of each noun in list1 can be with one of each noun in list2."; rs = solver.addMarkByRule(mark, rule, 'b', noun1, Verb.IsNot, noun2, msg); if (rs !== 0) return rs; } } } for (let irow = 0; irow < numNouns; irow++) { const noun1 = nouns1[irow]; let i = -1; const cnts = [0, 0, 0]; for (let icol = 0; icol < numNouns; icol++) { const verb = grid[irow][icol]; cnts[verb.num] += 1; if (verb.num === 2) i = icol; } if (cnts[0] === numNouns - 1 && cnts[1] === 0 && cnts[2] === 1) { grid[irow][i] = Verb.Is; const noun2 = nouns2[i]; const msg = "Only one noun in list2 is available for noun1."; rs = solver.addMarkByRule(mark, rule, 'c', noun1, Verb.Is, noun2, msg); if (rs !== 0) return rs; } } for (let icol = 0; icol < numNouns; icol++) { const noun2 = nouns2[icol]; let i = -1; const cnts = [0, 0, 0]; for (let irow = 0; irow < numNouns; irow++) { const verb = grid[irow][icol]; cnts[verb.num] += 1; if (verb.num === 2) i = irow; } if (cnts[0] === numNouns - 1 && cnts[1] === 0 && cnts[2] === 1) { grid[i][icol] = Verb.Is; const noun1 = nouns1[i]; const msg = "Only one noun in list1 is available for noun2."; rs = solver.addMarkByRule(mark, rule, 'd', noun1, Verb.Is, noun2, msg); if (rs !== 0) return rs; } } return rs; } return matchOneToOne; } export function getMatchOneList(solver, 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; const n = nouns1.length; const nouns = []; let nbad = 0; for (let noun1 of nouns1) { let cnt = 0; for (let noun2 of nouns2) { const verb = solver.getGridVerb(noun1, noun2); if (verb === Verb.Is) return rs; if (verb === Verb.IsNot) continue; ++cnt; if (nouns.indexOf(noun2) < 0) 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 === 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; const msg = noun1.name + " is not with " + noun2.name + "."; rs = solver.addMarkByRule(mark, rule, 'a', noun1, Verb.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) { const msg = noun1.name + " is not with " + noun2.name + "."; rs = solver.addMarkByRule(mark, rule, 'a', noun1, Verb.IsNot, noun2, msg); if (rs !== 0) return rs; } } } return rs; } return matchOneList; } export function getIsNotBetween(solver, rule, nounType, noun1, noun2, noun3) { function isNotBetween(mark) { let rs = 0; const slotA = (noun1.type === nounType) ? noun1.num : noun1.getPairNounNum(nounType); const slotB = (noun2.type === nounType) ? noun2.num : noun2.getPairNounNum(nounType); const slotC = (noun3.type === nounType) ? noun3.num : noun3.getPairNounNum(nounType); if (slotA > 0 && slotB > 0 && slotC > 0) { if (slotB < slotA && slotA < slotC) return -1; if (slotC < slotA && slotA < slotB) return -1; return rs; } const 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; } const msg = noun1.name + " is not between " + noun2.name + " and " + noun3.name + "."; for (let i = i1; i < i2; i++) { const slot = nounType.nouns[i]; if (solver.getGridVerb(noun, slot) === Verb.IsNot) continue; rs = solver.addMarkByRule(mark, rule, ch, noun, Verb.IsNot, slot, msg); if (rs !== 0) return rs; } return rs; } return isNotBetween; } export function getIsRelated(solver, rule, noun1, link, nouns2) { function isRelated(mark) { let rs = 0; const slots = link.nounType; const slot1 = (noun1.type === slots) ? noun1 : noun1.getPairNoun(slots); if (slot1 !== null) { let nounB, slotB; let ok; ok = false; for (let noun2 of nouns2) { const slot = (noun2.type === slots) ? noun2 : noun2.getPairNoun(slots); if (slot === null || link.getVerb(slot1, slot) === Verb.Is) { ok = true; break; } } if (!ok) return -1; ok = false; for (let slot of slots.nouns) { if (link.getVerb(slot1, slot) !== Verb.Is) continue; for (let noun of nouns2) { nounB = slot.getPairNoun(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.getVerb(slot1, slot) !== Verb.Is) continue; for (let noun of nouns2) { if (solver.getGridVerb(slot, noun) !== Verb.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.getVerb(slot1, slot) !== Verb.Is) continue; for (let noun of nouns2) { const slotX = noun.getPairNoun(slots); if (slotX === slot) { cnt = 2; break; } if (slotX !== null) continue; if (solver.getGridVerb(noun, slot) === Verb.Maybe) { if (++cnt > 1) break; nounB = noun; slotB = slot; } } if (cnt > 1) break; } if (cnt === 1) { const msg = nounB.name + " must be with " + slotB.name + "."; rs = solver.addMarkByRule(mark, rule, 'a', nounB, Verb.Is, slotB, msg); if (rs !== 0) return rs; } } if (slot1 === null) { for (let slotX of slots.nouns) { if (solver.getGridVerb(noun1, slotX) !== Verb.Maybe) continue; let ok = false; const msg = noun1.name + " is not with " + slotX.name + "."; for (let slot2 of slots.nouns) { if (link.getVerb(slotX, slot2) !== Verb.Is) continue; for (let noun2 of nouns2) { if (solver.getGridVerb(noun2, slot2) !== Verb.IsNot) { ok = true; break; } } if (ok) break; } if (!ok) { rs = solver.addMarkByRule(mark, rule, 'b', noun1, Verb.IsNot, slotX, msg); if (rs !== 0) return rs; } } } return rs; } return isRelated; } export function getInOppositeGroup(solver, rule, noun1, noun2, nounType, map, groupName, groupNames) { function inOppositeGroup(mark) { let rs = 0; const nounA = (noun1.type === nounType) ? noun1 : noun1.getPairNoun(nounType); const nounB = (noun2.type === nounType) ? noun2 : noun2.getPairNoun(nounType); if (nounA === null && nounB === null) return rs; const g1 = (nounA === null) ? -1 : map[nounA.num - 1]; const g2 = (nounB === null) ? -1 : map[nounB.num - 1]; if (nounA !== null && nounB !== null) { return (g1 === g2) ? -1 : 0; } const 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, Verb.IsNot, noun, msg); if (rs !== 0) return rs; } if (nounB !== null && map[noun.num - 1] === g2) { rs = solver.addMarkByRule(mark, rule, 'b', noun1, Verb.IsNot, noun, msg); if (rs !== 0) return rs; } } return rs; } return inOppositeGroup; } export function getInSameGroup(solver, 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, Verb.IsNot, noun, msg); if (rs !== 0) return rs; } for (let noun of list2) { rs = solver.addMarkByRule(mark, rule, 'b', noun2, Verb.IsNot, noun, msg); if (rs !== 0) return rs; } return rs; } function inSameGroup(mark) { let rs = 0; const nounA = (noun1.type === nounType) ? noun1 : noun1.getPairNoun(nounType); const nounB = (noun2.type === nounType) ? noun2 : noun2.getPairNoun(nounType); const g1 = (nounA === null) ? -1 : map[nounA.num - 1]; const 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, Verb.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, Verb.IsNot, noun, msg); if (rs !== 0) return rs; } } if (nounA !== null || nounB !== null) return rs; const group1 = []; const group1Noun1 = []; const group1Noun2 = []; const group2 = []; const group2Noun1 = []; const group2Noun2 = []; for (let noun of nounType.nouns) { let i = noun.num - 1; const verb1 = solver.getGridVerb(noun, noun1); if (verb1 === Verb.Maybe) { if (map[i] === 0) group1Noun1.push(noun); else group2Noun1.push(noun); } const verb2 = solver.getGridVerb(noun, noun2); if (verb2 === Verb.Maybe) { if (map[i] === 0) group1Noun2.push(noun); else group2Noun2.push(noun); } if (verb1 === Verb.Maybe || verb2 === Verb.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; }
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.