Description

P02CSPandKRR

Yikun Liang
Contents
1 Futoshiki (GAC, C++/Python) 2
1.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Tasks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 Blocks World (Planner, Prolog) 5
2.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Tasks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3 Notes 8
1 Futoshiki (GAC, C++/Python)
1.1 Description
Futoshiki is a board-based puzzle game, also known under the name Unequal. It is playable on a square board having a given fixed size (4 × 4 for example), please see Figure 1.
The purpose of the game is to discover the digits hidden inside the board’s cells; each cell is filled with a digit between 1 and the board’s size. On each row and column each digit appears exactly once; therefore, when revealed, the digits of the board form a so-called Latin square.
At the beginning of the game some digits might be revealed. The board might also contain some inequalities between the board cells; these inequalities must be respected and can be used as clues in order to discover the remaining hidden digits.
Each puzzle is guaranteed to have a solution and only one.
You can play this game online: http://www.futoshiki.org/.

Figure 1: Futoshiki Puzzles
1.2 Tasks
1. You should use GAC algorithm to implement a Futoshiki solver by C++ or Python.
2. If necessary, you could add some heuristic strategies to speed up your algorithm.
3. You should run the following 5 test cases to verify your solver’s correctness and efficiency in Figure 2, 3, 4, 5, and 6, and I will grade your codes in GAC implementation, correctness of 5 cases and algorithm efficiency.
4. Don’t forget you have implemented this game by FC algorithm in E04.

Figure 2: Futoshiki Test Case 1

Figure 3: Futoshiki Test Case 2

Figure 4: Futoshiki Test Case 3

Figure 5: Futoshiki Test Case 4

Figure 6: Futoshiki Test Case 5
2 Blocks World (Planner, Prolog)
2.1 Description
Planning in the blocks world is a traditional planning exercise, and you can recall what we have introduced in class in Figure 7:
An exercise: blocks world planning
There are a collection of blocks: a block can be on the table, or on top of another block. There are three predicates: clear(x): there is no block on top of block x; on(x,y): block x is on top of block y; and onTable(x): block x is on the table.
There are three actions:
move(x,y,z): move block x from block y onto block z, provided x is on y, both x and z are clear; moveFromTable(x,y): move block x from the table onto block y, provided x is on the table, both x and y are clear; and moveToTable(x,y): move block x from block y onto the table, provided x is on y, and x is clear.
a
b
c
a
b
c
The initial state isThe goal state is
Y. Liu Intro to AI 80/81
Figure 7: Blocks World
Here are several hints for you to develop a blocks world planner by using Prolog:
• You can represent the states with on(Block,Object) and clear(Object). You’d better take into account the location of the blocks, so Objection can be a block or a place.
• The only kind of action can be move(Block,From,To).
• Each available action is defined in terms of its precondition and its effects. Preconditions can be defined by the procedure can(Action,Cond). The effects of an action can be defined by two procedures:adds(Action,AddRels) and deletes(Action,DelRels).
• The planner aims at finding a plan, that is, a sequence of actions, which achieves the goal. You can adopt the principle of planning by means-ends analysis illustrated in Figure 8:
• In order to delete unnecessary steps, you can consider avoiding those actions that destroy goals.

Figure 8: The Principle of Means-Ends Planning
2.2 Tasks
• Please develop a planner to solve the blocks world problem by using Prolog.
• There are 5 cases (Figure 9, Figure 10, Figure 11, Figure 12 and Figure 13) for you to test the performance of your planner. I will grade your planner in correctness of cases, the number of steps, and time cost.
• Adopting breadth-first and best-first heuristic can accelerate the planner, however, you can optimize your planner by using better heuristic functions or other means.

Figure 9: Blocks World Case 1

Figure 10: Blocks World Case 2

Figure 11: Blocks World Case 3

Figure 12: Blocks World Case 4

Figure 13: Blocks World Case 5
3 Notes