本帖最後由 KoolFreeze 於 2013-11-26 01:05 編輯
開個array
做CHECKING
IF right pattern -> true
DONE

唔洗太複雜
Jimmy0911 發表於 2013-11-24 21:20


How do you check all the configurations of various moves?
Do you know that there are an exponential number of states?
How can you make sure your program run fast enough?

Chess without AI is merely hard-coding.
This problem is more challenging.

TOP

本帖最後由 KoolFreeze 於 2013-11-26 01:43 編輯

Here is the pseudocode of the basic algorithm

IDAStar(State s, int limit) {
    mark state s as visited
    if s is ending state {
        print the path by tracing the predecessor of s
    } else {
       for all neighbour state s' {
           if s' is not visited && limit >= cost of s' + h(s') {
               mark s' as visited
               record s as the predecessor of s'
               IDAStar(s', limit)
           }
       }
   }
}

where h(s') is an admissible heuristic function, for example, sum of manhattan distances of each tiles.

TOP

回復 28# 神秘二代

My mistake... No need to update the limit.
Just keep calling IDAStar with an increasing limit until a solution can be found.

TOP

also, this algorithm not consider more than 1 slot and duplicate number
神秘二代 發表於 2013-11-26 01:22


It just depends on how you enumerate neighbour states.

TOP

回復 31# 神秘二代

A simple solution is to find all spaces and swap each with any adjacent tile.

For heuristic function, you don't need to insist on matching each tile of the same digit to a different location. Otherwise, it becomes a Maximum Weight Matching problem, which can be quite complicated. You can simply use the shortest manhattan distance to that digit at the target state. It is still an admissible heuristic.

TOP

本帖最後由 KoolFreeze 於 2013-11-27 16:32 編輯

I've written an example program. It can handle arbitrary number of slots and duplicate numbers. I only focus on simplicity rather than speed, so there are still many rooms for optimization.
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>

  4. using namespace std;

  5. typedef vector< vector<int> > State;

  6. map<State, bool> visited;
  7. vector<State> path;
  8. State start, target;
  9. int N;

  10. void input(State &s) {
  11.   s = State(N, vector<int>(N));
  12.   for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) cin >> s[i][j];
  13. }

  14. inline int h(const State &s, const State &t) {
  15.   int a, b, c, d, tot = 0;
  16.   for (a = 0; a < N; ++a) for (b = 0; b < N; ++b) if (s[a][b] != 0) {
  17.     int best = N + N;
  18.     for (c = 0; c < N; ++c) for (d = 0; d < N; ++d) if (t[c][d] == s[a][b]) {
  19.       if (best > abs(a - c) + abs(b - d)) best = abs(a - c) + abs(b - d);
  20.     }
  21.     tot += best;
  22.   }
  23.   return tot;
  24. }

  25. bool IDAStar(const State &s, int cost, int limit) {
  26.   visited[s] = true;
  27.   path.push_back(s);
  28.   if (s == target) {
  29.     for (int x = 0; x <= cost; ++x) {
  30.       cout << "== Step " << x << " ==" << endl;
  31.       for (int i = 0; i < N; ++i) {
  32.         for (int j = 0; j < N; ++j) cout << path[x][i][j] << ' ';
  33.         cout << endl;
  34.       }
  35.     }
  36.   } else if (cost + h(s, target) <= limit) {
  37.     for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) if (s[i][j] == 0) {
  38.       for (int d = 0; d < 4; ++d) {
  39.         int ni = i + ((d + 1) % 2) * (d - 1), nj = j + (d % 2) * (d - 2);
  40.         if (ni >= 0 && ni < N && nj >= 0 && nj < N && s[ni][nj] != 0) {
  41.           State ns(s);
  42.           swap(ns[i][j], ns[ni][nj]);
  43.           if (!visited[ns] && IDAStar(ns, cost + 1, limit)) return true;
  44.         }
  45.       }
  46.     }
  47.   }
  48.   path.pop_back();
  49.   return s == target;
  50. }

  51. int main() {
  52.   cout << "N? ";
  53.   cin >> N;
  54.   cout << "Starting state?" << endl;
  55.   input(start);
  56.   cout << "Target state?" << endl;
  57.   input(target);
  58.   for (int limit = 0; !IDAStar(start, 0, limit); ++limit) {
  59.     visited.clear();
  60.     cout << "Searching with limit " << limit << "..." << endl;
  61.   }
  62.   return 0;
  63. }
複製代碼
Example input
  1. N? 4
  2. Starting state?
  3. 1 2 0 3
  4. 3 0 4 0
  5. 4 4 6 0
  6. 1 4 5 6
  7. Ending state?
  8. 4 0 0 2
  9. 3 0 1 0
  10. 4 4 6 6
  11. 1 4 5 3
複製代碼

TOP