Questions tagged [square-grid]
The square-grid tag has no usage guidance.
38
questions
16
votes
1
answer
3k
views
Are "Flow Free" puzzles NP-hard?
A "Flow Free" puzzle consists of a positive integer $n$ and a set of (unordered) pairs of distinct vertices in the $n \times n$ grid graph such that each vertex is in at most one pair. A solution to ...
user12859
12
votes
1
answer
4k
views
Treewidth of k x k square grid graphs
According to some slides I found on google, the treewidth of any $k \times k$ square grid graph $G$ is $tw(G) = k$. I just started researching about treewidth and tree decomposition, and for the most ...
- 293
6
votes
1
answer
3k
views
Can someone explain this formula for calculating Manhattan distance?
This is from a Kickstart problem:
Note: The Manhattan distance between two squares (r1,c1) and (r2,c2)
is defined as |r1 - r2| + |c1 - c2|, where |*| operator denotes the
absolute value.
Then ...
- 275
6
votes
1
answer
765
views
Route on a square grid with only (x,y) → (x,x+y) and (x,y) → (x+y,y) moves
This problem is about finding a route on a square grid.
The starting point is $(1,1)$ and the target point $(n,m)$.
I can move each step from my current point $(x,y)$ either to $(x+y,y)$ or $(x,y+x)$.
...
- 201
6
votes
0
answers
215
views
Upper bound on the number of hamiltonian cycles on a $n \times n $ grid graph
What is the best upper bound that is known for the number of hamiltonian cycles on a $n \times n $ grid graph?
I did some searching and found that the number of hamiltonian cycles on a planar graph ...
- 161
4
votes
1
answer
316
views
Find a simple cycle in an undirected subgraph of a grid graph that encloses the most faces
Imagine a finite $n*n$ grid graph $G(V,E)$, much like a chessboard. Imagine further an undirected subgraph $H(V',E')$ of $G$. Let us call the squares of chessboard $G$ "faces". A DFS algorithm can ...
- 41
4
votes
2
answers
598
views
Largest N squares that fit in a rectangle
I was working on a project and I needed to display N squares inside a rectangle area and I want them to be as large as possible, no rotations. More formally:
Problem: Given N equal-sized squares and ...
- 141
4
votes
0
answers
58
views
Algorithm to find equivalent classes of homotopic pathes on a grid with obstacles
Given a $n \times n$ grid with some walls and two cells $a$ and $b$, I want to compute the non-homotopics paths from $a$ to $b$ on this grid. A path is a sequence of adjacent cells (diagonal does not ...
- 141
4
votes
1
answer
261
views
Maximizing number of selected squares in a grid
We have an $n\times n$ grid of squares, each square has a non-negative integer. Two distinct squares are neighbours if they share a row or column. A selection of squares is good if every selected ...
user26358
3
votes
2
answers
136
views
Maximize enclosed area of given figures on 2d grid
I need to solve an optimization problem for a given set of polyominoes, for example the five Tetrominoes known from Tetris. The goal is to place each one of the figures on the 2d grid, so the area ...
- 33
3
votes
2
answers
91
views
Finding a hamiltonianISH path in a graph
Problem statement
Given a graph of all the blue squares in the following image where each blue square is connected to other blue squares in all 4 cardinal directions.
Given any starting node.
What ...
- 201
3
votes
1
answer
582
views
Find smallest enclosing circle
On a 2d plane, there is a large circle centered at $(0, 0)$ with a radius of $R_{{o}}$. It encloses $\sim 100$ or so smaller circles distributed randomly across the parent circle otherwise with known ...
- 133
3
votes
2
answers
1k
views
Efficient algorithm to find minimum steps to cover all the given points in infinite 2D grid?
Problem statement: You are in an infinite 2D grid where you can move in any of the 8 directions :
...
- 1,303
3
votes
0
answers
599
views
Algorithm to traverse all unblocked $1*1$ squares in a $n*m$ grid
Given a $n*m$ grid, some $1*1$ squares are blocked(can't be entered) and some are unblocked(can be entered).
What is the algorithm which prints the shortest path, such that the path covers all ...
- 31
3
votes
0
answers
291
views
Approximation ratio of a greedy grid-cover algorithm
We're given a $N\times M$ grid, and we want to cover all coordinates in the greedy by rectangles of size $\le k$.
Consider the following greedy algorithm. At each iteration, it chooses a rectangle ...
- 2,634
2
votes
2
answers
193
views
2
votes
1
answer
149
views
Algorithm to find player position in a 2D grid when all you know is the directional steps he has taken
Given the 2D grid shown below, where blue tiles can be visited and island tiles cannot.
Given that we do not know the starting position of a player on this grid.
Given that the player can move 1 ...
- 201
2
votes
1
answer
143
views
Finding the best poker hand in a connected grid structure where order matters
I am trying to find the best poker hand in a connected grid, where order matters. An illustration is the best way of explaining the situation.
This grid has 12 random cards, in random positions. Each ...
- 23
1
vote
1
answer
63
views
Recreate a spanning tree in a grid graph given vertex descriptions
Let's assume I have graph above with spanning tree pointed out by blue edges.
Vertex at position (1,1) (row 1, column 1) is connected to the bottom vertex and has degree 1.
Vertex at position (4,2) (...
- 175
1
vote
1
answer
23
views
Condition for detection of collision in an algorithmic problem
While solving This algorithm problem I was unable to come up with condition for the collision to occur ( other than the naive O(n^2) algorithm ) on reading the explanation they say
Let’s deepen the ...
- 219
1
vote
1
answer
3k
views
Square sub-grid with maximum sum
Given $N$ points in a grid having some weight, I have to find the side length of a square sub-grid with maximum sum of weight of points contained in that square sub-grid. Also square sub-grid must ...
- 19
1
vote
1
answer
1k
views
Shortest path from starting cell to all cells in the grid
I found an algorithm for finding the shortest path on grid between selected cell, to all cells on the grid, with $O(KN)$ where $K$ is the number of neighbor cells and $N$ is the number of cells.
How ...
- 909
1
vote
1
answer
265
views
Algorithm to find the path with minimum bending points on a square grid board
Let's suppose we have a square grid board like the one shown in the picture below:
I'm wondering how I can find the path with minimum number of "bending" points (like the ones shown in red) ...
- 153
1
vote
1
answer
107
views
How to mathematically determine row, column, and sub-square of cell in nxn array where n is a perfect square?
Given an one dimensional array of size nxn, where n is a perfect square
How can one mathematically determine the row, column, and/or sub-square the cell resides in? Additionally, is there a ...
- 113
1
vote
1
answer
156
views
SAT formula for connected graphs on the grid
In the answer to an earlier question "SAT algorithm for determining if a graph is disjoint" a formula is constructed that is satisfiable iff a given graph is connected.
The formula uses a ...
- 30.6k
1
vote
0
answers
28
views
1
vote
2
answers
386
views
Grid Puzzle Split Algorithm
I want to generate a random partition of an $N\times N$ grid into $N$ connected groups having $N$ tiles each. How would I do this? Max grid size will be 10x10. Below is an example for a 5x5 grid.
- 13
1
vote
0
answers
26
views
Grid treaversal with forbidden coordinates
What alorithm/heuristic can be applied to get a shortest path to all the blue coordinates below without going through red coordinates? starting and ending in bottom left(0,0).
I have list of all the ...
- 11
0
votes
1
answer
812
views
Maximum flow on a n ×n grid
I am currently dealing with a network flow problem and I am trying to find some similar solved problems to help me formulate my solution.
The text is:
You are the owner of a large chain of franchise ...
0
votes
1
answer
31
views
Combining chunks on an infinite grid into regions
I am working on an floorplan application where I save elements on an infinite grid in a sparse manner. Specifically, I have the following Python class representing a sparse grid (basically a ...
- 103
0
votes
1
answer
56
views
Detect contour from point grid
Suppose we have a grid of points (which can also be very dense 10000x10000) like the one in the figure in which the points are marked with two different colors.
What is the best algorithm from a ...
- 5
0
votes
1
answer
203
views
Grid Based DP: How do we tweak the Travelling Salesman Problem to work with Grids
The question is:
There is a n x n grid (Maze) which has either 0, 1 or 2. 0 means a path
exists, 1 means the cell is blocked and 2 means there exists gold in
that cell. Task is to start from 0,...
- 245
0
votes
0
answers
47
views
Display XY data on computer
I would like to experiment with displaying the output of an analog to digital converter on computer. Samples of the ADC output would determine the intensity of one pixel.
The input to the ADC is an ...
0
votes
0
answers
79
views
How to reposition an undirected weighted graph on a 2D grid where strongly connected nodes stay together?
I have an undirected fully-connected weighted graph of $n$ nodes, where $n=m\times m$. I want to visualize this graph on an $m$ x $m$ 2D grid. My goal is to place nodes connected with edges of higher ...
0
votes
0
answers
31
views
find maximum number of sections that satisfies the condition in a grid
Here is the description of a problem
Given an array of strings representing an $N$x$N$ grid of $red$ and $blue$ cells and a target color $r$ or $b$, partition the grid into $N$ sections of $N$ ...
- 125
0
votes
0
answers
71
views
Using counting to build a grid world
For this question, I have tried everything that I can think of, but cannot solve it. What I want to do is iterate over all possible values of $z_1$, but every method I use, it requires me to know ...
- 101
0
votes
1
answer
232
views
Find a continuous path filling whole 3xN grid going through certain points in given order
I've got a grid consisting of squares that is 3 squares high and N squares long.
Some of the squares are filled with numbers that are not greater than 3*N. You can move only to squares that are below,...
- 41
-1
votes
3
answers
14k
views
Draw a 5 × 5 grid graph. How many edges does the n × n grid graph have?
just confuse with this problem. What is n × n grid graph and how many edges it has?
- 17