Solved-Assignment 2: -Solving Akari using CSP -Solution

Description

Akari uses a rectangular grid of black cells and white cells.¹ The player solves puzzles via placing light bulbs in the white boxes according to following rules:

Light bulbs are permitted to be placed at any white square. A numbered square indicates how many light bulbs are next to it, vertically and horizontally.

Each light bulb illuminates from itself to a black square or the outer frame in its row and column.

Every white square must be illuminated and no light bulbs should illuminate each other.

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

(a) (b)

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

Represent Akari as a Constraint Satisfaction Problem (CSP). Find 3 different Akari 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/

Gecode: http://www.gecode.org/

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.

• http://www.nikoli.co.jp/en/puzzles/akari.html

CS 404, Artificial Intelligence

Submit the following files at SU Course:

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

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

Demos Make a demo of your solution at one of the following times:

The places will be announced at SUCourse.

Late policy Late assignments will be handled based on a system of “grace days”: you begin the term with two grace days, an assignment handed in from one minute to 24 hours late uses up one grace day, and 24:01 to 48 hours late uses up two grace days.

2