Problème classique de recherche combinatoire avec test de primalité.

#include <iostream>
using namespace std;

int countPrimes(int val) {
   if (val < 2) return 0;
   for (int d = 2; d * d <= val; ++d) {
       if (val % d == 0) return 0;
   }
   return 1;
}

int totalComb = 0;
void generateCombinations(int step, int lastIndex, int currentSum, int *data, int maxSteps, int size) {
   if (step + (size - lastIndex) < maxSteps) return;
   if (step == maxSteps + 1) {
       totalComb += countPrimes(currentSum);
       return;
   }
   for (int idx = lastIndex + 1; idx <= size; ++idx) {
       generateCombinations(step + 1, idx, currentSum + data[idx], data, maxSteps, size);
   }
}

int main() {
   int n, k;
   cin >> n >> k;
   int numbers[26];
   for (int i = 1; i <= n; ++i) cin >> numbers[i];
   generateCombinations(1, 0, 0, numbers, k, n);
   cout << totalComb << endl;
   return 0;
}
   

Optimisation du parcours de fromages

Problème de voyageur du commerce avec élagage d'optimalité.

#include <iostream>
#include <cmath>
using namespace std;

double points[16][2];
double distances[16][16];
double minimalDist = 1e9;
bool visited[16];
int nodeCount, maxIter = 10000000;

void explorePath(int depth, int currentNode, double accumulatedDist) {
   if (--maxIter < 0) {
       printf("%.2lf\n", minimalDist);
       exit(0);
   }
   if (depth > nodeCount) {
       if (accumulatedDist < minimalDist) minimalDist = accumulatedDist;
       return;
   }
   for (int next = 1; next <= nodeCount; ++next) {
       if (!visited[next]) {
           double newDist = accumulatedDist + distances[currentNode][next];
           if (newDist >= minimalDist) continue;
           visited[next] = true;
           explorePath(depth + 1, next, newDist);
           visited[next] = false;
       }
   }
}

int main() {
   cin >> nodeCount;
   for (int i = 1; i <= nodeCount; ++i) {
       cin >> points[i][0] >> points[i][1];
   }
   for (int i = 0; i <= nodeCount; ++i) {
       for (int j = 0; j <= nodeCount; ++j) {
           distances[i][j] = hypot(points[i][0] - points[j][0], points[i][1] - points[j][1]);
       }
   }
   explorePath(1, 0, 0.0);
   printf("%.2lf\n", minimalDist);
   return 0;
}
   

Reconstruction de bâtonnets

Problème de correspondance avec élagage de symétrie et de branches.

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int stickCount, targetLength, pieceCount;
int lengths[71];
bool used[71];

void assembleSticks(int group, int currentLen, int startIndex) {
   if (group > pieceCount) {
       cout << targetLength << endl;
       exit(0);
   }
   if (currentLen == targetLength) {
       assembleSticks(group + 1, 0, 1);
       return;
   }
   int lastSkipped = -1;
   for (int i = startIndex; i <= stickCount; ++i) {
       if (!used[i] && currentLen + lengths[i] <= targetLength && lengths[i] != lastSkipped) {
           used[i] = true;
           assembleSticks(group, currentLen + lengths[i], i + 1);
           used[i] = false;
           lastSkipped = lengths[i];
           if (currentLen == 0 || currentLen + lengths[i] == targetLength) return;
       }
   }
}

int main() {
   cin >> stickCount;
   int totalLength = 0, maxPiece = 0;
   for (int i = 1; i <= stickCount; ++i) {
       cin >> lengths[i];
       totalLength += lengths[i];
       maxPiece = max(maxPiece, lengths[i]);
   }
   sort(lengths + 1, lengths + stickCount + 1, greater<int>());
   for (int len = maxPiece; len <= totalLength; ++len) {
       if (totalLength % len == 0) {
           targetLength = len;
           pieceCount = totalLength / len;
           memset(used, 0, sizeof(used));
           assembleSticks(1, 0, 1);
       }
   }
   return 0;
}
   

Fractions égyptiennes

Recherche en profondeur limitée pour la décomposition en fractions unitaires.

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;
int maxDepth, found;
ll sequence[11], bestSequence[11];

ll gcd(ll a, ll b) {
   return b ? gcd(b, a % b) : a;
}

void findDecomposition(int depth, ll numerator, ll denominator) {
   if (depth > maxDepth) return;
   if (numerator == 1 && denominator > sequence[depth - 1]) {
       sequence[depth] = denominator;
       if (!found || sequence[depth] < bestSequence[depth]) {
           for (int i = 1; i <= depth; ++i) bestSequence[i] = sequence[i];
       }
       found = 1;
       return;
   }
   ll lower = max(denominator / numerator, sequence[depth - 1] + 1);
   ll upper = (maxDepth - depth + 1) * denominator / numerator;
   if (found && upper >= bestSequence[maxDepth]) upper = bestSequence[maxDepth] - 1;
   for (ll divisor = lower; divisor < upper; ++divisor) {
       sequence[depth] = divisor;
       ll newNum = numerator * divisor - denominator;
       ll newDen = denominator * divisor;
       ll common = gcd(newNum, newDen);
       findDecomposition(depth + 1, newNum / common, newDen / common);
   }
}

int main() {
   ll a, b;
   cin >> a >> b;
   ll common = gcd(a, b);
   a /= common;
   b /= common;
   sequence[0] = 1;
   for (maxDepth = 1; maxDepth <= 10; ++maxDepth) {
       findDecomposition(1, a, b);
       if (found) {
           for (int i = 1; i <= maxDepth; ++i) cout << bestSequence[i] << " ";
           break;
       }
   }
   return 0;
}
   

Combinaisons de cubes

Approche diviser pour régner avec mappage de sous-ensembles.

#include <iostream>
#include <map>
using namespace std;

typedef long long ll;
const int MAXN = 105;
int numbers[MAXN], decisions[MAXN];
int halfSize, cubeLimit;
ll targetSum;

map<pair<int, ll>, int> countMap;
map<pair<int, ll>, ll> queryCache;

ll computeFactorial(ll x) {
   ll result = 1;
   for (ll i = x; i >= 1; --i) {
       if (targetSum / result < i) return -1;
       result *= i;
   }
   return result;
}

void processSubset(int start, int end) {
   int cubesUsed = 0;
   ll currentSum = 0;
   for (int i = start; i <= end; ++i) {
       if (decisions[i] == 1) {
           currentSum += numbers[i];
       } else if (decisions[i] == 2) {
           ll fact = computeFactorial(numbers[i]);
           if (fact == -1 || (++cubesUsed > cubeLimit) || fact + currentSum > targetSum) return;
           currentSum += fact;
       }
   }
   countMap[{cubesUsed, currentSum}]++;
   countMap[{-1, currentSum}]++;
}

void enumerateFirstHalf(int pos) {
   if (pos > halfSize) {
       processSubset(1, halfSize);
   } else {
       for (int choice = 0; choice < 3; ++choice) {
           decisions[pos] = choice;
           enumerateFirstHalf(pos + 1);
       }
   }
}

ll queryPrefix(int maxCubes, ll sum) {
   auto key = make_pair(maxCubes, sum);
   if (queryCache.find(key) != queryCache.end()) return queryCache[key];
   return queryCache[key] = countMap[key] + (maxCubes ? queryPrefix(maxCubes - 1, sum) : 0);
}

ll totalWays = 0;
void enumerateSecondHalf(int pos) {
   if (pos > halfSize + (halfSize)) {
       int cubesUsed = 0;
       ll currentSum = 0;
       for (int i = halfSize + 1; i <= halfSize + halfSize; ++i) {
           if (decisions[i] == 1) {
               currentSum += numbers[i];
           } else if (decisions[i] == 2) {
               ll fact = computeFactorial(numbers[i]);
               if (fact == -1 || (++cubesUsed > cubeLimit) || fact + currentSum > targetSum) return;
               currentSum += fact;
           }
       }
       if (countMap.count({-1, targetSum - currentSum})) {
           totalWays += queryPrefix(cubeLimit - cubesUsed, targetSum - currentSum);
       }
   } else {
       for (int choice = 0; choice < 3; ++choice) {
           decisions[pos] = choice;
           enumerateSecondHalf(pos + 1);
       }
   }
}

int main() {
   int n;
   cin >> n >> cubeLimit >> targetSum;
   for (int i = 1; i <= n; ++i) cin >> numbers[i];
   halfSize = n / 2;
   enumerateFirstHalf(1);
   enumerateSecondHalf(halfSize + 1);
   cout << totalWays << endl;
   return 0;
}
   

Puzzle à 8 cases

Recherche en largeur d'abord pour le problème de glissement de tuiles.

#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;

const int TARGET = 123804765;
unordered_map<int, int> visited;

int solveBFS(int startState) {
   queue<int> q;
   q.push(startState);
   visited[startState] = 1;
   const int dx[4] = {-1, 0, 1, 0};
   const int dy[4] = {0, 1, 0, -1};

   while (!q.empty()) {
       int state = q.front();
       q.pop();
       if (state == TARGET) return visited[state] - 1;

       int grid[3][3], blankX, blankY;
       int temp = state;
       for (int i = 0; i < 3; ++i) {
           for (int j = 0; j < 3; ++j) {
               grid[i][j] = temp % 10;
               temp /= 10;
               if (grid[i][j] == 0) blankX = i, blankY = j;
           }
       }

       for (int dir = 0; dir < 4; ++dir) {
           int newX = blankX + dx[dir];
           int newY = blankY + dy[dir];
           if (newX >= 0 && newX < 3 && newY >= 0 && newY < 3) {
               swap(grid[blankX][blankY], grid[newX][newY]);
               int newState = 0;
               for (int i = 2; i >= 0; --i) {
                   for (int j = 2; j >= 0; --j) {
                       newState = newState * 10 + grid[i][j];
                   }
               }
               if (visited.find(newState) == visited.end()) {
                   visited[newState] = visited[state] + 1;
                   q.push(newState);
               }
               swap(grid[blankX][blankY], grid[newX][newY]);
           }
       }
   }
   return -1;
}

int main() {
   int start;
   cin >> start;
   cout << solveBFS(start) << endl;
   return 0;
}
   

État du mécanisme

Recherche A* avec heuristique pour un problème d'états discrets.

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int STATE_SPACE = 1 << 24;
int transitionCost[STATE_SPACE];
int nextState[12][4];
int parentState[STATE_SPACE];
int moveHistory[20];

struct SearchNode {
   int state;
   double priority;
   SearchNode(int s) : state(s) {
       double heuristic = 0;
       priority = 0;
       for (int i = 0; i < 12; ++i) {
           int knobPos = (s >> (i * 2)) & 3;
           if (knobPos) heuristic += 4 - knobPos;
       }
       priority = heuristic + transitionCost[s];
   }
   bool operator<(const SearchNode& other) const {
       return priority > other.priority;
   }
};

priority_queue<SearchNode> pq;

int main() {
   int initialButton, initialState = 0;
   for (int i = 0; i < 12; ++i) {
       cin >> initialButton;
       initialState |= (initialButton - 1) << (i * 2);
       for (int j = 0; j < 4; ++j) {
           cin >> nextState[i][j];
           nextState[i][j]--;
       }
   }
   pq.push(SearchNode(initialState));
   transitionCost[initialState] = 0;
   memset(parentState, -1, sizeof(parentState));

   while (!pq.empty()) {
       int current = pq.top().state;
       pq.pop();
       if (current == 0) break;

       for (int knob = 0; knob < 12; ++knob) {
           int currentPos = (current >> (knob * 2)) & 3;
           int affected = nextState[knob][currentPos];
           int affectedPos = (current >> (affected * 2)) & 3;

           int newState = current ^ (currentPos << (knob * 2)) ^ (((currentPos + 1) & 3) << (knob * 2));
           newState = newState ^ (affectedPos << (affected * 2)) ^ (((affectedPos + 1) & 3) << (affected * 2));

           if (transitionCost[newState] == 0 && newState != initialState) {
               transitionCost[newState] = transitionCost[current] + 1;
               parentState[newState] = current;
               moveHistory[newState] = knob + 1;
               pq.push(SearchNode(newState));
           }
       }
   }

   int stepCount = 0;
   int traceState = 0;
   while (traceState != initialState) {
       moveHistory[++stepCount] = moveHistory[traceState];
       traceState = parentState[traceState];
   }
   cout << stepCount << endl;
   for (int i = stepCount; i >= 1; --i) cout << moveHistory[i] << " ";
   return 0;
}
   

Cavalier sur l'échiquier

Rceherche itérative en profondeur avec heuristique pour les mouvemants du cavalier.

#include <iostream>
using namespace std;

int board[7][7];
int startX, startY, foundSolution;
const int dx[9] = {0, 1, 1, -1, -1, 2, 2, -2, -2};
const int dy[9] = {0, 2, -2, 2, -2, 1, -1, 1, -1};
const int targetBoard[7][7] = {
   {0,0,0,0,0,0,0},
   {0,1,1,1,1,1,1},
   {0,0,1,1,1,1,1},
   {0,0,0,2,1,1,1},
   {0,0,0,0,0,1,1},
   {0,0,0,0,0,0,1},
   {0,0,0,0,0,0,0}
};

int evaluateMismatch() {
   int mismatches = 0;
   for (int i = 1; i <= 5; ++i) {
       for (int j = 1; j <= 5; ++j) {
           if (board[i][j] != targetBoard[i][j]) mismatches++;
       }
   }
   return mismatches;
}

bool inBounds(int x, int y) {
   return x >= 1 && x <= 5 && y >= 1 && y <= 5;
}

void depthLimitedSearch(int depth, int x, int y, int maxDepth) {
   if (depth == maxDepth) {
       if (evaluateMismatch() == 0) foundSolution = 1;
       return;
   }
   for (int move = 1; move <= 8; ++move) {
       int newX = x + dx[move];
       int newY = y + dy[move];
       if (!inBounds(newX, newY)) continue;
       swap(board[x][y], board[newX][newY]);
       int mismatches = evaluateMismatch();
       if (mismatches + depth <= maxDepth) {
           depthLimitedSearch(depth + 1, newX, newY, maxDepth);
       }
       swap(board[x][y], board[newX][newY]);
   }
}

int main() {
   int testCases;
   cin >> testCases;
   while (testCases--) {
       foundSolution = 0;
       char cell;
       for (int i = 1; i <= 5; ++i) {
           for (int j = 1; j <= 5; ++j) {
               cin >> cell;
               if (cell == '*') {
                   board[i][j] = 2;
                   startX = i;
                   startY = j;
               } else {
                   board[i][j] = cell - '0';
               }
           }
       }
       if (evaluateMismatch() == 0) {
           printf("0\n");
           continue;
       }
       for (int depthLimit = 1; depthLimit <= 15; ++depthLimit) {
           depthLimitedSearch(0, startX, startY, depthLimit);
           if (foundSolution) {
               printf("%d\n", depthLimit);
               break;
           }
       }
       if (!foundSolution) printf("-1\n");
   }
   return 0;
}
   

Sudoku en forme de cible

Recherche en profondeur avec optimisation d'ordre et de contraintes pour Sudoku avancé.

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 10;
int grid[N][N];
bool usedInRow[N][N], usedInCol[N][N], usedInBox[4][4][N];
int scoreGrid[N][N] = {
   {0,0,0,0,0,0,0,0,0,0},
   {0,6,6,6,6,6,6,6,6,6},
   {0,6,7,7,7,7,7,7,7,6},
   {0,6,7,8,8,8,8,8,7,6},
   {0,6,7,8,9,9,9,8,7,6},
   {0,6,7,8,9,10,9,8,7,6},
   {0,6,7,8,9,9,9,8,7,6},
   {0,6,7,8,8,8,8,8,7,6},
   {0,6,7,7,7,7,7,7,7,6},
   {0,6,6,6,6,6,6,6,6,6}
};

struct Cell {
   int x, y;
} cells[100];
int emptyInRow[N], emptyInCol[N], cellCount;
int maxScore = -1;

bool compareCells(Cell a, Cell b) {
   if (emptyInRow[a.x] == emptyInRow[b.x]) return emptyInCol[a.y] < emptyInCol[b.y];
   return emptyInRow[a.x] < emptyInRow[b.x];
}

bool canPlace(int i, int j, int num) {
   int boxI = (i - 1) / 3 + 1, boxJ = (j - 1) / 3 + 1;
   return !usedInRow[i][num] && !usedInCol[j][num] && !usedInBox[boxI][boxJ][num];
}

void search(int pos, int currentScore) {
   if (pos == 82) {
       maxScore = max(maxScore, currentScore);
       return;
   }
   int i = cells[pos].x, j = cells[pos].y;
   int boxI = (i - 1) / 3 + 1, boxJ = (j - 1) / 3 + 1;

   if (grid[i][j]) {
       search(pos + 1, currentScore + grid[i][j] * scoreGrid[i][j]);
   } else {
       for (int num = 1; num <= 9; ++num) {
           if (canPlace(i, j, num)) {
               usedInRow[i][num] = true;
               usedInCol[j][num] = true;
               usedInBox[boxI][boxJ][num] = true;
               search(pos + 1, currentScore + num * scoreGrid[i][j]);
               usedInRow[i][num] = false;
               usedInCol[j][num] = false;
               usedInBox[boxI][boxJ][num] = false;
           }
       }
   }
}

int main() {
   for (int i = 1; i <= 9; ++i) {
       for (int j = 1; j <= 9; ++j) {
           cin >> grid[i][j];
           int boxI = (i - 1) / 3 + 1, boxJ = (j - 1) / 3 + 1;
           cells[(i - 1) * 9 + j] = {i, j};
           if (grid[i][j] == 0) {
               emptyInRow[i]++;
               emptyInCol[j]++;
           } else {
               usedInRow[i][grid[i][j]] = true;
               usedInCol[j][grid[i][j]] = true;
               usedInBox[boxI][boxJ][grid[i][j]] = true;
           }
       }
   }
   sort(cells + 1, cells + 82, compareCells);
   search(1, 0);
   cout << maxScore << endl;
   return 0;
}