problema-cavalo-multithread

problema-cavalo-mt.cpp

//=============================================================================
// Resolve o problema do cavalo utilizando backtracking...
//
// Este código utiliza muitas referências e constantes de maneira
// a permitir que ele rode mais rápido possível...
//
// Versão melhorada (e mais complexa), utilizando multithreading,
// o código pode utilizar até 8 threads dependendo da posição inicial dada.
// Esse código utiliza o padrão C++11
//=============================================================================

#include <iostream>
#include <list>
#include <vector>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cctype>
#include <chrono>
#include <thread>
#include <atomic>
#include <cstring>
#include <mutex>

using namespace std;
using namespace chrono;

// Número de casas do tabuleiro
const int N = 10;
const int NxN = N * N;

//=============================================================================
// Como este código é multithreading, então é necessário que haja
// sincronização na hora da escrita, para ter acesso a saída
// padrão é necessário ter o lock do mutex... utilizando lock_guard
// para evitar leaks e deadlocks... o importante é saber utilizar
// com consciência :)
//=============================================================================
std::mutex& cout_mutex() {
    static std::mutex m;
    return m;
}

// Dado um escopo (!!!) adquiri o lock para imprimir, o lock
// será liberado quando o escopo deixar de existir
#define proteger_saida()    std::lock_guard<std::mutex> _(cout_mutex())

// Cria um escopo e adquiri o lock para imprimir, o lock
// é liberado imediatamente após realizar as operações definidas por x
#define saida_protegida(x) do { \
    std::lock_guard<std::mutex> _(cout_mutex());    \
    x;   \
    } while(0)

// Representa um movimento
struct movimento {
    int x, y;
    movimento(int _x=-1, int _y=-1) : x(_x), y(_y) {
    }

    // verifica se este é um movimento válido
    bool valido() {
        if ((x < 0 || x >= N) || (x < 0 || x >= N))
            return false;
        return true;
    }

    // verifica se dois movimentos são iguais
    bool operator==(const movimento &rhs) {
        return (x == rhs.x && y == rhs.y);
    }
};

// Define o tipo movimentos
typedef list<movimento> movimentos;

// Foward definition do tabuleiro...
class tabuleiro_xadrez;

// Nosso functor que compara dois possíveis movimentos
// e retorna qual deles está menos acessível
struct compara_menos_acessivel
{
    tabuleiro_xadrez &tabuleiro;
    compara_menos_acessivel(tabuleiro_xadrez &t) : tabuleiro(t) {
    }

    bool operator()(const movimento &r, const movimento &l);
};

class tabuleiro_xadrez
{
    bool m[N][N];
    int jogadas[N][N];
public:

    tabuleiro_xadrez() {
        limpar();
    }

    // nosso operador de cópia...
    void operator=(const tabuleiro_xadrez &l) {
        memcpy(m, l.m, sizeof(m));
        memcpy(jogadas, l.jogadas, sizeof(jogadas));
    }

    // limpa o tabuleiro
    void limpar() {
        for (int y = 0; y < N; y++) {
            for (int x = 0; x < N; x++) {
                m[y][x] = false;
                jogadas[y][x] = 0;
            }
        }
    }

    // marca a posição e o número da jogada
    void travar(const movimento &a, int pos) {
        const int &x = a.x;
        const int &y = a.y;
        if ((x >= 0 && x < N) && (y >= 0 && y < N)) {
            jogadas[y][x] = pos;
            m[y][x] = true;
        }
    }

    // exibe o tabuleiro com as jogadas
    void exibir() {
        // nosso lock vai ser automaticamente liberado quando sair
        // fora do escopo...
        proteger_saida();
        for (int y = 0; y < N; y++) {
            for (int x = 0; x < N; x++) {
                cout << setw(4) << jogadas[y][x];
            }
            cout << endl;
        }
        cout << endl;
    }

    // libera uma posição do tabuleiro
    void liberar(const movimento &a) {
        if ((a.x >= 0 && a.x < N) && (a.y >= 0 && a.y < N)) {
            m[a.y][a.x] = false;
            jogadas[a.y][a.x] = 0;
        }
    }


    // retorna a lista dos movimentos possíveis em uma posição
    // levando em consideração o estado atual do tabuleiro
    movimentos possiveis(const movimento &a, bool somente_livres=true) {

        const int &x = a.x;
        const int &y = a.y;

        const movimento deslocamentos[8] = {
            { 1, -2 }, { 1,  2 },
            {-1, -2 }, {-1,  2 },
            { 2, -1 }, { 2,  1 },
            {-2, -1 }, {-2,  1 },
        };
        movimentos lista;
        for (int i = 0; i < 8; i++) {
            int nx = x + deslocamentos[i].x;
            int ny = y + deslocamentos[i].y;

            // verifica se está dentro dos limites em X e Y
            if ((nx < 0) || (nx >= N))
                continue;
            if ((ny < 0) || (ny >= N))
                continue;

            // verifica se o lugar está livre
            if (m[ny][nx] && somente_livres)
                continue;
            lista.push_back(movimento(nx, ny));
        }

        return lista;
    }

    // Utilizando a regra de warnsdorff para chegar ao resultado
    // mais rapidamente.
    movimentos possiveis_ordenado(const movimento &a) {
        movimentos lista = possiveis(a);
        // ordena a lista por ordem de acessibilidade
        lista.sort(compara_menos_acessivel(*this));
        return lista;
    }
};

// Estrutua compartilhada entre os resolvedores
struct problema_cavalo {
    vector<std::thread> resolvedores;
    vector<tabuleiro_xadrez> tabuleiros;
    // lista de quantos resolvedores ainda estão trabalhando
    list<int> trabalhando;
    // verifica se já foi encontrada pelo menos uma solução
    atomic<bool> encontrou;
    // verifica se é necessário encontrar todas as soluções
    bool todas_solucoes;
};


// Move o cavalo para uma posição levando em consideração
// o estado atual, esta função é recursiva.
bool mover_cavalo_mt(problema_cavalo &problema,
                     const int resolvedor,
                     const movimento &partida,
                     const movimento &pos,
                     const int nivel,
                     bool fechada)
{

    tabuleiro_xadrez &tabuleiro = problema.tabuleiros[resolvedor];

    // Se já encontrou uma solução...
    if (problema.encontrou && !problema.todas_solucoes)
        return false;

    // Trava esta posição no tabuleiro...
    tabuleiro.travar(pos, nivel);

    // verifica se estamos no último movimento
    if (nivel == NxN) {

        // Verifica se é necessário uma solução fechada...
        if (fechada) {
            // vamos verificar se está nos leva a uma tour fechada...
            movimentos p = tabuleiro.possiveis(pos, false);

            // verifica se o ponto de partida faz parte das jogadas
            // possíveis na última posição
            if (find(p.begin(), p.end(), partida) != p.end()) {

                saida_protegida(cout << "Encontrou fechada no resolvedor " << resolvedor << endl);

                tabuleiro.exibir();
                problema.encontrou = true;
                problema.trabalhando.pop_front();
                return true;
            }

            // não é fechada, retorna...
            tabuleiro.liberar(pos);
            return false;
        }

        saida_protegida(cout << "Encontrou aberta no resolvedor " << resolvedor << endl);

        tabuleiro.exibir();
        problema.encontrou = true;
        problema.trabalhando.pop_front();
        return true;
    }

    // recebe a lista com as jogadas possíveis no estado atual
    movimentos p = tabuleiro.possiveis_ordenado(pos);

    // se a lista estiver vazia, então esse caminho está errado...
    if (!p.empty()) {

        // vamos verifica movimento por movimento para ver qual é nos
        // leva a uma tour...
        for (auto i = p.begin(); i != p.end(); i++) {
            if (mover_cavalo_mt(problema, resolvedor, partida, *i, nivel + 1, fechada))
                return true;
        }
    }

    // nenhum movimento neste nível foi válido...
    tabuleiro.liberar(pos);

    if (nivel == 2) {
        proteger_saida();
        if (problema.encontrou && !problema.todas_solucoes) {
            cout << "Terminando resolvedor " << resolvedor <<
                    ", a solução já foi encontrada em outro resolvedor" << endl;
        } else {
            cout << "Não existe solução no resolvedor " << resolvedor << endl;
        }
        problema.trabalhando.pop_front();
    }
    return false;
}


// Resolve uma tour para (x,y) utilizando backtracking com recursividade...
void resolver_mt(const int ix, const int iy,
                 const bool fechada=false,
                 const bool todas_solucoes=false)
{
    tabuleiro_xadrez tabuleiro;
    const movimento partida(ix, iy);
    problema_cavalo problema;

    problema.encontrou = false;
    problema.todas_solucoes = todas_solucoes;

    tabuleiro.travar(partida, 1);
    // para cada ramificação teremos uma thread
    movimentos ramos = tabuleiro.possiveis_ordenado(partida);

    const int max_threads = (int) ramos.size();

    problema.tabuleiros.resize(max_threads);
    problema.resolvedores.resize(max_threads);

    cout << "Ramos possíveis: " << max_threads << endl;

    auto tempo_inicio = chrono::high_resolution_clock::now();

    // Cria um resolvedor para cada ramificação possível....
    for (int i = 0; i < max_threads; i++) {
        movimento pos = ramos.front();

        // não queremos que nossos programas travem
        saida_protegida(cout << "Criando thread para (" << pos.x << ", " << pos.y <<
                                 ") : resolvedor " << i << endl);


        ramos.pop_front();
        // copia o tabuleiro atual para o do resolvedor
        problema.tabuleiros[i] = tabuleiro;
        // Para manter o controle das threads, temos uma lista informando
        // quantas delas ainda estão trabalhando...
        problema.trabalhando.push_back(1);
        problema.resolvedores[i] = std::thread(mover_cavalo_mt,
                                               std::ref(problema),
                                               i,
                                               std::cref(partida),
                                               pos, 2, fechada);
        // deixa a thread trabalhar livremente...
        problema.resolvedores[i].detach();
    }

    while (!problema.trabalhando.empty()) {
        // Não queremos que nossa thread fique em um loop com busy wait
        // estes ciclos serão melhores se alocados nos nossos resolvedores
        std::this_thread::sleep_for(microseconds(50));
    }

    auto tempo_delta = high_resolution_clock::now() - tempo_inicio;
    auto tempo_ms = duration_cast<milliseconds>(tempo_delta).count();

    // Já não temos nenhuma thread rodando paralelamente, então
    // podemos acessar cout sem problemas :)
    cout << "Tempo necessário: " << tempo_ms << "ms" << endl;

    cout << "Todas as rotas possíveis (dentro dos requisitos) foram calculadas!" << endl;
}


bool compara_menos_acessivel::operator()(const movimento &r, const movimento &l)
{
    movimentos a = tabuleiro.possiveis(r);
    movimentos b = tabuleiro.possiveis(l);
    return (a.size() < b.size());
}

int main()
{

    int x, y;
    char fechada, todas;

    cout << "Informe a posição: " << endl;
    cout << "Linha  (0-" << N-1 << "): ";
    cin >> y;
    cout << "Coluna (0-" << N-1 << "): ";
    cin >> x;
    cout << "Solução fechada? (s/n): ";
    cin >> fechada;

    cout << "Todas as soluções ramificadas? (s/n): ";
    cin >> todas;


    resolver_mt(x, y, tolower(fechada) == 's', tolower(todas) == 's');

    return 0;
}