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 dfsNQueens. 2. A função deve aceitar exatamente um argumento: um inteiro n. 3. Se n for menor que 1, a função deve retornar um array vazio ([]). 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 `dfsNQueens` que recebe um argumento.
• Se `n` for menor que `1`, a função deve retornar um array vazio.
• A função deve retornar um array de soluções, onde cada solução é um array de comprimento `n`.
• `dfsNQueens(1)` deve retornar `[[0]]`.
• `dfsNQueens(2)` deve retornar `[]`.
• `dfsNQueens(3)` deve retornar `[]`.
• `dfsNQueens(4)` deve retornar `[[1, 3, 0, 2], [2, 0, 3, 1]]`.
• `dfsNQueens(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]]`.
• `dfsNQueens(5).length` deve ser `10`.
• `dfsNQueens(8).length` deve ser `92`.
• `dfsNQueens` deve retornar o resultado correto.