Uma das sugestões dadas no enunciado que eu estou tentando implementar é definir uma ordem em que se vai tentar preencher as casas durante o backtracking... estou em duvida entre 2 regras de ordenação:
1 - Preencher primeiro a área(linha, coluna ou regiao) em que tem menos casas em branco.
2 - Preencher primeiro a casa que tenha menos possibilidades que precisem ser testadas, independente em que linha, coluna ou região elas estejam.
Se o objetivo é diminuir a "largura" da arvore de possibilidades no começo, a segunda me parece mais indicada. Por outro lado, testando áreas inteiras de uma vez, me parece mais provável que eu chegue mais rápido à uma folha, então a primeira pode ser melhor...
Sugestões?
Em resposta à Gabriel R. C. Peixoto
Re: Melhor ordem para fazer o backtracking
por Marco Dimas Gubitoso -
Fiz alguns testes com heurísticas diferentes, seja por número de possibilidades de cada casa, seja por número de casas livres em linhas, colunas, etc , ou por uma combinação de fatores, o que percebi é que não existe uma heurística claramente melhor. Alguns problemas se beneficiam bastante de uma heurística, mas a mesma heurística não dá bons resultados em outros casos.
Para efeitos de conseguir o bônus do EP, escolha uma heurística que apresente resultados bons para alguns casos.
Gubi
Para efeitos de conseguir o bônus do EP, escolha uma heurística que apresente resultados bons para alguns casos.
Gubi
Em resposta à Marco Dimas Gubitoso
Re: Melhor ordem para fazer o backtracking
por Gabriel R. C. Peixoto -
Beleza, obrigado!