# Question

Minesweeper, the well-known computer game, is closely related to the wumpus world. A minesweeper world is a rectangular grid of N squares with M invisible mines scattered among them. Any square may be probed by the agent; instant death follows if a mine is probed. Minesweeper indicates the presence of mines by revealing, in each probed square, the number of mines that are directly or diagonally adjacent. The goal is to have probed every un-mined square.

a. Let Xi,j be true ill square [i, j] contains a mine. Write down the assertion that there are exactly two mines adjacent to [1, 1] as a sentence involving some logical combination of Xi,j propositions.

b. Generalize your assertion from (a) by explaining how to construct a CNF sentence asserting that k of ii neighbors contain mines.

c. Explain precisely how an agent can use DPLL to prove that a given square does (or does riot) contain a mine, ignoring the global constraint that there ate exactly M mines in all.

d. Suppose that the global constraint is constructed via your method from part (b). How does the number of clauses depend on M and N? Suggest a way to modify DPLL so that the global constraint does not need to be represented explicitly.

e. Are any conclusions derived by the method in part (c) invalidated when the global constraint is taken into account?

f. Give examples of configurations of probe values that induce long-range dependencies such that the contents of a given un-probed square would give information about the contents of a far-distant square

a. Let Xi,j be true ill square [i, j] contains a mine. Write down the assertion that there are exactly two mines adjacent to [1, 1] as a sentence involving some logical combination of Xi,j propositions.

b. Generalize your assertion from (a) by explaining how to construct a CNF sentence asserting that k of ii neighbors contain mines.

c. Explain precisely how an agent can use DPLL to prove that a given square does (or does riot) contain a mine, ignoring the global constraint that there ate exactly M mines in all.

d. Suppose that the global constraint is constructed via your method from part (b). How does the number of clauses depend on M and N? Suggest a way to modify DPLL so that the global constraint does not need to be represented explicitly.

e. Are any conclusions derived by the method in part (c) invalidated when the global constraint is taken into account?

f. Give examples of configurations of probe values that induce long-range dependencies such that the contents of a given un-probed square would give information about the contents of a far-distant square

## Answer to relevant Questions

This exercise looks into the relationship between clauses and implication sentences. a. Show that the clause (—P1 V . . . V —Pm VQ) iS logically equivalent to the implication sentence (P1 Λ . . . Λ Pm) ...A logical knowledge base represents the world using a set of sentences with no explicit structure. An analogical representation, on the other hand, has physical structure that corresponds directly to the structure of the ...What axiom is needed to infer the fact Female (Laura) given the facts Male (Jim) and Spouse (Jim, Laura)?Write out the axioms required for reasoning about the wumpus’s location, using a constant symbol Wumpus and a binary predicate In (Wumpus, Location). Remember that there is only one wumpus.One might suppose that we can avoid the problem of variable conflict in unification during backward chaining by standardizing apart all of the sentences in the knowledge base once and for all. Show that, for some sentences, ...Post your question

0