Quem joga xadrez conhece a forma do movimento do cavalo. Ele faz uma espécis de L.

Neste problema, todas as casas do tabuleiro devem ser visitadas pelo cavalo, sem repetir casas. O cavalo pode terminar o percurso em uma casa onde seja possivel alcançar a casa inicial no próximo movimento. Este cenário é chamado de caminho fechado, pois forma uma espécie de círculo. A outra forma é o caminho aberto, onde os casas de início e fim não conseguem se conectar diretamente.

Backtracking

Backtracking é uma técnica aplicável na solução de problemas de satisfação de restrições. Basicamente, a ideia é construir a solução de maneira gradual, observando todas as restrições a cada etapa. A solução de alguns problemas com backtracking geralmente usa uma lógica com recursividade. É importante notar que backtracking usa recursividade como uma maneira para implementar a solução. A recursividade por sí só não representa backtracking.

Em determinadas situações, testar todas as possibilidades é uma solução factível, muito mais útil que montar uma lógica complexa que resolva o problema. Uma solução inicial é expandida e novos elementos são adicionados. A cada iteração o algoritmo verifica se todas as restrições são atendidas. Assim, backtracking é uma técnica generalista que precisa ser adaptada para as necessidades de cada problema. No final, encontra-se uma solução, ou não, após testar tudo.

Para o problema do caminho do cavalo, fica evidente o quão naturalmente a solução pode ser encontrada ao se usar backtracking. Quando tentatamos resolver o problema por nós mesmos, uma forma de buscar uma solução é testar alguns caminhos, progredindo até quando percebemos que o cavalo está preso. Nesse ponto, dificilmente iniciamos a solução do zero. Preferimos voltar algumas casas e continuar dali.

Solução

O algoritmo inicia posicionando a peça em uma casa do tabuleiro, marca essa casa como ocupada e busca testar o próximo movimento a partir dessa casa. Daí basta repetir o processo. Sempre que uma restrição não for atendida, o algoritmo desfaz o caminho feito e tenta outro movimento. A natureza recursiva da solução fica responsável por desfazer caminhos que já foram testados.

A implementação abaixo busca a solução movimentando o cavalo de maneira aleatória entre as opções disponíveis até que todas as opções acabem. Adicionei o fator aleatório porque percebi que algumas soluções eram encontradas em alguns milissegundos por pura coincidência, isto é, a maneira como programei, ao testar alguns caminhos primeiro, encontrava uma solução rapidamente.

import kotlin.random.Random
import kotlin.time.measureTimedValue

class KnightPath(
    val boardSideSize: Int,
    val startRow: Int,
    val startColumn: Int
) {

    private val rdn = Random(System.nanoTime())
    private val boardSize = boardSideSize * boardSideSize
    private val path = Array(boardSideSize) {
        Array(boardSideSize) { EMPTY }
    }

    fun findPath(): List<Pair<Int, Int>> {
        path.forEach { a -> a.forEachIndexed { index, _ -> a[index] = EMPTY } }
        path[startRow][startColumn] = 0
        if (findPath(startRow, startColumn, 1)) {
            return path.flatMapIndexed { indexX, row ->
                row.mapIndexed { indexY, y -> y to Pair(indexX, indexY) }
            }.sortedBy { it.first }
                .map { it.second }
        }
        return emptyList()
    }

    private fun findPath(x: Int, y: Int, step: Int): Boolean {
        if (step == boardSize) {
            return true
        }
        val r = rdn.nextInt(1000000)
        for (shiftIndex in 0..7) {
            val idx = (r + shiftIndex) % 8
            val tX = x + shifts[0][idx]
            val tY = y + shifts[1][idx]
            if (
                tX !in 0 until boardSideSize
                || tY !in 0 until boardSideSize
                || path[tX][tY] != EMPTY
            ) {
                continue
            }
            path[tX][tY] = step
            if (findPath(tX, tY, step + 1)) {
                return true
            }
            path[tX][tY] = EMPTY
        }
        return false
    }

    companion object {
        private const val EMPTY = -1
        private val shifts = arrayOf(
            intArrayOf(-2, -2, -1, -1, +1, +1, +2, +2),
            intArrayOf(-1, +1, -2, +2, -2, +2, -1, +1),
        )
    }
}

fun main() {
    val tests = 1
    measureTimedValue {
        val rdn = Random(System.nanoTime())
        val boardSideSize = 7
        repeat(tests) {
            val startRow = 0
            val startColumn = 0
            KnightPath(
                boardSideSize = boardSideSize,
                startRow = 0,
                startColumn = 0
            ).findPath()
                .apply {
                    if (isEmpty()) println("No solution found starting in [$startRow, $startColumn]")
                }
                .forEachIndexed { index, pair ->
                    println("#${index + 1} - [${pair.first}, ${pair.second}]")
                }
        }
    }.duration.inWholeMilliseconds.run {
        println("Duration: ${this / tests} ms")
    }
}
Kotlin

Ao testar essa solução, no entanto, notei que ela não era performática. Mesmo buscando os caminhos de maneira aleatória, iniciando o caminho em determinadas casas fazia com que a solução demorasse muito a ser encontrada. Em tabuleiros de tamanho 8×8, o algoritmo continua a procurar mesmo depois de várias horas.

Tive que implementar uma técnica chamada de Heurística de Warnsdorff. A partir de uma posição, o algoritmo vai testar primeiro o movimento que leva à menor quantidade de opções no movimento subsequente. Isso reduz bastante quantidade de caminhos que precisam ser testando, provocando que uma solução seja encontrada mais rapidamente. Em outras palavras, se o cavalo está na posição X e tem como opção as casas A, B e C para mover, ele vai testar primeiro a casa A se, a partir dela, o cavalo conseguir ir a menos locais do que se estivesse em C ou B.

import kotlin.random.Random
import kotlin.time.measureTimedValue

class KnightPath(
    val boardSideSize: Int,
    val startRow: Int,
    val startColumn: Int
) {

    private val boardSize = boardSideSize * boardSideSize
    private val availableMoves = Array(8) {
        Array(3) { 0 }
    }
    private val path = Array(boardSideSize) {
        Array(boardSideSize) { EMPTY }
    }

    fun findPath(): List<Pair<Int, Int>> {
        path.forEach { a -> a.forEachIndexed { index, _ -> a[index] = EMPTY } }
        path[startRow][startColumn] = 0
        if (findPath(startRow, startColumn, 1)) {
            return path.flatMapIndexed { indexX, row ->
                row.mapIndexed { indexY, y -> y to Pair(indexX, indexY) }
            }.sortedBy { it.first }
                .map { it.second }
        }
        return emptyList()
    }

    private fun findPath(x: Int, y: Int, step: Int): Boolean {
        if (step == boardSize) {
            return true
        }
        val totalMoves = generateMovesByWarnsdorffHeuristic(x, y)
        for (moveIndex in 0 until totalMoves) {
            val move = availableMoves[moveIndex]
            path[move[0]][move[1]] = step
            if (findPath(move[0], move[1], step + 1)) {
                return true
            }
            path[move[0]][move[1]] = EMPTY
        }
        return false
    }

    private fun generateMovesByWarnsdorffHeuristic(x: Int, y: Int): Int {
        var foundMoves = 0
        for (shiftIndex in 0..7) {
            val tx = x + shifts[0][shiftIndex]
            val ty = y + shifts[1][shiftIndex]
            if (!isSafe(tx, ty)) {
                continue
            }
            var counter = 0
            for (shiftIndex2 in 0..7) {
                if (
                    isSafe(
                        tx + shifts[0][shiftIndex2],
                        ty + shifts[1][shiftIndex2]
                    )
                ) {
                    counter++
                }
            }
            availableMoves[foundMoves][0] = tx
            availableMoves[foundMoves][1] = ty
            availableMoves[foundMoves][2] = counter
            foundMoves++
        }
        (foundMoves until availableMoves.size).forEach { i ->
            availableMoves[i][2] = Int.MAX_VALUE
        }
        availableMoves.sortBy { it[2] }
        return foundMoves
    }

    private fun isSafe(x: Int, y: Int): Boolean {
        return (x in 0 until boardSideSize)
                && y in (0 until boardSideSize)
                && path[x][y] == EMPTY
    }

    companion object {
        private const val EMPTY = -1
        private val shifts = arrayOf(
            intArrayOf(-2, -2, -1, -1, +1, +1, +2, +2),
            intArrayOf(-1, +1, -2, +2, -2, +2, -1, +1),
        )
    }
}

fun main() {
    val tests = 5
    measureTimedValue {
        val boardSideSize = 8
        repeat(tests) {
            val startRow = Random.nextInt(boardSideSize)
            val startColumn = Random.nextInt(boardSideSize)
            KnightPath(
                boardSideSize = boardSideSize,
                startRow = startRow,
                startColumn = startColumn
            ).findPath()
                .apply {
                    if (isEmpty()) println("No solution found starting in [$startRow, $startColumn]")
                }
                .forEachIndexed { index, pair ->
                    println("#${index + 1} - [${pair.first}, ${pair.second}]")
                }
        }
    }.duration.inWholeMilliseconds.run {
        println("Duration: ${this / tests} ms")
    }
}
Kotlin

A busca por uma solução no tabuleiro 8×8 que levaria várias horas numa implementação mais simples, terminou em alguns milissegundos usando a Heurística de Warnsdorff. Conseguiu encontrar soluções para tabuleiros bem maiores, como 1000×1000 (1 milhão de casas), que custou apenas 6 segundos.

Conclusão

Força bruta é uma solução para diversos problemas computacionais e backtracking é uma das formas de implementar essa solução. Por testar todas as possibilidades, a busca eventualmente alcança uma solução ótima.

No entanto, a complexidade de tempo necessária à execução do programa pode se tornar um fator crítico. O tempo necessário pode não ser factível mesmo para pequenas instâncias. Conhecer o domínio do problema que está sendo resolvido é importante, uma vez que dependendo da quantidade de estados possíveis, o algoritmo pode ser muito caro do ponto de vista de tempo. Assim, conhecer o problema possibilita a aplicação de otimizações, como a Heurística de Warnsdorff no caminho do cavalo, fazendo que caminhos que não levam a uma solução nem sejam avaliados, ou escolhendo caminhos melhores primeiro.

Outro fator importante do trabalho com backtracking é assumir o seu caráter ad doc, ou seja, cada solução precisa ser implementada individualmente. Backtracking é uma técnica de tentativa e erro na construção da solução. As restrições que devem ser atendidas, como o modelo computacional vai ser construído, como a construção das soluções parciais vai ser realizada é uma especificidade de cada problema.

Com tudo isso, backtracking apresenta-se como uma solução válida para o problema do caminho do cavalo. Consequentemente, vários outros problemas que podem ter uma solução geral construída a partir de soluções parciais, ou ainda, cuja as configurações possíveis possam ser todas testadas, podem ser resolvidos com backtracking se bem implementadas, sempre levando-se em consideração o fator do tempo.

Referências

  • Artificial Intelligence – A Modern Approach, 4 ed., de Stuart Russell e Peter Norvig, publicado pela Pearson. Para adquirir o livro na Amazon Brasil: link
  • Programming Challenges: The Programming Contest Training Manual, 1 ed, de Steven S. Skiena e Miguel A. Revila, publicado pela Springer. Para adquirir o livro na Amazon Brasil: link
  • HEURÍSTICA EFICIENTE PARA O PASSEIO ABERTO DO CAVALO A PARTIR DE CASAS ARBITRÁRIAS EM TABULEIROS QUADRADOS, por Vitor Silva Costa e Vinícius Gusmão Pereira de Sá. Artigo disponível no em link

Categorized in:

Algoritmos,

Last Update: 27/03/2024

Tagged in:

, ,