Find the most optimal algortihm to clear pieces off n × n chessboard.
There is a chessboard n × n, where some of the squares are inaccessible (you know what squares are accessible or not). The entire bottom row is occupied by pieces that can move one square forward, diagonally left forward, or diagonally right forward. In one move, all the pieces move at once (they can even stand still), but there must be no more than one piece per square. If the piece is on one of the square on the top row of the chessboard, it disappears. Design an algorithm that finds a minimum number of moves such that we can remove all the pieces from the board, or announces that there is no solution. This algorithm should have the best time and space complexity.
The algorithm should be described mainly in words (not code or semi code), thus the input or output doesn't have to be handled as precisely.
Also if possible the algorithm should use some sort of flow network (but if this requirement would mean that the solution isn't the most optimal time and space, it doesn’t have to be solved with that).
Iamjustjerry
- closed
- 797 views
- $15.00
Related Questions
- In how many different ways $n$ persons can seat around a round table?
- Solve summation problem: $\sum_{k=1}^{n} \tfrac{2k+1}{k^{2}(k+1)^2 } $
- Singular Value Decomposition Example
- Prove that $S \subseteq X$ is nowhere dense iff $X-\overline{S}$ is dense.
- [Intro to Topology] Verify if $K$ is compact
- Generalization of the Banach fixed point theorem
- [Discrete Mathematics] Big-O Notation
- Given locally limited $f:[0,1]→\mathbb{R}$, show that $Graph(f)$ is closed in $\mathbb{R^2}$ ⟺ $f$ is continuous using sequences
Do you really expect someone to answer this question for $3?
I reckon that people experienced in this field will have no problem comming up with the solution and shouldn't take much time to write it down. If nobody will answer I'll just increase the bounty.
Well, I think even people experienced in this field would take at the very least a couple hours to find a solution and to write it down. It's not my area of expertise, but I think the price range of this is in the hundreds. Certainly not 3$.
This was part of a test that had several questions and had time limit of 1 hour.
Really? I'm extremely surprised by this. I would have believed that if the pieces moved one at time, but all together and without knowing where the missing squares are, I find it hard to believe. Are you sure the text is right?
You know the position of the missing squares (will add it to the text). I was imagining doing by the representing each square as a vertex and then the pieces as sources, final row as sinks and by using flow network algorithm like Ford–Fulkerson you could get to the solution. You don't need to describe it very precisely.
Oh I see where you're going, if there are general results in graph theory that handle most of the work, then it might be doable within the timeframe. Not my area of expertise though, I hope you find someone who's more familiar with it.