Questions tagged [square-grid]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
0answers
17 views

Multiple objects in one cell: spread them across multiple cells following the flow of the 3d projection

I am facing what to me feels an almost impossible problem. I have some objects living in a 3d space. I want to create an interface with buttons where each buttons selects on of these objects. Since ...
1
vote
1answer
34 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 ...
1
vote
2answers
65 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.
2
votes
1answer
39 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 ...
3
votes
2answers
43 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 ...
6
votes
1answer
1k 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 ...
0
votes
1answer
122 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,...
1
vote
0answers
21 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 ...
2
votes
2answers
132 views

Finding the number of squares by connected coordinates

If I have a list of lists as below , ...
3
votes
1answer
442 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 ...
2
votes
1answer
93 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 ...
4
votes
1answer
147 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 ...
2
votes
2answers
855 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 : ...
3
votes
0answers
455 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 ...
0
votes
0answers
45 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 ...
4
votes
1answer
225 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 ...
9
votes
1answer
2k 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 ...
-2
votes
3answers
7k 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?
1
vote
1answer
2k 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 ...
5
votes
0answers
182 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 ...
3
votes
0answers
232 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 ...
15
votes
1answer
2k 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 ...
4
votes
2answers
470 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 ...
1
vote
1answer
859 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 ...
0
votes
1answer
199 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,...
6
votes
1answer
639 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)$. ...