I’m not an “ace programmer” by any means, but I know some people on this forum are very good at this stuff.
This puzzle, which I mentioned to skell, Chaco, and some others in chat, was recently added to the “Logic Games” iOS app, and it seemed interesting enough to make me want to write a solver program for it.
Given an NxN grid with some cells containing numbers, the objective is to divide the grid into regions such that every region contains two numbers, and the size of the region is strictly between the numbers.
Example:
Click here to view the secret text
×
So here is my approach to an algorithm. The problem is that it runs very, very slowly (takes days or weeks to solve even a 7x7 grid). I was hoping someone might suggest a low-hanging optimization.
Here is the algorithm:
// Step 1. Prepopulate a “master region map”, which can be referred to later. This is faster than calculating the regions every time.
For every possible pair of numbers in the grid...
If the difference between the numbers is at least 2, and the Manhattan distance between their locations is not too large...
Calculate all possible regions for this number pair, excluding those regions too small or large in size or containing any other number
Store an entry in the master region map: (this number pair) => (its calculated set of regions)
(Fortunately, Step 1 only happens once and doesn’t take too long)
// Step 2. Search for regions that meet the criteria. At the beginning, all grid squares are unmarked.
If no numbers in the grid are unmarked...
Return solution
Else: for every pair of unmarked numbers in the grid...
Get all regions from the “master region map” associated with this pair.
For each region...
If all squares in this region are unmarked...
Mark all squares in this region to indicate they are used.
Recurse step 2
Backtrack: unmark all squares in this region.
Step 2, the recursive step, takes forever. Doing a bit of timing, the program appears to be spending the most time in the red highlighted line. It’s a pretty simple function:
for (OUSq sq : region.getAllSquares())
{
if (sq.marked)
{
return false;
}
}
return true;
Anyway, I'm not sure how to optimize this.
____________________________
34th Skywatcher
Best to PM me, since I might miss your message on CaravelNet chat.
[Last edited by disoriented at 05-25-2016 05:23 AM]