kami-solver

Solution finder for KAMI 2 game on IOS (or KAMI on Android). Uses DFS (naive) or A* search (much much faster) to reach a solution.

The puzzle is entered as separate regions, each with a unique id and information on color and adjacent regions.

For example, the puzzle below is divided into separate regions identified by letters:

The above puzzle is represented as follows:

colors = ["ORANGE", "BLUE", "CREAM"]
# Region (id, color_index, adjacent_region_ids)
A = Region("A", 2, {'B', 'D', 'E'})
B = Region("B", 0, {'A', 'D', 'C'})
C = Region("C", 2, {'B', 'D', 'E'})
D = Region("D", 1, {'A', 'B', 'C', 'E'})
E = Region("E", 0, {'D', 'A', 'C'})

The solution is computed as follows:

kami = Kami([A, B, C, D, E], colors)
kami.solve(2) # Solve within a maximum of 2 moves

Solution found:
        Begin
        Move 2: set D to ORANGE
        Move 1: set B+E+D to CREAM
Finished in 0.01346732 seconds

There is also a solve_i() method which attempts the puzzle without any knowledge of the optimal number of moves. It uses iterative deepening while calling the above solve(n) method:

kami = Kami([A, B, C, D, E], colors)
kami.solve_i() # Finds solution and minimal number of moves required

Following is an example involving more regions. As the number of steps increase, the solver could run for a few seconds due to the size of the puzzle:

# See source for complete puzzle representation
kami = Kami([A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X], colors)
kami.solve(5)

Solution found!
        Begin
        Move 5: set R to CREAM
        Move 4: set Q+S+R+L to RED
        Move 3: set P+K+Q+S+R+L to BLACK
        Move 2: set C+E+I+M+P+K+Q+S+R+L+U+T to CREAM
        Move 1: set B+D+F+H+J+O+N+C+E+I+M+P+K+Q+S+R+L+U+T+W+V to BLACK
Finished in 0.36057810783 seconds