Number aligning

For fans of all other kinds of logic puzzles

Number aligning

Postby dobrichev » Mon Dec 10, 2012 9:01 pm

We have a square N * N matrix of integers populated with random values between 1 and vMax.
If 2 adjacent values in a row or in a column (Von Neumann neighborhood) are equal, then they are cleared to zero.
We have a predefined number of M moves to do. Each move changes the value of a single cell to some other value in the range.
The goal is to play all moves so that as much as possible cells are cleared for a fixed time.
Each move is a transaction. If 3 cells in a row become with equal values, then the last move should change the middle cell in order all 3 cells to be cleared. The same is valid for the corner of the 3 cell L shape, and for the center of the 5 cell + shape.
N is about 1000, vMax is about 5000, M is about 100, time limit is about 3 seconds computer execution time.
It is supposed that the time is insufficient to find the best possible solution so the target is finding some "good" solution.

Does this problem have its own name? Are there known applicable theories? How an efficient computer algorithm will look like?
dobrichev
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

Re: Number aligning

Postby David P Bird » Tue Dec 11, 2012 9:43 am

dobrichev from your figures the average number of cells to be cleared per move = N x N / M = 1,000 x 1,000 / 100 = 10,000.

From your description the maximum number of cells that can be cleared in one move is a 5-cell cross when the centre cell is set to a common value last. If any more adjacent cells were set the to same value before this, then they would be cleared automatically whenever a touching pair was created.
David P Bird
2010 Supporter
 
Posts: 960
Joined: 16 September 2008
Location: Middle England

Re: Number aligning

Postby dobrichev » Tue Dec 11, 2012 2:31 pm

David P Bird wrote:From your description the maximum number of cells that can be cleared in one move is a 5-cell cross when the centre cell is set to a common value last.

Yes.

David P Bird wrote:If any more adjacent cells were set the to same value before this, then they would be cleared automatically whenever a touching pair was created.

This is a matter of clarification of the initial state. Suppose that initially there are NO adjacent cells set to the same value.

David P Bird wrote:the average number of cells to be cleared per move = N x N / M = 1,000 x 1,000 / 100 = 10,000.

I can't get your point.
dobrichev
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

Re: Number aligning

Postby David P Bird » Tue Dec 11, 2012 3:57 pm

Dobrichev you replied just as I was trying to delete my post! Even though I read your post a couple of times I had the mistaken impression that the objective was to clear all the cells, not just as many as possible. This made me think that one of your figures was probably a typo.

In a grid with no duplicated values it seems that the best that can be achieved is to clear two cells per move. The only way I see this being improved is to locate cells with duplicated values that are close together. This seems to require a sort routine for the values and their positions.

From a method I use to locate group nodes in Sudoku, I have a feeling that the easiest way to determine if cells are close together is to use a modification of the most canonical grid to number cells in regions to allow simple proximity checks to be run.

As I'm not well enough equipped to follow this up any further, I'm afraid that's where I must leave it for now.
David P Bird
2010 Supporter
 
Posts: 960
Joined: 16 September 2008
Location: Middle England


Return to Other logic puzzles