Announcement: Be excellent to each other.


Caravel Forum : Other Boards : Anything : OverUnder (Programming question)
New Topic New Poll Post Reply
Poster Message
disoriented
Level: Smitemaster
Rank Points: 1195
Registered: 08-07-2007
IP: Logged

File: sample_puzzle.gif (12.1 KB)
Downloaded 489 times.
License: Public Domain
icon OverUnder (+2)  
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:

quote:
// 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)

quote:
// 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

[Last edited by disoriented at 05-25-2016 05:23 AM]
05-25-2016 at 05:22 AM
View Profile Send Private Message to User Send Email to User Show all user's posts High Scores This architect's holds Quote Reply
Someone Else
Level: Smitemaster
Avatar
Rank Points: 1091
Registered: 06-14-2005
IP: Logged
icon Re: OverUnder (+2)  
I'm assuming that a solution is guaranteed? It might be better to start by checking which pairs are possible. For example, the 3 and the 8 in your example problem are not a valid set because the only solution including them isolates the 5. Similarly, the 3 and the 7 directly above it are not a good set. This should eliminate some of the ineligible combinations.

The best way to go about the above (IMO) would be to test each possible region and see if it is isolating. Remember, an isolating set only needs to separate an odd number of numbers off from the rest to be impossible.

If you find a region which must be included in the solution, you can run the isolating test again. This should remove a large portion of obviously bad sets.

For bonus points, this test could also look at the maximum and minimum number of tiles that one section could use. If, for example, one side of the region being examined contained (8,8,5,3) then it could use a minimum of 10 tiles and a maximum of 14.
05-25-2016 at 06:27 AM
View Profile Send Private Message to User Send Email to User Show all user's posts High Scores This architect's holds Quote Reply
TripleM
Level: Smitemaster
Rank Points: 1361
Registered: 02-05-2003
IP: Logged
icon Re: OverUnder (+2)  
Currently I assume you're looping over each pair and each valid region for that pair in no particular order. One possible optimisation - before each recursive step, loop over each pair and count how many valid regions there are for that pair. Find the one that results in the least regions - then recurse from there.

(That will actually implement some of Someone Else's suggestion indirectly.)

Edit - that was slightly incorrect since of course a specific pair doesn't need to be in the solution. What I really meant was - find which *single number* results in the least number of regions containing that and another number, and then try each of those recursively.

[Last edited by TripleM at 05-25-2016 11:20 PM]
05-25-2016 at 10:12 AM
View Profile Send Private Message to User Show all user's posts Quote Reply
disoriented
Level: Smitemaster
Rank Points: 1195
Registered: 08-07-2007
IP: Logged
icon Re: OverUnder (0)  
Thanks. Let's see if I have any luck implementing some of these suggestions.

____________________________
34th Skywatcher
05-26-2016 at 12:53 AM
View Profile Send Private Message to User Send Email to User Show all user's posts High Scores This architect's holds Quote Reply
Maurog
Level: Smitemaster
Avatar
Rank Points: 1496
Registered: 09-16-2004
IP: Logged
icon Re: OverUnder (+2)  
Here is how I would approach the problem:

* Let MAXSTEPS = highest number on the grid
* Give EACH NUMBER a unique identifier
* For each unique identifier do the following:
** Dijkstra from the number up to (MAXSTEPS-1) out to find the matching numbers using the following rules:
*** You're not allowed to go through numbers.
*** You're not allowed to take numbers which are +1 -1 or the same as the original number the identifier belongs to.
*** You're not allowed to take a number if the number of steps it took to reach it is >= than both the original and the found one.
** Save all found pairs of (id, second id) in the PAIRS vector (make you you don't take them twice).
* Now you can work with pairs, but first you will sort the vector:
** You will sort the vector by min(fist num, second num), with the lower pair minimum first.
** Within the groups with the same minimum, you will sort it by abs(first_num-second_num), with lowest being first.
* Now take the resulting vector of possible pairs and apply your original algorithm to it, the recursion should work faster.



____________________________
Slay the living! Raise the dead!
Paint the sky in crimson red!
05-26-2016 at 12:50 PM
View Profile Send Private Message to User Send Email to User Show all user's posts Quote Reply
Lucky Luc
Level: Smitemaster
Avatar
Rank Points: 1069
Registered: 08-19-2012
IP: Logged
icon Re: OverUnder (+2)  
I'm not really a good programmer either, not particularly good at this sort of algorithms, and I'm not sure if this is an improvement, but here's how I would try to relatively quickly eliminate a few possibilities:

While or after creating the master map, also create a "forced" region for each pair by connecting all possible regions via a logical AND. This region will include at least both number squares and at least in your example puzzle in many cases a bit more.

Before starting to actually lay out regions, overlay all forced regions. Remember which pairs of pairs share at least one forced square as they mutually exclude each other. (Note that this includes all pairs of pairs that share one number)

Maybe do some sorting now. In the beginning, all pairs are unmarked. Now start the recursion:
- if there are no unmarked pairs left, backtrack
- mark the first unmarked pair as used.
- mark all mutually exclusive pairs as unused.
- if the number of marked pairs sufficient, try to solve the puzzle with this setup. Afterwards backtrack.
- recurse.

Another thing that might be worth considering while actually trying to solve the puzzle with a given pair setup would be also looking storing a "possible" region for all pairs and overlaying those. If a square is empty, dismiss this setup right away. If a square contains only one possible pair, it must belong to that pair and all regions for that pair that don't contain said square can be dismissed. Not sure if this is worth implementing, though.

On a side note, do you keep track of how much memory your program uses? It sounds to me like the master map might be pretty memory-intensive and might be causing a slow-down?
05-28-2016 at 08:14 AM
View Profile Send Private Message to User Show all user's posts High Scores This architect's holds Quote Reply
disoriented
Level: Smitemaster
Rank Points: 1195
Registered: 08-07-2007
IP: Logged
icon Re: OverUnder (+2)  
I've implemented Someone Else’s (and TripleM’s) suggestions, and there's been a bit of improvement.
But it still takes many hours/days to solve a 7x7 grid.

The algorithm is now:
quote:
// 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
        Remove all regions that isolate areas of the grid containing 0 or an odd number of numbered squares
        Store an entry in the master region map: (this number pair) => (its calculated set of regions)


(Step 1 only happens once and doesn't take too long)
quote:
// 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... (starting with the pair containing the fewest regions in its map entry. Break ties using the minimum Manhattan distance)
    Get all regions from the "master region map" associated with this pair.
    For each region...
        If all squares in this region are unmarked...
            If this region would not isolate areas of the grid containing 0 or an odd number of numbered squares...
                Mark all squares in this region to indicate they are used.
                Recurse step 2
                Backtrack: unmark all squares in this region.




Since it's still too slow, are there any other tweaks I could add? Thank you in advance!

(I'd also be happy to post my code someplace, if anyone wants to take a peek at it.)

____________________________
34th Skywatcher

[Last edited by disoriented at 06-06-2016 07:23 AM]
06-05-2016 at 03:41 AM
View Profile Send Private Message to User Send Email to User Show all user's posts High Scores This architect's holds Quote Reply
disoriented
Level: Smitemaster
Rank Points: 1195
Registered: 08-07-2007
IP: Logged

File: three_puzzles.png (55 KB)
Downloaded 204 times.
License: Public Domain
icon Re: OverUnder (0)  
Here are some puzzles for you to try.

By the way, I was never able to write a program to solve this in a reasonable amount of time.



____________________________
34th Skywatcher

[Last edited by disoriented at 08-20-2017 10:10 PM]
08-20-2017 at 10:10 PM
View Profile Send Private Message to User Send Email to User Show all user's posts High Scores This architect's holds Quote Reply
Someone Else
Level: Smitemaster
Avatar
Rank Points: 1091
Registered: 06-14-2005
IP: Logged
icon Re: OverUnder (+2)  
I tried these puzzles and came up with some insights on coding the puzzle:

- Squares can be exclusive to one number. For instance, every possible set with the 5 on the left of the third puzzle includes the square directly above it. Removing every set which includes that square but not that 5 could cut the search size down some. You could run a function that checks if all sets containing a certain number share a square whenever a set is eliminated (on both numbers the eliminated set contained).

- Potentially, there could be something done with the total number of required squares. For instance, in the third puzzle there are 18 numbers - 9 pairs. The smallest of these are (2,2,3,3,4,4,5,5,6), requiring (3+3+4+4+5+5+6+6+7)=43 squares at minimum. As there are only 49 squares, that's only 6 squares extra.
I don't know if this would ever be an efficient thing to calculate, but it's something to potentially consider.
08-21-2017 at 04:51 PM
View Profile Send Private Message to User Send Email to User Show all user's posts High Scores This architect's holds Quote Reply
Pekka
Level: Master Delver
Rank Points: 268
Registered: 09-19-2007
IP: Logged
icon Re: OverUnder (+2)  
As a general idea, here's how to get some data on what your program is looking at. Take a random sample of the positions it is considering during search. Write the current position to a file at set intervals of time or after a number of changes to the position (marking or unmarking a region).

From these sample positions you can see what kind of situations the programs spends its time on. If you can come up with evaluation rules that let the program prune these positions sooner when the search is clearly not going anywhere, you should make the search go faster.

Another general rule is to guide the search with heuristics. The kind of data you get from the experiment I suggest can help with this too. Another way is to try something and see if it speeds or slows down the search. For example, we could reason that the areas of the puzzle with a lot of numbers have fewer combinations of possible regions that are legal, and direct the search to first pick regions that touch numbers that are near a lot of other numbers. Or, we could try to see if picking regions that touch the corners first helps.

These are things that require some experiments to see if they help. A simpler optimization is to use bit vectors for the regions. Assign each square of the grid a distinct power of two and set the bits to 1 that correspond to the squares that a region occupies. Checking to see if a region intersects with another or the set of marked squares is now just a logical AND operation, and updating the marked squares is a XOR (if the update is valid currently, which you check in advance).

A completely different and untested approach is to start with each square being its own region and then use the operation of joining two adjacent regions to reduce their number until the target of eight or nine regions meeting the puzzle criteria. This is again a search problem where you need to prune the unwanted search subtrees as early as possible, and I have no way of knowing if it is harder or easier to optimize than the current solution.

Perhaps I'll write my own program soon. This post had just some ideas for you to consider.
08-23-2017 at 06:37 AM
View Profile Send Private Message to User Show all user's posts High Scores This architect's holds Quote Reply
TripleM
Level: Smitemaster
Rank Points: 1361
Registered: 02-05-2003
IP: Logged
icon Re: OverUnder (+1)  
I managed to whip up a (completely awful, don't ask) program that solved two of the three puzzles in under a couple of minutes, though got stuck on the second as it's a lot less 'restricted'.

Basic idea was similar to the original approach, but just concentrate on which pairs of numbers go together - not the exact region that connects them.

Once you know the pairs, a lot of cells are forced to belong to a certain pair - you can then remove those as potential cells for other regions, and repeat.

Once that leads to no more forced cells, I started doing some recursion over options for which pair each remaining cell belongs to.

Plenty of improvements I can make, I feel like it should be able to solve all of these puzzles quite quickly if done right.

Click here to view the secret text


[Last edited by TripleM at 08-24-2017 05:42 AM]
08-24-2017 at 05:39 AM
View Profile Send Private Message to User Show all user's posts Quote Reply
disoriented
Level: Smitemaster
Rank Points: 1195
Registered: 08-07-2007
IP: Logged
icon Re: OverUnder (0)  
The first solution posted is a bit off - just fix the lower left part.

Really nice work!

Would you be willing to share your code for this?

____________________________
34th Skywatcher

[Last edited by disoriented at 08-24-2017 07:16 AM]
08-24-2017 at 07:16 AM
View Profile Send Private Message to User Send Email to User Show all user's posts High Scores This architect's holds Quote Reply
disoriented
Level: Smitemaster
Rank Points: 1195
Registered: 08-07-2007
IP: Logged

File: IMG_1945.PNG (68.9 KB)
Downloaded 90 times.
License: Public Domain
icon Re: OverUnder (0)  
A more advanced puzzle to test your solver on:

Click here to view the secret text


____________________________
34th Skywatcher

[Last edited by disoriented at 08-24-2017 07:18 AM]
08-24-2017 at 07:18 AM
View Profile Send Private Message to User Send Email to User Show all user's posts High Scores This architect's holds Quote Reply
TripleM
Level: Smitemaster
Rank Points: 1361
Registered: 02-05-2003
IP: Logged

File: overunderdlx.cpp (4.9 KB)
Downloaded 1 times.
License: Public Domain
icon Re: OverUnder (+3)  
Ah yep, that was a transcription error rather than a code error.

That version of my code is currently too ugly to share. Maybe when I come up with a better version :P

However, I tried scrapping the whole thing and going with a completely brute force recursive approach for comparison (without even testing for isolated regions etc) - this one is attached.

It struggles to solve the 7x7 examples, but interestingly, the last puzzle you posted is far far easier - it found the solution within a few seconds, and took 34 seconds in total to prove it was unique.

Plus probably a lot more to draw that answer into a picture, so here's the raw output:

Click here to view the secret text


Am using DLX to handle the recursion quickly.

PS - when I said struggled, it did manage to come up with the answer I was lacking - probably took 10+ minutes though.

Click here to view the secret text


[Last edited by TripleM at 08-25-2017 02:01 AM]
08-25-2017 at 12:06 AM
View Profile Send Private Message to User Show all user's posts Quote Reply
New Topic New Poll Post Reply
Caravel Forum : Other Boards : Anything : OverUnder (Programming question)
Surf To:


Forum Rules:
Can I post a new topic? No
Can I reply? No
Can I read? Yes
HTML Enabled? No
UBBC Enabled? Yes
Words Filter Enable? No

Contact Us | CaravelGames.com

Powered by: tForum tForumHacks Edition b0.98.8
Originally created by Toan Huynh (Copyright © 2000)
Enhanced by the tForumHacks team and the Caravel team.