{"id":478,"date":"2024-02-18T09:49:31","date_gmt":"2024-02-18T14:49:31","guid":{"rendered":"https:\/\/www.notexponential.com\/notes\/?page_id=478"},"modified":"2025-03-15T11:15:48","modified_gmt":"2025-03-15T15:15:48","slug":"project-2-csp-tile-placement","status":"publish","type":"page","link":"https:\/\/www.notexponential.com\/notes\/artificial-intelligence\/projects\/project-2-constraint-satisfaction-problems-csp\/project-2-csp-tile-placement\/","title":{"rendered":"Project 2 &#8211; CSP &#8211; Tile Placement"},"content":{"rendered":"\n<h1 class=\"wp-block-heading\">Given<\/h1>\n\n\n\n<ul class=\"wp-block-list\">\n<li>You are given a landscape on which certain \u201cbushes\u201d grow, marked by colors: 1, 2, 3, 4.<\/li>\n\n\n\n<li>The landscape is of square shape, so, it might be 100 x 100 or 200 x 200 etc.<\/li>\n\n\n\n<li>You are given a set of \u201ctiles\u201d which are of three different shapes. The tiles are 4 x 4.&nbsp; One tile only covers part of the landscape.&nbsp; Here are the shapes<ul><li>Full Block: A \u201cfull block\u201d tile covers the full 4 x 4 area, and no bush is then visible in that patch.<\/li><\/ul><ul><li>An \u201couter boundary\u201d tile covers the outer boundary of the 4 x 4 area, and any bush in the middle part is visible.<\/li><\/ul>\n<ul class=\"wp-block-list\">\n<li>An \u201cEL\u201d shaped tile covers only two sides of the area.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>You are given a \u201ctarget\u201d of which bushes should be visible after you have finished placing the tiles.<\/li>\n<\/ul>\n\n\n\n<h1 class=\"wp-block-heading\">Observations<\/h1>\n\n\n\n<ul class=\"wp-block-list\">\n<li>The total tiles cover the entire landscape.&nbsp; However, depending on which tiles are placed where, different parts of the landscape, and hence different bushes are visible.<\/li>\n\n\n\n<li>The tiles can be rotated. This can change what bushes are visible. Rotating a boundary or full block tile obviously has no effect, but depending on the shape, it theoretically can. For EL shape, it obviously does.<\/li>\n\n\n\n<li>The number of tiles equals the size of the area divided by the size of tile.&nbsp; So, for 20 x 20 landscape, you are given 25 tiles.<\/li>\n<\/ul>\n\n\n\n<h1 class=\"wp-block-heading\">Input Files<\/h1>\n\n\n\n<p>Structure of the input file is as follows.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Landscape is given in a space delimited, new line separated.<\/li>\n\n\n\n<li>Tiles in terms of counts by different shapes.<\/li>\n\n\n\n<li>Target of how many different bushes should be visible.<\/li>\n<\/ul>\n\n\n\n<p>Many input files can be found at&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <a href=\"https:\/\/github.com\/amrinderarora\/ai\/tree\/master\/src\/main\/resources\/csp\/tileplacement\">https:\/\/github.com\/amrinderarora\/ai\/tree\/master\/src\/main\/resources\/csp\/tileplacement<\/a><\/p>\n\n\n\n<p>More input files can be generated using <a href=\"https:\/\/github.com\/amrinderarora\/ai\/blob\/master\/src\/main\/java\/edu\/gwu\/cs\/ai\/csp\/tileplacement\/TilePlacementProblemGenerator.java\">https:\/\/github.com\/amrinderarora\/ai\/blob\/master\/src\/main\/java\/edu\/gwu\/cs\/ai\/csp\/tileplacement\/TilePlacementProblemGenerator.java<\/a><\/p>\n\n\n\n<h1 class=\"wp-block-heading\">Algorithm<\/h1>\n\n\n\n<p>Write a CSP algorithm to solve this problem.&nbsp; The CSP algorithm should have the following components:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Search algorithm to solve the CSP<\/li>\n\n\n\n<li>Heuristics (min remaining values, least constraining value, tie breaking rules)<\/li>\n\n\n\n<li>Constraint propagation using AC3.<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Given Observations Input Files Structure of the input file is as follows. Many input files can be found at&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; https:\/\/github.com\/amrinderarora\/ai\/tree\/master\/src\/main\/resources\/csp\/tileplacement More input files can be generated using https:\/\/github.com\/amrinderarora\/ai\/blob\/master\/src\/main\/java\/edu\/gwu\/cs\/ai\/csp\/tileplacement\/TilePlacementProblemGenerator.java Algorithm Write a CSP algorithm to solve this problem.&nbsp; The CSP algorithm should have the following components:<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":469,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-478","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/www.notexponential.com\/notes\/wp-json\/wp\/v2\/pages\/478","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.notexponential.com\/notes\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.notexponential.com\/notes\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.notexponential.com\/notes\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.notexponential.com\/notes\/wp-json\/wp\/v2\/comments?post=478"}],"version-history":[{"count":3,"href":"https:\/\/www.notexponential.com\/notes\/wp-json\/wp\/v2\/pages\/478\/revisions"}],"predecessor-version":[{"id":584,"href":"https:\/\/www.notexponential.com\/notes\/wp-json\/wp\/v2\/pages\/478\/revisions\/584"}],"up":[{"embeddable":true,"href":"https:\/\/www.notexponential.com\/notes\/wp-json\/wp\/v2\/pages\/469"}],"wp:attachment":[{"href":"https:\/\/www.notexponential.com\/notes\/wp-json\/wp\/v2\/media?parent=478"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}