Questo non è (IMO) un problema molto interessante da un punto di vista della programmazione. Potresti trovare un algoritmo ricorsivo che provi ogni arrangiamento, qualcosa del genere:
bool try_queens(Board board, int n)
{
if (n == 0) {
// no queens left to place, so we're done
return true
}
// try each open position until we find one that works
for each position on the board {
if (is_empty(board, position) and not is_attacked(board, position)) {
place_queen(board, position)
if (try_queens(board, n-1)) {
return true
}
remove_queen(board, position)
}
}
// if we get this far, there's no available position
return false
}
main()
{
initialize board(X,Y)
return try_queens(board, N)
}
Se pensi un po 'al problema, ti renderai conto che non c'è modo di adattare N queens su una board dove X < N o Y < N perché ciò richiederebbe che almeno due regine finissero nello stesso grado o file, e quindi si attaccerebbero l'un l'altro. Se leggi il problema di n-queens, imparerai presto che è sempre possibile posizionare N queens su una scheda NxN per N > 3. Ora sappiamo che la risposta è NO per (X < N o Y < N) e YES per (X > = N e Y > = N, N > 3). Tutto ciò che rimane sono i casi speciali:
- N = 1 (YES)
- N = 2 (YES per X > = 2 e Y > 2 o viceversa)
- N = 3 (YES per X > = 3 e Y > 3 o viceversa)
Quindi ora la nostra bella funzione ricorsiva diventa una semplice funzione che confronta solo N a X e Y e restituisce un risultato in scatola. È fantastico dal punto di vista delle prestazioni, dal momento che è possibile ottenere una risposta in tempo costante. Non è così bello da un punto di vista della programmazione perché ti rendi conto, a questo punto, che la domanda è più che altro su quanto riesci a risolvere i puzzle piuttosto che sulla tua capacità di scrivere una funzione ricorsiva.
(E ragazzo oh ragazzo, spero davvero che non abbia fatto un errore stupido nella mia risposta da smarty-pants. ;-))
