Homework answers / question archive / Solving Aquarium Puzzle using CSP Aquarium puzzle _ uses a rectangular grid of cells divided into blocks (called aquariums), with numeric clues on each row and column

Solving Aquarium Puzzle using CSP Aquarium puzzle _ uses a rectangular grid of cells divided into blocks (called aquariums), with numeric clues on each row and column

Computer Science

Share With

---

Solving Aquarium Puzzle using CSP

Aquarium puzzle _ uses a rectangular grid of cells divided into blocks (called aquariums), with numeric clues on each row and column. The aim is to fill some of the cells with water according to the following rules:

• The water level of a block should be the same across its full width.
• A block can be filled up to a certain level, obeying the gravity law. If a cell in a block is filled with water, the cells below it should also be filled in that block.
• The clues denote the number of filled cells in each row and column.

For instance, an instance of this puzzle, and its solution are presented in Figure??.

 

 

Figure 1: (a) A sample initial board in Aquarium puzzle, and (b) its solution.

Represent Aquarium puzzle as a Constraint Satisfaction Problem (CSP). Find 3 Different Aquarium puzzles of different difficulties. Use an existing CSP solver, such as

• Google OR-Tools CP Solver: https: //developers.google.com/optimization/
• python-constraint: http: //labix.org/python-constraint/

To solve these puzzles based on the CSP representation. Make sure that your solution is readable by human; for instance, you can use a matrix to represent the board.

Submit the following files at SUCourse+:

• A pdf file containing your CSP representation of Aquarium puzzle, and a discussion on whether A* or CSP is more appropriate for solving this puzzle.

• The source files containing the representation of Aquarium puzzle and the puzzles presented to the CSP solver, and the solutions of the puzzles computed by the CSP solver.

In each of the deliverables above, please include your name and student id.

Demos Make a demo of your solution on 30 November. The time and places will be announced at SU Course+.