The New Sudoku Players' Forum

[dobrichev]

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?

[David P Bird]

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.

[dobrichev]

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.

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.

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.

[David P Bird]

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.