3
$\begingroup$

I am looking for a very specific algorithm, so I think it doesn't exist yet. I would be satisfied if anyone was able to give me some hints to develop it.

My problem is about a square grid of size n x n, where n is an odd natural number ≥3. For instance, it can be a 5 by 5 grid:

.---.---.---.---.---.
|   |   |   |   |   |
.---.---.---.---.---.
|   |   |   |   |   |
.---.---.---.---.---.
|   |   |   |   |   |
.---.---.---.---.---.
|   |   |   |   |   |
.---.---.---.---.---.
|   |   |   |   |   |
.---.---.---.---.---.

The middle cell of the first column and the middle cell of the last column must be found:

.---.---.---.---.---.
|   |   |   |   |   |
.---.---.---.---.---.
|   |   |   |   |   |
.---.---.---.---.---.
| ● |   |   |   | ● |
.---.---.---.---.---.
|   |   |   |   |   |
.---.---.---.---.---.
|   |   |   |   |   |
.---.---.---.---.---.

Then, and this is the hardest part of the algorithm, I want to get a path from the left-most point to the right-most one, that goes through every cell of the grid.

For example, this is one possibility:

  > > v   > > > > v
  ^   v   ^       v
  ^   v   ^   v < <
  ^   v   ^   v    
  ●   v   ^   v   ●
      v   ^   v   ^
  v < <   ^   v   ^
  v       ^   v   ^
  > > > > ^   > > ^ 

and this is another:

  > > > > v   > > v
  ^       v   ^   v
  < < <   v   ^   v
      ^   v   ^   v
  ● > ^   v   ^   ●
          v   ^    
  v < < < <   ^ < <
  v               ^
  > > > > > > > > ^ 

This implies directly some obviousnesses. Let a be the number of up displacements, b down, c left and d right, we can know that:

  • a + b + c + d = n^2 - 1
  • a = b
  • d - c = n - 1

I also want to randomize the creation of this path, and the best would be a uniform distribution amongst all the possibilities (I don't know their number but I am almost sure it increases as n increases).

I think it can be solved thanks to graph theory since my grid can be considered as an unoriented graph where the vertices are the cells and where two adjacent cells are linked with an edge. The problem is now equivalent to making a non-redundant graph traversal, but I have no idea where to begin.

I hope my question was clear enough, thanks in advance.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.