[Solved]: Solving AlienTiles with an A* heuristic

Problem Detail: 

Hello I am trying to solve the AlienTiles problem described at alientiles.com using the A* algorithm but I cannot find any good heuristic function so far.

In AlienTiles you have a board with $N \times N$ tiles, all coloured red. By clicking on a tile, all tiles in the same row and column advance to the next color, with the colour order being red $\rightarrow$ green $\rightarrow$ blue $\rightarrow$ purple, resetting to red after purple. A goal state is a state where every tile has the same colour, as long as its not red.

Is there any good point to start? I am completely frustrated about how I am supposed to handle the problem. An easy function that I came up with was the distance of the colour of the current tile with the target tile, but it is very slow.

Asked By : Mario

Answered By : D.W.

One candidate approach: for each color $c \in \{\text{green}, \text{blue}, \text{purple}\}$, try to define a distance heuristic $f_c(\cdot)$ that approximates the distance to the specific goal of getting all tiles to be the color $c$. For instance, if $s$ is a state, then $f_\text{green}(s)$ should be an estimate of the distance to the all-green state.

Next, given these heuristics, define a distance heuristic

$$f(s) = \min(f_\text{green}(s), f_\text{blue}(s), f_\text{purple}(s)).$$

Then you could use $f$ as your distance heuristic with $A^*$.

I leave it up to you to see if you can find a suitable definition of $f_c(s)$. One candidate would be the number of tiles in $s$ whose color is not $c$, but that's probably not going to work; you'll probably need something smarter.

---

If you're willing to use something other than the $A^*$ algorithm, there is an elegant solution to this problem using linear algebra.

Identify the colors red, green, blue, purple with the integers $0$, $1$, $2$, $3$, taken modulo 4 (so you are working in $\mathbb{Z}/4\mathbb{Z}$). Now you can solve the problem using linear algebra. In particular, the state $s$ is a $N^2$-vector over $\mathbb{Z}/4\mathbb{Z}$. Clicking on a tile at position $i,j$ corresponds to updating the state from $s$ to $s+v_{i,j}$, where $v_{i,j}$ is a fixed $N^2$-vector over $\mathbb{Z}/4\mathbb{Z}$. Thus, you can get from state $s$ to state $s'$ if and only if $s'-s$ is in the linear span of the $v_{i,j}$. If it is in the span, then find coefficients $c_{i,j} \in \mathbb{Z}/4\mathbb{Z}$ such that

$$s' - s = \sum_{i,j} c_{i,j} v_{i,j},$$

and this will give you a solution method: for each $i,j$, click on tile $i,j$ exactly $c_{i,j}$ times (order is irrelevant). You can use generalized Gaussian elimination to check whether $s'-s$ is in the span, and if so, to find the coefficients $c_{i,j}$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/20017

3.2K people like this

 Download Related Notes/Documents