O problema das N-Rainhas pede que você coloque N rainhas em um tabuleiro de xadrez N×N de modo que nenhuma duas rainhas se ataquem (nenhuma duas compartilhem uma linha, coluna ou diagonal). Por exemplo, se houver um tabuleiro 4x4, uma disposição válida é:

[1, 3, 0, 2]

Isso significa que na linha 0, a rainha está posicionada na coluna 1; na linha 1, a rainha está posicionada na coluna 3; na linha 2, a rainha está posicionada na coluna 0; e na linha 3, a rainha está posicionada na coluna 2. Visualmente, esse arranjo se parece com:

. Q . .
. . . Q
Q . . .
. . Q .

Onde Q representa uma rainha e . representa uma casa vazia. Neste laboratório, você implementará o resolvedor do problema das N-Rainhas usando a abordagem de busca em profundidade. Objetivo: Cumprir as user stories abaixo e fazer com que todos os testes passem para completar o laboratório. Histórias de Usuário: 1. Você deve ter uma função chamada dfs_n_queens. 2. A função deve aceitar exatamente um argumento: um inteiro n. 3. Se n for menor que 1, a função deve retornar uma lista vazia ([]). 4. A função deve retornar uma lista de soluções; cada solução é ela mesma uma lista de comprimento n, onde o elemento no índice i é o índice da coluna (baseado em 0) da rainha na linha i.

Testes:

• Você deve ter uma função chamada `dfs_n_queens` que recebe um argumento.
• Se `n` for menor que `1`, a função deve retornar uma lista vazia.
• A função deve retornar uma lista de soluções, onde cada solução é uma lista de comprimento `n`.
• `dfs_n_queens(1)` deve retornar `[[0]]`.
• `dfs_n_queens(2)` deve retornar `[]`.
• `dfs_n_queens(3)` deve retornar `[]`.
• `dfs_n_queens(4)` deve retornar `[[1, 3, 0, 2], [2, 0, 3, 1]]`.
• `dfs_n_queens(5)` deve retornar `[[0, 2, 4, 1, 3], [0, 3, 1, 4, 2], [1, 3, 0, 2, 4], [1, 4, 2, 0, 3], [2, 0, 3, 1, 4], [2, 4, 1, 3, 0], [3, 0, 2, 4, 1], [3, 1, 4, 2, 0], [4, 1, 3, 0, 2], [4, 2, 0, 3, 1]]`.
• `len(dfs_n_queens(5))` deve ser `10`.
• `len(dfs_n_queens(8))` deve ser `92`.
• `dfs_n_queens` deve retornar o resultado correto.