Em um tabuleiro de xadrez, a rainha é uma peça poderosa, pois sua posição invalida muitas outras casas. Para transformar isso em um problema de busca, começamos descrevendo exatamente quais casas uma rainha ataca; assim, podemos tratar os ataques como restrições que invalidam possíveis posicionamentos. Essa abordagem é importante porque permite que um algoritmo de resolução construa uma solução candidata passo a passo, descartando candidatos parciais assim que violam uma regra, em vez de esperar até que o tabuleiro esteja totalmente preenchido.
Um posicionamento é válido apenas se nenhuma rainha atacar outra, o que significa que três restrições devem ser satisfeitas simultaneamente. Duas rainhas não podem compartilhar a mesma linha, a mesma coluna nem a mesma diagonal.
Para visualizar essas restrições na prática, observe como uma única rainha em uma coordenada específica marca as casas atacadas em um tabuleiro pequeno.
As restrições de linha e coluna são diretas, pois qualquer casa com o mesmo índice de linha ou de coluna é atacada. A restrição de diagonal também é mecânica, uma vez que as casas permanecem em uma diagonal quando suas coordenadas de linha e coluna variam simultaneamente; assim, uma rainha ataca as casas situadas ao longo das duas direções diagonais até que a borda do tabuleiro interrompa a linha.
Uma vez esclarecidas as restrições, o próximo passo é escolher uma representação que facilite a construção incremental de soluções candidatas. Uma opção simples é um array unidimensional no qual queens[row] = col, indicando que a rainha da linha row está posicionada na coluna col. Com essa representação, a restrição de linha é garantida pela própria estrutura, visto que cada índice de linha aparece apenas uma vez.
O widget demonstra como um array específico corresponde a uma configuração do tabuleiro.