AI coding

Hello /prog/
Reposted from /g/
I'm trying to find a heuristic function capable of solving the problem described at www.alientiles.com for my AI class.
The problem is essentially this: There is a NxN board of zeros. A click on one of them increases all the numbers in the same row and column by 1 mod 4. The goal is to reach a specified goal state (eg all ones).
I've tried some obvious solutions, such as summing the distance of each tile to its goal and using that as the distance to the goal, but nothing has been working very well.
The only thing I've found on the net is about symmetry breaking, which I'm already working on.
Of course I'm not asking you to solve my homework, but some ideas or tips or anything I could read to help me.
Thanks.

Sounds a lot like the n queens problem.

install BSD/Gentoo

Maybe use a genetic algorithm? Generate the sequence of positions to click, and after the clicks are done run the fitness function, which`d be the number of one tiles.

One problem would be that you don`t know the number of clicks it would take.

Did you read your AIMA today?

for N=2 // all ones, you click each tile once to get all threes, do again for all twos, and a third times gives all ones

12 clicks at +3 per click gives +36, divide four squares gives 9... 9 mod 4 = 1?

so, N=3 // all ones...
+5 per click / nine squares..

do you just click each square once?

9*5 / 5 mod 4 = 1?

whoops, / 9

hmm..
So, for a board N with residual x, each click gives 2N -1..
Minimum number of clicks to x is, uh...

c(2N-1) mod (4*N*N) = x ?

Thank you all for the replies.
Yes, you can click each square once, or you can click each square in any column or row twice and get to one of the goal states. I also know that, by clicking in a specific pattern, you can advance a single specific tile by two. Thing is, I need to find a heuristic that can find the fastest solution to any state, from any state using the A* algorithm.
I believe that the problem can be expressed with maths. The sum of clicks on each square's row and column mod 4 must be equal to the distance of that square to the goal. By doing this for each square, I can end up with a (rather large) linear system. I'm not sure I can use this to come up with a heuristic though.
Also yes, I've read my AIMA plenty, haven't found anything helpful in it.

YOU HAVE BEEN VISITED BY LE GREEN SAD NEGRO FROGE OF SADDNESS
REPOST THIS IN 100`000 threads or be a frog!

`
           ████████     ██████       
         █░░░░░░░░██ ██░░░░░░█      
        █░░░░░░░░░░░█░░░░░░░░░█     
       █░░░░░░░███░░░█░░░░░░░░░█    
       █░░░░███░░░███░█░░░████░█    
      █░░░██░░░░░░░░███░██░░░░██    
     █░░░░░░░░░░░░░░░░░█░░░░░░░░███ 
    █░░░░░░░░░░░░░██████░░░░░████░░█
    █░░░░░░░░░█████░░░████░░██░░██░░█
   ██░░░░░░░███░░░░░░░░░░█░░░░░░░░███
  █░░░░░░░░░░░░░░█████████░░░█████████
 █░░░░░░░░░░█████ ████   ████ █████   █
 █░░░░░░░░░░█     █ ███  █    ███ █   █
█░░░░░░░░░░░░█   ████ ████   ██ ██████
░░░░░░░░░░░░░█████████░░░████████░░░█
░░░░░░░░░░░░░░░░█░░░░░█░░░░░░░░░░░░█
░░░░░░░░░░░░░░░░░░░░██░░░░█░░░░░░██ 
░░░░░░░░░░░░░░░░░░██░░░░░░░███████  
░░░░░░░░░░░░░░░░██░░░░░░░░░░█░░░░░█ 
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█
░░░░░░░░░░░█████████░░░░░░░░░░░░░░██
░░░░░░░░░░█▒▒▒▒▒▒▒▒███████████████▒▒█
░░░░░░░░░█▒▒███████▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒█
░░░░░░░░░█▒▒▒▒▒▒▒▒▒█████████████████
░░░░░░░░░░████████▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒█
░░░░░░░░░░░░░░░░░░██████████████████
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█    
██░░░░░░░░░░░░░░░░░░░░░░░░░░░██     
▓██░░░░░░░░░░░░░░░░░░░░░░░░██       
▓▓▓███░░░░░░░░░░░░░░░░░░░░█         
▓▓▓▓▓▓███░░░░░░░░░░░░░░░██          
▓▓▓▓▓▓▓▓▓███████████████▓▓█         
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓██       
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓█       
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓█

The space wraps around, and order of clicks isn't important, only the position and number

max clicks to reach any possible state should be 3*N*N

total search space is 3^(N*N)... so every state is possible =)

3 1 2
2 1 3
1 2 3

1 1 1 / 2 0 1
0 0 1 / 2 1 2
0 0 1 / 1 2 2

1 0 0 / 1 0 1
1 0 0 / 1 1 2
1 1 1 / 0 1 1

0 0 1 / 1 0 0
1 1 1 / 0 0 1
0 0 1 / 0 1 0

probably just avoid zeros and backtrack?

4^(N*N), i forgot to count zeros =)

largest count on a single cell before modulo should be 3*(2N-1)

ooh, you can probably even separate row and column increments, as long as you have an equal number of each =D

And then subtract one for intercepts?