lgoritmo de retrocesso do Sudoku
Em primeiro lugar, afirmo que essa é uma tarefa da universidade, então não peço que alguém escreva o código para mim, só preciso ser apontado na direção certa. :)
Ok, então eu preciso escrever um algoritmo para resolver qualquer placa sudoku (solucionável) de tamanho arbitrário. Eu escrevi uma função recursiva que pode resolver qualquer placa 9x9 rapidamente (~ 1ms), mas quando eu faço placas maiores (16x16) difíceis de resolver, ela se esforça. Eu fiz um teste por 20 minutos e ele pode ' parece não resolver isso. Ele pode resolver quebra-cabeças simples de 16x16 ou até um quadro de 16x16 em branco, então não acho que sejam as dimensões que são o problema. É mais provável que seja o algoritmo que é o problema que eu ach
e qualquer forma, esta é a lógica básica do meu program
Eu tenho um vetor 3D que armazena os valores possíveis de todos os meus quadradosQuando um valor é colocado em um quadrado, ele é removido dos possíveis valores do quadrado, linha e coluna circundantes em que estáEntão minha função de resolução é basicamente:
bool solve() {
if (there are no unfilled squares)
return true
if (the board is unsolvable - there are empty squares that have no possible values)
return false
while (there are empty squares)
{
int squaresFilled = fillSquaresWithOnlyOneChoice(); //this method updates the possible results vector whenever it fills a square
if (squaresFilled == 0)
break;
}
//exhausted all of the 'easy' squares (squares with only one possible choice), need to make a guess
while (there ar,e empty squares that have choices left) {
find the square with the least number of choices
if (the square with the least number of choices has 0 choices)
return false; //not solvable.
remove that choice from the 3D vector (vector that has the choices for each square)
make a copy of the board and the 3D choices vector
fill the square with the choice
if (solve())
return true; //we're done
restore the board and choices vector
//the guess didn't work so keep looping and make a new guess with the restored board and choices -- the choice we just made has been removed though so it won't get made again.
}
return false; //can't go any further
}
Existe algo ineficiente sobre isso? Existe alguma maneira de fazê-lo funcionar melhor? Suponho que um quadro de 16x16 leva tanto tempo é porque a árvore de decisão é muito grande para um quadro que não é muito preenchido. É estranho, porque uma placa 9x9 resolverá muito rápido.
Todas as idéias ou sugestões seriam absolutamente incríveis. Se houver alguma informação que eu tenha perdido, avise-me também!