Artificial intelligence

Polyominoes puzzle is one of the most famous single player games that can be played in so many forms. One of these forms consists of an n × m board that should be covered by some of a given collection of tiles in some certain order. [login to view URL] <a href="[login to view URL]"><img src="[login to view URL]" alt="CS340_Project_Spring_2017_2" border="0"></a> This project aims to build an efficient solver to solve a simpler version of Polyomino, where each one of its tiles contain some numbers that matches the main board position numbers. The player should find the best collection of tiles that covers all the board (if possible) without any overlapping. Problem Description The input: Given a set X and a collection S of subsets of X. The goal… Find a sub-collection S* of S that satisfies the two conditions: * The intersection of any two distinct subsets in S* is empty (no overlapping) . * The union of the subsets in S* is X. For example : Let set X = {1, 2, 3, 4, 5}, and S ={A, B, C, D, E} be a collection of subsets: * A={1, 5} * B={1, 3, 4} * C={3, 4} * D={2, 4} * E={3} The sub-collection S* = {A, D, E} is exact covering solution for X. Requirements 1. Incremental Formulation Give an incremental formulation for the exact cover problem, providing a precise definition of the following components: * Initial state. * Successor function. * Goal test. * Solution cost. 2. Optimization Problem Formulation Formulate the problem as an optimization problem, providing a precise definition of the following components: * Solution representation, i.e. how a candidate solution (sequence) is represented. * The objective function. Given a candidate solution following the representation you suggested, the objective function should return a numerical value to measure the quality of the solution. 3. Illustration Use the previous example to illustrate the components of questions 1 & 2. 4. Analysis Analyze the size of the state (i.e. search) space in terms of N where N is the number of subsets. 5. Neighborhood Function Based on the solution representation given in question 2, suggest at least one (or may be multiple) effective neighborhood function of a local search algorithm. Remember that a neighborhood function maps a candidate solution S to a set of other solutions by applying small (i.e. local) changes to S. 6. Genetic Algorithms Based on the solution representation given in question 2, suggest effective crossover and mutation operators of a Genetic Algorithm.