Description
1 Overview
In this project, you will develop algorithm to solve Futoshiki game. Although there are several different approaches to solving Futoshiki puzzles, you will be developing a generic binary constraint satisfaction problem (CSP) solver to solve the puzzles.
2 TheFutoshikiPuzzle
TheFutoshikipuzzleisplayedonasquaregrid,suchas5x5. Theobjectiveistoplacethenumbers1to5(orwhatever the dimensions are) such that each row and column contains each of the digits 1 to 5. Some digits may be given at the start. Inaddition, inequalityconstraintsare alsoinitially specifiedbetweensomeofthesquares, suchthatonemust be higher or lower than its neighbor. These constraints must be honored as the grid is filled out.
(a) An unsolved Futoshiki puzzle. (b) A solved Futoshiki puzzle
Figure 1: An example of an “easy” Futoshiki puzzle (from http://www.futoshiki.org/. Numbers from 1 through 4 are filled such that each row and column contains each of the digits, and the inequalities are followed.
Like Sudoku, the game requires satisfying AllDiff constraints across rows and columns of the board. However, there will be additional binary constraints for the inequalities between the cells.
1
3 ProvidedCode
We have provided code to deal with the basic mechanics of the game, and some stub code for each problem already. In particular, the Futoshiki class provides methods to parse the board and produce binary CSPs. The following is a brief description of each class provided in the assignment3.py code:
• TheVariableclassrepresentsaparticularvariable(suchasX1). EachVariablehasanassociateddomain, which in the case of Futoshiki is either the integers 1 through N (the size of the board) or the number already displayed on the board. • The Variables classrepresentsacollectionof Variable objectswiththeabilityto“begintransaction”and “rollback”. The“rollback”methodwillrevertanychangesmadetothevariabledomains(andassignments)that occurred since the last “begin transaction” method. You should find this method useful for implementing the backtracking search with the AC3 inference. (See problem 3 for more details.) • The Constraint class represents a binary constraint between two variables var1 and var2. The constraint is satisfied (is satisfied(val1, val2) == True) when the values of var1 and var2 (val1 and val2)satisfytherelationshipspecifiedbyrelation. InthecaseofFutoshiki,“notequal”(operator.ne), “less-than” (operator.lt) and “greater-than” (operator.gt) relations are used. • The Constraints is a collection of Constraint objects with the ability to look up constraints by the variables. Italsohastheabilitytoreturntheneighborsofthenodeintheconstraintgraph, aswellasthe arcsinvolvedintheconstraints. Forexample,tofindallconstraintsinvolvingavariable Xi (neighborsof Xi), you can use
for constraint in constraints[x_i]: # All constraint.var1 are x_i constraint.is_satisfied(….)
Please see the class docstring for more detailed usages. • The BinaryCSP class defines a binary CSP problem, and it has the variables (a list of CSP variables) and constraints (an instance of Constraints). The assignment() method returns a dictionary of current variable assignments. (Note that this is provided for viewing purposes only, you probably do not need to use this method in your implementation.) • The Futoshiki class has methods to parse and print the board, as well as a method to produce a binary CSP (to binary csp()) and to use a CSP solver to solve a Futoshiki puzzle solve with()).
The Futoshiki board is represented with 0 for the “empty” cells and other numbers for pre-filled cells. “>”, “<”, “v” and “ˆ” (hat) characters are used to represent left-right and top-down inequalities. A typical initial Futoshiki board looks like the following:
input1.txt
0>0>0 0 v 0 0 0>0
0 0 0 0 ˆ
0 0<0 1
2
Utilities
You can use the fetch puzzle.py to fetch puzzles of various difficulties from http://www.futoshiki.org/. To do this, you can run the following in the command-line:
$ python fetch_puzzle.py [board size] [difficulty] [puzzle id]
For instance
$ python fetch_puzzle.py 4 1 128
To fetch 4x4 “easy” level puzzle (with ID=128). Once you’ve implemented a solver, you may also use the solve puzzle.py to solve a puzzle from the command line. By default, it calls the backtracking search method in p6 solver.py, but you can optionally specify a different python filename and a method name to use as the solver. For example:
$ python solve_puzzle.py < ../problems/p6/in/input1.txt
To solve the above puzzle, or
$ python solve_puzzle.py ../solutions/p3_basic_backtracking.py < ../problems/p6/in/input1.txt
to use the basic backtracking solver. You can also pipe the output from fetch puzzle.py directly, for e.g.
$ python fetch_puzzle.py 4 1 110 | python solve_puzzle.py
AutomatedTestCases
You can also perform a subset of automated testing by running test problems.py in the tests directory:
$ cd tests $ python test_problems.py
This executes the test corresponding to problems 1 to 6 by giving some input in the in directories and comparing the output against ones in out directories. The tests will be reported as a “failure” if the output of your code does not match the text files the out directories. A good practice is to run the tests before doing the problems and observe that theyfail. Then,onceyouimplementtheproblemscorrectly,yourtestsshouldpass. Therewillbemoretestcasesinthe actual online submission site, and you are encouraged to add more of your own inputs and outputs in the problems directory!
3
4 Problems
Problem1
Implement the is complete method that returns True when all variables in the CSP has been assigned. Hint: The list of all variables for the CSP can be obtained by csp.variables. Also, if the variable is assigned, variable.is assigned() will be True. (Note that this can happen either by explicit assignment using variable.assign(value), or when the domain of the variable has been reduced to a single value.)
Problem2
Implement the is consistent method that returns True when the variable assignment to value is consistent, i.e. it does not violate any of the constraints associated with the given variable for the variables that have values assigned. For example, if the current variable is X and its neighbors are Y and Z (there are constraints (X,Y ) and (X,Z) in csp.constraints), and the current assignment is Y = y, we want to check if the value x we want to assign to X violates the constraint c(x,y). This method would not not check c(x,Z), because Z is not yet assigned.
Problem3
Implementthebasicbacktrackingalgorithminthebacktrack()method. Itis“basic”inasensethatthevariableordering,valueorderingandinferenceheuristicsarenotimplementedyet. Inotherwords,youonlyneedtoimplement thebacktrack()methodinthisproblem. (Butyoushouldofcoursemakecallstotheselect unassigned variable() and other methods.) Hint: As noted earlier, you may find it necessary / useful to be able to revert any changes that have been made to the variable assignments and domain changes. To do this, you can use the transaction-inspired methods in the Variables class:
csp.variables csp.variables.begin_transaction() # Do whatever you need with the variables (assignment, domain reductions) csp.variables.rollback() # This undoes whatever
Problem4
ImplementtheAC3algorithminthe ac3() method. Dependingonthe arc parametergiven,itshouldalsoactasthe Maintaining Arc Consistency (MAC) algorithm described in p.218 of the textbook. You do not need to worry about preserving domain changes in this method.
Problem5
Implementthevariableandvalueorderingheuristicsinselect unassigned variableandorder domain values methods. For the variable heuristics, implement the minimum-remaining-values (MRV) and the degree heuristic as the tie-breaker. For the value ordering, implements the least-constraining-value (LCV) heuristic.
Problem6
Complete a faster backtracking search algorithm by augmenting the basic backtracking algorithm with the MAC inference and the variable and value ordering heuristics written so far.
4
Problem7
Submit a write-up for this project in PDF. You should include the following:
• Description of the problem and the algorithms used in the problems (culminating in the solution in Problem 6). • Run the solver you developed on different types of puzzles and measure how the solution time varies with the board size and difficulty ratings. Show your results in two separate graphs (one for the board size and another for the difficulty rating). Summarize your finding in a paragraph. • Extracredit: Youmayalsoanalyzetheeffectofeachtypeofheuristics(inference,variableandvalueordering). Compared to the basic solver in p3, how much does each type of heuristic speed up the solver for this problem? • A paragraph from each author stating what their contribution was and what they learned. Your writeup should be structured as a formal report, and we will grade based on the quality of the writeup, including structure and clarity of explanations.