fork download
copy 
  1. #include <iostream>
  2. #include <fstream>
  3. #include <chrono>
  4. #include <vector>
  5.  
  6. using namespace std;
  7. using namespace std::chrono;
  8.  
  9. // Defina os valores de N e M aqui
  10. const int N = 8; // Número de linhas
  11. const int M = 8; // Número de colunas
  12.  
  13. vector<vector<int>> sol(N, vector<int>(M, -1));
  14. int tentativas = 0; // Contador de tentativas
  15.  
  16. // Movimentos possíveis do cavalo
  17. int moveX[8] = {2, 1, -1, -2, -2, -1, 1, 2};
  18. int moveY[8] = {1, 2, 2, 1, -1, -2, -2, -1};
  19.  
  20. // Verifica se a posição (x, y) é válida
  21. bool isSafe(int x, int y) {
  22.     return (x >= 0 && x < N && y >= 0 && y < M && sol[x][y] == -1);
  23. }
  24.  
  25. // Função recursiva de Backtracking
  26. bool solveKnightTour(int x, int y, int movei) {
  27.     tentativas++;
  28.     if (movei == N * M) return true;
  29.  
  30.     for (int k = 0; k < 8; k++) {
  31.         int nextX = x + moveX[k];
  32.         int nextY = y + moveY[k];
  33.         if (isSafe(nextX, nextY)) {
  34.             sol[nextX][nextY] = movei;
  35.             if (solveKnightTour(nextX, nextY, movei + 1))
  36.                 return true;
  37.             else
  38.                 sol[nextX][nextY] = -1; // Backtracking
  39.         }
  40.     }
  41.     return false;
  42. }
  43.  
  44. // Função principal para resolver o problema do Passeio do Cavalo
  45. void knightTour(int startX, int startY) {
  46.     // Inicializa o tabuleiro com -1
  47.     for (int x = 0; x < N; x++)
  48.         for (int y = 0; y < M; y++)
  49.             sol[x][y] = -1;
  50.  
  51.     // O cavalo inicia na posição definida por startX e startY
  52.     sol[startX][startY] = 0;
  53.     tentativas = 0;
  54.  
  55.     auto start = high_resolution_clock::now(); // Tempo inicial
  56.  
  57.     if (solveKnightTour(startX, startY, 1)) {
  58.         auto stop = high_resolution_clock::now(); // Tempo final
  59.         auto duration = duration_cast<milliseconds>(stop - start).count();
  60.  
  61.         // Abrindo ou criando o arquivo para salvar os resultados
  62.         fstream file;
  63.         file.open("cavalo_blak.txt", ios::in | ios::out | ios::app);
  64.  
  65.         // Verifica quantas execuções já existem no arquivo
  66.         int execCount = 1;
  67.         string line;
  68.         while (getline(file, line)) {
  69.             if (line.find("****************************") != string::npos) {
  70.                 execCount++;
  71.             }
  72.         }
  73.  
  74.         // Salvando os resultados
  75.         file.clear();
  76.         file << "\n**************************** Execução " << execCount << " ****************************\n";
  77.         file << "Tamanho do tabuleiro: " << N << "x" << M << "\n";
  78.         file << "Posição inicial: (" << startX << ", " << startY << ")\n";
  79.         file << "Tempo de execução: " << duration << " ms\n";
  80.         file << "Número de tentativas: " << tentativas << "\n";
  81.         file << "Solução:\n";
  82.         for (int x = 0; x < N; x++) {
  83.             for (int y = 0; y < M; y++) {
  84.                 file << sol[x][y] << " ";
  85.             }
  86.             file << "\n";
  87.         }
  88.         file.close();
  89.         cout << "Resultado salvo no arquivo 'cavalo_blak.txt' com sucesso!\n";
  90.     } else {
  91.         cout << "Não existe solução para esse passeio do cavalo.\n";
  92.     }
  93. }
  94.  
  95. int main() {
  96.     // Defina as coordenadas de início do cavalo
  97.     int startX = 0; // Coordenada X inicial
  98.     int startY = 0; // Coordenada Y inicial
  99.  
  100.     knightTour(startX, startY);
  101.     return 0;
  102. }
  103.  
Success #stdin #stdout 0.17s 5272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Resultado salvo no arquivo 'cavalo_blak.txt' com sucesso!
https://ideone.com/Comw8n
language:
C++14 (gcc 8.3)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!