This challenge is inspired by this app. The test cases are borrowed from that app.
This is a fastest-code challenge, where the objective is to solve the largest test cases in the least amount of time. There are provided some smaller test cases, so that people might test their algorithms faster.
You'll be given a square input grid, of dimensions n-by-n where 9 <= n <= 12. This grid will be divided into n areas, where the cells of each area has a unique identifiers (I'll use lower case letters from a-l in the the text here, but you may choose whatever you like, for instance integers 1-12).
The input may look like this (optional input format):
aabbbbbcc adddbbbcc adeeecccc adddefgcc hhhdifggg hdddifffg hhhiifffg hihiifffg iiiiiiggg
Or, easier to visualize:
You are to place 2*n trees in this park, according to the following rules:
- There shall be exactly 2 trees per column, and 2 trees per row
- All areas shall have exactly 2 trees.
- No trees can be adjacent to another tree, vertically, horizontally or diagonally
The solution to the layout above is:
Note: There is only one solution to each puzzle
- The input and output formats are optional
- The output might for instance be a list of indices, a grid with 1/0 indicating if there's a tree in that position, or a modified version of the input where the trees are indicated
- The execution time must be deterministic
- The program must finish withing 1 minute at @isaacg's computer
- Specs: 4 CPUs, i5-4300U CPU @ 1.9 GHz, 7.5G of RAM.
- In case your program can't solve the two largest test case in one minute each then the time for the second largest (n=11) will be your score. You'll lose against a solution that solves the largest case.
I might edit this list if submissions seems to be customized to fit these test cases.
--- Input --- aaaaabccccdd aaaaabccccdd aaaaabbbbddd eeeafffgbghh eeaafffgbghh eefffffggghh eeefijffghhh iieiijjjjkhh iiiiijjjjkhk lljjjjjjjkkk llllllkkkkkk llllllkkkkkk --- Solution --- aaaaabcccCdD aaaaaBcCccdd aAaaabbbbdDd eeeaffFgBghh eeAaFffgbghh eefffffGgGhh EeefijffghhH iiEiIjjjjkhh IiiiijjjjkHk lljJjJjjjkkk lLllllkkKkkk lllLllKkkkkk
--- Input --- aaaaaaabbcc adddabbbbcc edddbbbbbbc eddddbbbbbb effffggghhh effffgghhii eefffjjhhii eeeejjjhhii eeejjjjkiii jjjjjjkkiii jjjjjkkkiii --- Solution --- aaAaaaabbCc adddAbBbbcc eDddbbbbbbC eddDdBbbbbb effffggGhHh eFfffGghhii eefFfjjhHii EeeejjjhhiI eeEjjjjKiii JjjjJjkkiii jjjjjkKkIii
--- Input --- aaaaabccdd aeaabbbccd aeaabfbgcd eeeaafggcd eeeaafghcd eeeiifghcd ieiiigghcd iiijighhcd jjjjighhcd jjjggghhdd --- Solution --- aaAaabccdD aeaaBbBccd aEaabfbgcD eeeaaFgGcd eEeAafghcd eeeiiFghCd IeiIigghcd iiijigHhCd JjJjighhcd jjjgGghHdd
--- Input --- aabbbbbcc adddbbbcc adeeecccc adddefgcc hhhdifggg hdddifffg hhhiifffg hihiifffg iiiiiiggg --- Solution --- aAbBbbbcc adddbbBcC adEeEcccc AdddefgCc hhhDiFggg hDddifffG hhhiIfFfg HiHiifffg iiiiiIgGg --- Input --- aaabbbccc aaaabbccc aaaddbcce ffddddcce ffffddeee fgffdheee fggfhhhee iggggheee iiigggggg --- Solution --- aaAbBbccc AaaabbcCc aaaDdBcce fFddddcCe fffFdDeee fGffdheeE fggfHhHee IggggheeE iiIgggGgg