#include<stdio.h> #include<string.h> #include<stdlib.h> #include<math.h> #include<iostream> #include<algorithm> using namespace std; const int MaxSize = 15; const int MaxProblem = 20; class Move { public: int nbLocations; int locations [MaxSize * MaxSize]; Move () { nbLocations = 0; } void add (int loc) { locations [nbLocations] = loc; nbLocations++; } void sort () { std::sort (locations, locations + nbLocations); } }; class Seen { public: char seen [MaxSize * MaxSize]; void init () { memset (seen, 0, MaxSize * MaxSize * sizeof (char)); } bool test (int loc) { return (seen [loc] == 0); } void set (int loc) { seen [loc] = 1; } }; static Move moves [MaxSize * MaxSize]; class Problem { public: int color [MaxSize * MaxSize]; int nbMoves; int score; int lengthVariation; Move variation [MaxSize * MaxSize]; void load (FILE *fp) { for (int i = 0; i < MaxSize; i++) for (int j = 0; j < MaxSize; j++) if (fscanf (fp, "%d", &color [MaxSize * i + j]) == -1) cerr << "Erreur de lecture des problemes" << endl; score = 0; lengthVariation = 0; } void buildMove (int loc, Seen & seen, Move & move) { int c = color [loc]; seen.set (loc); move.locations [0] = loc; move.nbLocations = 1; int stack [MaxSize * MaxSize]; stack [0] = 1; stack [1] = loc; while (stack [0] > 0) { int l = stack [stack [0]], neigh; stack [0]--; if (l >= MaxSize) { neigh = l - MaxSize; if (color [neigh] == c) if (seen.test (neigh)) { seen.set (neigh); move.add (neigh); stack [0]++; stack [stack [0]] = neigh; } } if (l < MaxSize * MaxSize - MaxSize) { neigh = l + MaxSize; if (color [neigh] == c) if (seen.test (neigh)) { seen.set (neigh); move.add (neigh); stack [0]++; stack [stack [0]] = neigh; } } if ((l % MaxSize) != 0) { neigh = l - 1; if (color [neigh] == c) if (seen.test (neigh)) { seen.set (neigh); move.add (neigh); stack [0]++; stack [stack [0]] = neigh; } } if ((l % MaxSize) != MaxSize - 1) { neigh = l + 1; if (color [neigh] == c) if (seen.test (neigh)) { seen.set (neigh); move.add (neigh); stack [0]++; stack [stack [0]] = neigh; } } } } bool moreThanOneMove (int c) { Seen seen; Move mv; int nb = 0; seen.init (); for (int i = 0; i < MaxSize * MaxSize; i++) if (color [i] == c) if (seen.test (i)) { buildMove (i, seen, mv); nb++; if (nb > 1) return true; } return false; } void findMoves (int tabu = 9) { Seen seen; nbMoves = 0; seen.init (); if (!moreThanOneMove (tabu)) tabu = 9; for (int i = 0; i < MaxSize * MaxSize; i++) if ((color [i] != 9) && (color [i] != tabu)) if (seen.test (i)) { buildMove (i, seen, moves [nbMoves]); if (moves [nbMoves].nbLocations > 1) nbMoves++; } if (nbMoves == 0) { for (int i = 0; i < MaxSize * MaxSize; i++) if (color [i] != 9) if (seen.test (i)) { buildMove (i, seen, moves [nbMoves]); if (moves [nbMoves].nbLocations > 1) nbMoves++; } } } void remove (int loc) { while (loc > MaxSize - 1) { color [loc] = color [loc - MaxSize]; loc = loc - MaxSize; } color [loc] = 9; } void removeColumn (int column) { for (int row = 0; row < MaxSize; row++) { for (int i = column; i < MaxSize - 1; i++) { color [row * MaxSize + i] = color [row * MaxSize + i + 1]; } color [row * MaxSize + MaxSize - 1] = 9; } } void playMove (Move & move) { // on doit trier pour enlever // les cases du haut en premier move.sort (); for (int i = 0; i < move.nbLocations; i++) { remove (move.locations [i]); } int column = 0; for (int i = 0; i < MaxSize; i++) { if (color [MaxSize * MaxSize - MaxSize + column] == 9) removeColumn (column); else column++; } score += (move.nbLocations - 2) * (move.nbLocations - 2); if (color [MaxSize * MaxSize - MaxSize] == 9) score += 1000; variation [lengthVariation] = move; lengthVariation++; } int bestColor () { int nbColors [10]; for (int i = 0; i < 10; i++) nbColors [i] = 0; for (int i = 0; i < MaxSize * MaxSize; i++) if (color [i] != 9) nbColors [color [i]]++; int best = 0, bestScore = 0; for (int i = 0; i < 10; i++) if (nbColors [i] > bestScore) { bestScore = nbColors [i]; best = i; } return best; } void playout () { int tabu = bestColor (); findMoves (tabu); while (nbMoves > 0) { int index = nbMoves * (rand () / (RAND_MAX + 1.0)); playMove (moves [index]); findMoves (tabu); } } }; Problem problem [MaxProblem]; void load (int nb, const char *name) { FILE * fp = fopen (name, "r"); if (fp != NULL) { for (int i = 0; i < nb; i++) problem [i].load (fp); fclose (fp); } else cerr << "pb ouverture " << name << "\n"; } int lengthBestRollout [10], scoreBestRollout [10]; Move bestRollout [10] [MaxSize * MaxSize]; Move nestedMoves [10] [MaxSize * MaxSize]; int nestedRollout (Problem & pb, int n) { int bestScore, scoreRollout, bestEvaluation; Move bestMove; int tabu = pb.bestColor (); pb.findMoves (tabu); for (int i = 0; i < pb.nbMoves; i++) nestedMoves [n] [i] = moves [i]; lengthBestRollout [n] = 0; scoreBestRollout [n] = 0; while (true) { if (pb.nbMoves == 0) break; bestScore = scoreBestRollout [n]; bestMove = bestRollout [n] [pb.lengthVariation]; for (int i = 0; i < pb.nbMoves; i++) { if (n == 1) { Problem p = pb; p.playMove (nestedMoves [n] [i]); p.playout (); scoreRollout = p.score; if (scoreRollout > bestScore) { bestScore = scoreRollout; bestMove = nestedMoves [n] [i]; scoreBestRollout [n] = bestScore; lengthBestRollout [n] = p.lengthVariation; for (int i = 0; i < p.lengthVariation; i++) bestRollout [n] [i] = p.variation [i]; } } else { Problem p = pb; p.playMove (nestedMoves [n] [i]); scoreRollout = nestedRollout (p, n - 1); if (scoreRollout > bestScore) { bestScore = scoreRollout; bestMove = nestedMoves [n] [i]; scoreBestRollout [n] = bestScore; lengthBestRollout [n] = p.lengthVariation; for (int i = 0; i < p.lengthVariation; i++) bestRollout [n] [i] = p.variation [i]; if (n > 0) { for (int t = 0; t < n - 1; t++) cout << "\t"; cout << "n = " << n << ", progres = " << pb.lengthVariation << ", length = " << lengthBestRollout [n] << ", score = " << scoreBestRollout [n] << ", nbMoves = " << pb.nbMoves << "\n"; } } } } pb.playMove (bestMove); pb.findMoves (tabu); for (int i = 0; i < pb.nbMoves; i++) nestedMoves [n] [i] = moves [i]; } return pb.score; } int main (int argc, char ** argv) { load (20, "problems.txt"); for (int pb = 0; pb < 20; pb++) { Problem p = problem [pb]; nestedRollout (p, 2); cout << endl; if (p.color [MaxSize * MaxSize - MaxSize] == 9) cout << "cleared!\n"; cout << "score (" << pb << ") = " << p.score << "\n\n"; } }