N皇后算法

Question

Algorithm NQueens ( k, n) //Prints all Solution to the n-queens problem
{
    for i := 1 to n do
    {
        if Place (k, i) then
        {
            x[k] := i;
            if ( k = n) then write ( x [1 : n]
            else NQueens ( k+1, n);
        }
    }
}

Algorithm Place (k, i)
{
    for j := 1 to k-1 do
        if (( x[ j ] = // in the same column
           or (Abs( x [ j ] - i) =Abs ( j – k ))) // or in the same diagonal
        then return false;
        return true;
}

上面的代码是用来解决N皇后问题的，我认为它可以将两列的前两个皇后放在各自的列中，然后当涉及到第三排皇后时，它不能被放置，因为没有皇后需要攻击，它只会从算法N queens...So中退出，这个算法是如何实现回溯的？

Answer 1

这里的秘密是递归。

让下面的每一层缩进表示递归的级别。

(并不是真正会发生什么，因为第三皇后可以很容易地被安置，但只是需要更多的写作和/或思考才能找到一个真正失败的案例)

try to place first queen
success
   try to place second queen
   success
      try to place third queen
      fail
   try to place second queen in another position
   success
      try to place third queen
      success
         try to place fourth queen

更符合代码实际操作的内容：(仍然不符合实际发生的情况)

first queen
i = 1
Can place? Yes. Cool, recurse.
   second queen
   i = 1
   Can place? No.
   i = 2
   Can place? No.
   i = 3
   Can place? Yes. Cool, recurse.
      third queen
      i = 1
      Can place? No.
      i = 2
      Can place? No.
      ... (can be placed at no position)
      fail
      back to second queen
   i = 4
   Can place? Yes. Cool, recurse.
      third queen
      i = 1
      Can place? No.
      ...

我希望这能帮上忙。

Answer 2

我刚刚决定用女皇之谜语言编写我的Python解决方案，下面是代码，它非常快，在几十秒内它找到了1-8皇后的所有解决方案，9皇后在几分钟内找到了所有的解决方案。它再次测试wiki的计数解部分中的参考编号。

解采用递归 回溯方法和快速numpy库，它只按组合的字典顺序搜索解，所有相同位置的皇后的排列都被认为是相同的，除了先搜索之外，所有的排列都不被搜索。所以算法是相当快的。

在网上试试！

def Main():
    import numpy as np
    
    con_width = 80 # Console width

    for h, w, n, rcnt in [
        # h - heignt, w - width, n - num queens
        # Create all tests here
    ] + [(i + 1, i + 1, i + 1, rcnt) for i, rcnt in enumerate([
        # See https://oeis.org/A000170/b000170.txt
        1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712, 365596, 2279184, 14772512, 95815104, 666090624, 4968057848, 39029188884,
    ])]:
        # Create empty board
        board = np.zeros([h, w], dtype = np.int8)
        sols = {}
        # Recursive function for placing next queen using back-propagation
        def Solve(*, qcnt = 0, fy = 0, fx = 0):
            nonlocal board, sols
            if qcnt >= n:
                sola = np.nonzero(board > 0)
                sol = tuple((y, x) for y, x in zip(sola[0].tolist(), sola[1].tolist()))
                assert sol not in sols
                sols[sol] = np.copy(board)
                return
            # Find coordinates of all available positions (zeroes)
            av = np.nonzero(board == 0)
            # Skip previous placed results
            ava = np.vstack(av).T
            avc = np.count_nonzero((ava[:, 0] < fy) | ((ava[:, 0] == fy) & (ava[:, 1] < fx)))
            av = (av[0][avc:], av[1][avc:])
            
            for i in range(av[0].shape[0]):
                # Get next available position
                y, x = av[0][i], av[1][i]
                assert board[y, x] == 0, (y, x, board[y, x])
                
                # Try placing queen into (y, x)
                
                ps = np.zeros([2, 0], dtype = np.int32)
                
                # Same row
                ps = np.concatenate((ps, [np.full([w], y), np.arange(w)]), 1)
                # Same column
                ps = np.concatenate((ps, [np.arange(h), np.full([h], x)]), 1)
                # Same primary diagonal
                if y < x:
                    dlen = min(h, w - (x - y))
                    ps = np.concatenate((ps, [np.arange(dlen), np.arange(x - y, x - y + dlen)]), 1)
                else:
                    dlen = min(w, h - (y - x))
                    ps = np.concatenate((ps, [np.arange(y - x, y - x + dlen), np.arange(dlen)]), 1)
                # Same secondary diagonal
                dlen = min(h, w, x + y + 1)
                ps = np.concatenate((ps, [
                    np.arange((x + y) - min(x + y, w - 1), min(x + y, h - 1) + 1),
                    np.arange(min(x + y, w - 1), max(0, x + y - (h - 1)) - 1, -1),
                ]), 1)
                
                ps = (ps[0, :].astype(np.int32), ps[1, :].astype(np.int32))
                
                #print('placing', qcnt + 1, '(', y, x, ')\n', ps, '\n', board)
                # Backup current values in positions
                cvs = np.copy(board[ps])
                # Attack all positions
                board[ps] = -1
                # Place queen
                board[y, x] = qcnt + 1
                #print('placed\n', board)
                # Recurse
                Solve(qcnt = qcnt + 1, fy = (y + 1, y)[bool(x + 1 < w)], fx = (x + 1) % w)
                # Undo placed queen and attacked positions
                board[ps] = cvs
        
        print(f'Testing: h = {h}, w = {w}, n = {n}, sols = {rcnt}\n')
        
        Solve()
        
        lcnt = con_width // (w + 1)
        sols = sorted(sols.items(), key = lambda e: e[0])
        for ibl in range((len(sols) + lcnt - 1) // lcnt):
            for l in range(h):
                for i in range(ibl * lcnt, min((ibl + 1) * lcnt, len(sols))):
                    sol = sols[i][1]
                    print(''.join([('.', 'X')[e] for e in (sol[l, :] > 0).astype(np.uint8).tolist()]) + ' ', end = '')
                print()
            print()
        
        num_sols = len(sols)
        print(f'Result: h = {h}, w = {w}, n = {n}, sols = {num_sols}')
        print('-' * con_width)
        if rcnt is not None:
            assert num_sols == rcnt, (h, w, n, num_sols, rcnt)
                        
Main()

它的产出如下：

Testing: h = 1, w = 1, n = 1, sols = 1

X 

Result: h = 1, w = 1, n = 1, sols = 1
--------------------------------------------------------------------------------
Testing: h = 2, w = 2, n = 2, sols = 0

Result: h = 2, w = 2, n = 2, sols = 0
--------------------------------------------------------------------------------
Testing: h = 3, w = 3, n = 3, sols = 0

Result: h = 3, w = 3, n = 3, sols = 0
--------------------------------------------------------------------------------
Testing: h = 4, w = 4, n = 4, sols = 2

.X.. ..X. 
...X X... 
X... ...X 
..X. .X.. 

Result: h = 4, w = 4, n = 4, sols = 2
--------------------------------------------------------------------------------
Testing: h = 5, w = 5, n = 5, sols = 10

X.... X.... .X... .X... ..X.. ..X.. ...X. ...X. ....X ....X 
..X.. ...X. ...X. ....X X.... ....X X.... .X... .X... ..X.. 
....X .X... X.... ..X.. ...X. .X... ..X.. ....X ...X. X.... 
.X... ....X ..X.. X.... .X... ...X. ....X ..X.. X.... ...X. 
...X. ..X.. ....X ...X. ....X X.... .X... X.... ..X.. .X... 

Result: h = 5, w = 5, n = 5, sols = 10
--------------------------------------------------------------------------------
Testing: h = 6, w = 6, n = 6, sols = 4

.X.... ..X... ...X.. ....X. 
...X.. .....X X..... ..X... 
.....X .X.... ....X. X..... 
X..... ....X. .X.... .....X 
..X... X..... .....X ...X.. 
....X. ...X.. ..X... .X.... 

Result: h = 6, w = 6, n = 6, sols = 4
--------------------------------------------------------------------------------
Testing: h = 7, w = 7, n = 7, sols = 40

X...... X...... X...... X...... .X..... .X..... .X..... .X..... .X..... .X..... 
..X.... ...X... ....X.. .....X. ...X... ...X... ....X.. ....X.. ....X.. .....X. 
....X.. ......X .X..... ...X... X...... .....X. X...... ..X.... ......X ..X.... 
......X ..X.... .....X. .X..... ......X X...... ...X... X...... ...X... ......X 
.X..... .....X. ..X.... ......X ....X.. ..X.... ......X ......X X...... ...X... 
...X... .X..... ......X ....X.. ..X.... ....X.. ..X.... ...X... ..X.... X...... 
.....X. ....X.. ...X... ..X.... .....X. ......X .....X. .....X. .....X. ....X.. 

.X..... ..X.... ..X.... ..X.... ..X.... ..X.... ..X.... ...X... ...X... ...X... 
......X X...... X...... ....X.. .....X. ......X ......X X...... X...... .X..... 
....X.. .....X. .....X. ......X .X..... .X..... ...X... ..X.... ....X.. ......X 
..X.... .X..... ...X... .X..... ....X.. ...X... X...... .....X. .X..... ....X.. 
X...... ....X.. .X..... ...X... X...... .....X. ....X.. .X..... .....X. ..X.... 
.....X. ......X ......X .....X. ...X... X...... .X..... ......X ..X.... X...... 
...X... ...X... ....X.. X...... ......X ....X.. .....X. ....X.. ......X .....X. 

...X... ...X... ...X... ....X.. ....X.. ....X.. ....X.. ....X.. ....X.. .....X. 
.....X. ......X ......X X...... X...... .X..... ..X.... ......X ......X X...... 
X...... ..X.... ....X.. ...X... .....X. .....X. X...... .X..... .X..... ..X.... 
..X.... .....X. .X..... ......X ...X... ..X.... .....X. ...X... .....X. ....X.. 
....X.. .X..... .....X. ..X.... .X..... ......X ...X... .....X. ..X.... ......X 
......X ....X.. X...... .....X. ......X ...X... .X..... X...... X...... .X..... 
.X..... X...... ..X.... .X..... ..X.... X...... ......X ..X.... ...X... ...X... 

.....X. .....X. .....X. .....X. .....X. .....X. ......X ......X ......X ......X 
.X..... ..X.... ..X.... ..X.... ...X... ...X... .X..... ..X.... ...X... ....X.. 
....X.. X...... ....X.. ......X .X..... ......X ...X... .....X. X...... ..X.... 
X...... ...X... ......X ...X... ......X X...... .....X. .X..... ....X.. X...... 
...X... ......X X...... X...... ....X.. ..X.... X...... ....X.. .X..... .....X. 
......X ....X.. ...X... ....X.. ..X.... ....X.. ..X.... X...... .....X. ...X... 
..X.... .X..... .X..... .X..... X...... .X..... ....X.. ...X... ..X.... .X..... 

Result: h = 7, w = 7, n = 7, sols = 40
--------------------------------------------------------------------------------
Testing: h = 8, w = 8, n = 8, sols = 92

X....... X....... X....... X....... .X...... .X...... .X...... .X...... 
....X... .....X.. ......X. ......X. ...X.... ....X... ....X... .....X.. 
.......X .......X ...X.... ....X... .....X.. ......X. ......X. X....... 
.....X.. ..X..... .....X.. .......X .......X X....... ...X.... ......X. 
..X..... ......X. .......X .X...... ..X..... ..X..... X....... ...X.... 
......X. ...X.... .X...... ...X.... X....... .......X .......X .......X 
.X...... .X...... ....X... .....X.. ......X. .....X.. .....X.. ..X..... 
...X.... ....X... ..X..... ..X..... ....X... ...X.... ..X..... ....X... 

.X...... .X...... .X...... .X...... ..X..... ..X..... ..X..... ..X..... 
.....X.. ......X. ......X. .......X X....... ....X... ....X... ....X... 
.......X ..X..... ....X... .....X.. ......X. .X...... .X...... ......X. 
..X..... .....X.. .......X X....... ....X... .......X .......X X....... 
X....... .......X X....... ..X..... .......X X....... .....X.. ...X.... 
...X.... ....X... ...X.... ....X... .X...... ......X. ...X.... .X...... 
......X. X....... .....X.. ......X. ...X.... ...X.... ......X. .......X 
....X... ...X.... ..X..... ...X.... .....X.. .....X.. X....... .....X.. 

..X..... ..X..... ..X..... ..X..... ..X..... ..X..... ..X..... ..X..... 
....X... .....X.. .....X.. .....X.. .....X.. .....X.. .....X.. .....X.. 
.......X .X...... .X...... .X...... ...X.... ...X.... .......X .......X 
...X.... ....X... ......X. ......X. X....... .X...... X....... X....... 
X....... .......X X....... ....X... .......X .......X ...X.... ....X... 
......X. X....... ...X.... X....... ....X... ....X... ......X. ......X. 
.X...... ......X. .......X .......X ......X. ......X. ....X... .X...... 
.....X.. ...X.... ....X... ...X.... .X...... X....... .X...... ...X.... 

..X..... ..X..... ..X..... ..X..... ...X.... ...X.... ...X.... ...X.... 
.....X.. ......X. ......X. .......X X....... X....... .X...... .X...... 
.......X .X...... .X...... ...X.... ....X... ....X... ....X... ......X. 
.X...... .......X .......X ......X. .......X .......X .......X ..X..... 
...X.... ....X... .....X.. X....... .X...... .....X.. .....X.. .....X.. 
X....... X....... ...X.... .....X.. ......X. ..X..... X....... .......X 
......X. ...X.... X....... .X...... ..X..... ......X. ..X..... X....... 
....X... .....X.. ....X... ....X... .....X.. .X...... ......X. ....X... 

...X.... ...X.... ...X.... ...X.... ...X.... ...X.... ...X.... ...X.... 
.X...... .X...... .X...... .X...... .....X.. .....X.. .....X.. ......X. 
......X. ......X. .......X .......X X....... .......X .......X X....... 
..X..... ....X... ....X... .....X.. ....X... .X...... ..X..... .......X 
.....X.. X....... ......X. X....... .X...... ......X. X....... ....X... 
.......X .......X X....... ..X..... .......X X....... ......X. .X...... 
....X... .....X.. ..X..... ....X... ..X..... ..X..... ....X... .....X.. 
X....... ..X..... .....X.. ......X. ......X. ....X... .X...... ..X..... 

...X.... ...X.... ...X.... ...X.... ...X.... ...X.... ....X... ....X... 
......X. ......X. ......X. .......X .......X .......X X....... X....... 
..X..... ....X... ....X... X....... X....... ....X... ...X.... .......X 
.......X .X...... ..X..... ..X..... ....X... ..X..... .....X.. ...X.... 
.X...... .....X.. X....... .....X.. ......X. X....... .......X .X...... 
....X... X....... .....X.. .X...... .X...... ......X. .X...... ......X. 
X....... ..X..... .......X ......X. .....X.. .X...... ......X. ..X..... 
.....X.. .......X .X...... ....X... ..X..... .....X.. ..X..... .....X.. 

....X... ....X... ....X... ....X... ....X... ....X... ....X... ....X... 
X....... .X...... .X...... .X...... .X...... ..X..... ..X..... ..X..... 
.......X ...X.... ...X.... .....X.. .......X X....... X....... .......X 
.....X.. .....X.. ......X. X....... X....... .....X.. ......X. ...X.... 
..X..... .......X ..X..... ......X. ...X.... .......X .X...... ......X. 
......X. ..X..... .......X ...X.... ......X. .X...... .......X X....... 
.X...... X....... .....X.. .......X ..X..... ...X.... .....X.. .....X.. 
...X.... ......X. X....... ..X..... .....X.. ......X. ...X.... .X...... 

....X... ....X... ....X... ....X... ....X... ....X... ....X... ....X... 
......X. ......X. ......X. ......X. ......X. ......X. .......X .......X 
X....... X....... .X...... .X...... .X...... ...X.... ...X.... ...X.... 
..X..... ...X.... ...X.... .....X.. .....X.. X....... X....... X....... 
.......X .X...... .......X ..X..... ..X..... ..X..... ..X..... ......X. 
.....X.. .......X X....... X....... X....... .......X .....X.. .X...... 
...X.... .....X.. ..X..... ...X.... .......X .....X.. .X...... .....X.. 
.X...... ..X..... .....X.. .......X ...X.... .X...... ......X. ..X..... 

.....X.. .....X.. .....X.. .....X.. .....X.. .....X.. .....X.. .....X.. 
X....... .X...... .X...... ..X..... ..X..... ..X..... ..X..... ..X..... 
....X... ......X. ......X. X....... X....... X....... ....X... ....X... 
.X...... X....... X....... ......X. .......X .......X ......X. .......X 
.......X ..X..... ...X.... ....X... ...X.... ....X... X....... X....... 
..X..... ....X... .......X .......X .X...... .X...... ...X.... ...X.... 
......X. .......X ....X... .X...... ......X. ...X.... .X...... .X...... 
...X.... ...X.... ..X..... ...X.... ....X... ......X. .......X ......X. 

.....X.. .....X.. .....X.. .....X.. .....X.. .....X.. .....X.. .....X.. 
..X..... ..X..... ..X..... ...X.... ...X.... ...X.... ...X.... .......X 
......X. ......X. ......X. X....... .X...... ......X. ......X. .X...... 
.X...... .X...... ...X.... ....X... .......X X....... X....... ...X.... 
...X.... .......X X....... .......X ....X... ..X..... .......X X....... 
.......X ....X... .......X .X...... ......X. ....X... .X...... ......X. 
X....... X....... .X...... ......X. X....... .X...... ....X... ....X... 
....X... ...X.... ....X... ..X..... ..X..... .......X ..X..... ..X..... 

......X. ......X. ......X. ......X. ......X. ......X. ......X. ......X. 
X....... .X...... .X...... ..X..... ..X..... ...X.... ...X.... ....X... 
..X..... ...X.... .....X.. X....... .......X .X...... .X...... ..X..... 
.......X X....... ..X..... .....X.. .X...... ....X... .......X X....... 
.....X.. .......X X....... .......X ....X... .......X .....X.. .....X.. 
...X.... ....X... ...X.... ....X... X....... X....... X....... .......X 
.X...... ..X..... .......X .X...... .....X.. ..X..... ..X..... .X...... 
....X... .....X.. ....X... ...X.... ...X.... .....X.. ....X... ...X.... 

.......X .......X .......X .......X 
.X...... .X...... ..X..... ...X.... 
...X.... ....X... X....... X....... 
X....... ..X..... .....X.. ..X..... 
......X. X....... .X...... .....X.. 
....X... ......X. ....X... .X...... 
..X..... ...X.... ......X. ......X. 
.....X.. .....X.. ...X.... ....X... 

Result: h = 8, w = 8, n = 8, sols = 92
--------------------------------------------------------------------------------
Testing: h = 9, w = 9, n = 9, sols = 352

X........ X........ X........ X........ X........ X........ X........ X........ 
..X...... ..X...... ..X...... ...X..... ...X..... ...X..... ...X..... ...X..... 
.....X... ......X.. .......X. .X....... .....X... .....X... ......X.. ......X.. 
.......X. .X....... .....X... .......X. ..X...... .......X. ..X...... ........X 
.X....... .......X. ........X .....X... ........X .X....... .......X. .X....... 
...X..... ....X.... .X....... ........X .X....... ....X.... .X....... ....X.... 
........X ........X ....X.... ..X...... .......X. ..X...... ....X.... .......X. 
......X.. ...X..... ......X.. ....X.... ....X.... ........X ........X .....X... 
....X.... .....X... ...X..... ......X.. ......X.. ......X.. .....X... ..X...... 

X........ X........ X........ X........ X........ X........ X........ X........ 
...X..... ....X.... ....X.... ....X.... ....X.... ....X.... ....X.... .....X... 
.......X. .X....... ......X.. ......X.. ......X.. ........X ........X .X....... 
..X...... .....X... .X....... ........X ........X .X....... .....X... ........X 
........X ........X .....X... ..X...... ...X..... .....X... ...X..... ......X.. 
......X.. ..X...... ..X...... .......X. .X....... .......X. .X....... ...X..... 
....X.... .......X. ........X .X....... .......X. ..X...... .......X. .......X. 
.X....... ...X..... ...X..... ...X..... .....X... ......X.. ..X...... ..X...... 
.....X... ......X.. .......X. .....X... ..X...... ...X..... ......X.. ....X.... 

X........ X........ X........ X........ X........ X........ X........ X........ 
.....X... .....X... .....X... .....X... .....X... ......X.. ......X.. ......X.. 
...X..... ...X..... .......X. .......X. ........X ...X..... ...X..... ...X..... 
.X....... .X....... ..X...... ....X.... ....X.... .....X... .......X. .......X. 
......X.. .......X. ......X.. .X....... .X....... ........X ..X...... ..X...... 
........X ..X...... ...X..... ...X..... .......X. .X....... ....X.... ........X 
..X...... ........X .X....... ........X ..X...... ....X.... ........X .....X... 
....X.... ......X.. ........X ......X.. ......X.. ..X...... .X....... .X....... 
.......X. ....X.... ....X.... ..X...... ...X..... .......X. .....X... ....X.... 

X........ X........ X........ X........ .X....... .X....... .X....... .X....... 
......X.. .......X. .......X. .......X. ...X..... ...X..... ...X..... ...X..... 
....X.... ...X..... ....X.... ....X.... X........ ......X.. .......X. ........X 
.......X. .X....... ..X...... ..X...... ......X.. X........ ..X...... ......X.. 
.X....... ......X.. .....X... ........X ........X ..X...... ........X ..X...... 
........X ........X ........X ......X.. .....X... ........X .....X... X........ 
..X...... .....X... .X....... .X....... ..X...... .....X... X........ .....X... 
.....X... ..X...... ...X..... ...X..... ....X.... .......X. ....X.... .......X. 
...X..... ....X.... ......X.. .....X... .......X. ....X.... ......X.. ....X.... 

.X....... .X....... .X....... .X....... .X....... .X....... .X....... .X....... 
...X..... ....X.... ....X.... ....X.... ....X.... ....X.... ....X.... ....X.... 
........X ......X.. ......X.. ......X.. ......X.. .......X. .......X. .......X. 
......X.. X........ ...X..... ........X ........X X........ X........ .....X... 
....X.... ..X...... X........ ..X...... ...X..... ..X...... ........X ........X 
..X...... .......X. ..X...... .....X... .......X. .....X... .....X... ..X...... 
X........ .....X... ........X ...X..... X........ ........X ..X...... X........ 
.....X... ...X..... .....X... X........ ..X...... ......X.. ......X.. ...X..... 
.......X. ........X .......X. .......X. .....X... ...X..... ...X..... ......X.. 

.X....... .X....... .X....... .X....... .X....... .X....... .X....... .X....... 
....X.... ....X.... .....X... .....X... .....X... .....X... .....X... .....X... 
.......X. ........X X........ X........ X........ X........ ..X...... ........X 
.....X... ...X..... ..X...... ......X.. ......X.. ........X X........ ..X...... 
........X X........ ......X.. ...X..... ....X.... ....X.... .......X. ....X.... 
..X...... .......X. ........X .......X. ..X...... .......X. ...X..... .......X. 
X........ .....X... ...X..... ..X...... ........X ...X..... ........X ...X..... 
......X.. ..X...... .......X. ....X.... ...X..... ......X.. ......X.. X........ 
...X..... ......X.. ....X.... ........X .......X. ..X...... ....X.... ......X.. 

.X....... .X....... .X....... .X....... .X....... .X....... .X....... .X....... 
......X.. ......X.. ......X.. .......X. .......X. .......X. ........X ........X 
....X.... ....X.... ........X X........ ....X.... .....X... ....X.... .....X... 
X........ .......X. .....X... ...X..... ..X...... ........X ..X...... ..X...... 
........X X........ ..X...... ......X.. ........X ..X...... .......X. ....X.... 
...X..... ...X..... X........ ........X .....X... X........ ...X..... .......X. 
.....X... .....X... ...X..... .....X... ...X..... ...X..... ......X.. X........ 
.......X. ..X...... .......X. ..X...... X........ ......X.. X........ ...X..... 
..X...... ........X ....X.... ....X.... ......X.. ....X.... .....X... ......X.. 

.X....... .X....... ..X...... ..X...... ..X...... ..X...... ..X...... ..X...... 
........X ........X X........ X........ X........ X........ X........ X........ 
.....X... .....X... ...X..... .....X... ......X.. ......X.. .......X. ........X 
..X...... ...X..... ......X.. .......X. .X....... ....X.... ...X..... ......X.. 
......X.. ......X.. ........X ....X.... .......X. .......X. ........X ....X.... 
...X..... X........ .X....... .X....... .....X... .X....... ......X.. .X....... 
X........ ..X...... ....X.... ...X..... ...X..... ...X..... ....X.... .......X. 
.......X. ....X.... .......X. ........X ........X .....X... .X....... .....X... 
....X.... .......X. .....X... ......X.. ....X.... ........X .....X... ...X..... 

..X...... ..X...... ..X...... ..X...... ..X...... ..X...... ..X...... ..X...... 
....X.... ....X.... ....X.... ....X.... ....X.... ....X.... ....X.... .....X... 
.X....... .X....... ......X.. .......X. .......X. ........X ........X .X....... 
.......X. .......X. X........ .X....... .X....... .X....... ...X..... ......X.. 
X........ X........ ...X..... ........X ........X ...X..... X........ X........ 
...X..... ......X.. .X....... .....X... ......X.. ......X.. ......X.. ...X..... 
......X.. ...X..... .......X. X........ X........ X........ .X....... .......X. 
........X .....X... .....X... ......X.. ...X..... .......X. .....X... ....X.... 
.....X... ........X ........X ...X..... .....X... .....X... .......X. ........X 

..X...... ..X...... ..X...... ..X...... ..X...... ..X...... ..X...... ..X...... 
.....X... .....X... .....X... .....X... .....X... .....X... .....X... .....X... 
.X....... .......X. .......X. .......X. .......X. .......X. ........X ........X 
........X X........ X........ .X....... ....X.... ....X.... X........ .X....... 
....X.... ...X..... ....X.... ...X..... X........ .X....... .......X. ....X.... 
X........ ......X.. ........X ........X ........X ........X ...X..... ......X.. 
.......X. ....X.... .X....... ......X.. ......X.. ......X.. .X....... ...X..... 
...X..... .X....... ...X..... ....X.... .X....... ...X..... ......X.. X........ 
......X.. ........X ......X.. X........ ...X..... X........ ....X.... .......X. 

..X...... ..X...... ..X...... ..X...... ..X...... ..X...... ..X...... ..X...... 
.....X... .....X... .....X... .....X... .....X... ......X.. ......X.. ......X.. 
........X ........X ........X ........X ........X .X....... .X....... .X....... 
.X....... ....X.... ......X.. ......X.. ......X.. ...X..... .......X. .......X. 
.......X. .......X. X........ .X....... ...X..... .......X. ....X.... .....X... 
X........ X........ ...X..... ...X..... X........ X........ ........X ...X..... 
...X..... ...X..... .X....... .......X. .......X. ....X.... X........ X........ 
......X.. .X....... ....X.... X........ .X....... ........X .....X... ....X.... 
....X.... ......X.. .......X. ....X.... ....X.... .....X... ...X..... ........X 

..X...... ..X...... ..X...... ..X...... ..X...... ..X...... ..X...... ..X...... 
......X.. ......X.. ......X.. ......X.. ......X.. .......X. .......X. .......X. 
...X..... ...X..... ...X..... ........X ........X .X....... ...X..... .....X... 
.X....... .X....... .......X. X........ ...X..... ...X..... ......X.. X........ 
........X ........X ....X.... ....X.... .X....... ........X ........X ........X 
....X.... .....X... ........X .X....... ....X.... ......X.. .X....... .X....... 
X........ X........ X........ .......X. .......X. ....X.... ....X.... ....X.... 
.......X. ....X.... .....X... .....X... .....X... X........ X........ ......X.. 
.....X... .......X. .X....... ...X..... X........ .....X... .....X... ...X..... 

..X...... ..X...... ..X...... ..X...... ..X...... ..X...... ..X...... ..X...... 
.......X. .......X. ........X ........X ........X ........X ........X ........X 
.....X... .....X... .X....... ...X..... ...X..... ...X..... .....X... .....X... 
...X..... ........X ....X.... X........ .X....... .......X. .X....... ...X..... 
........X .X....... .......X. .......X. .......X. ....X.... ....X.... X........ 
X........ ....X.... X........ .....X... .....X... .X....... ......X.. ......X.. 
....X.... X........ ......X.. .X....... X........ .....X... X........ ....X.... 
......X.. ...X..... ...X..... ......X.. ......X.. X........ ...X..... .X....... 
.X....... ......X.. .....X... ....X.... ....X.... ......X.. .......X. .......X. 

..X...... ...X..... ...X..... ...X..... ...X..... ...X..... ...X..... ...X..... 
........X X........ X........ X........ X........ X........ X........ .X....... 
.....X... ..X...... ....X.... ....X.... ....X.... ......X.. ........X ....X.... 
.......X. .....X... .X....... .......X. ........X ........X .....X... .......X. 
.X....... ........X ........X .X....... .X....... .X....... ..X...... X........ 
...X..... .X....... ......X.. ......X.. .....X... .....X... ......X.. ..X...... 
X........ .......X. ..X...... ..X...... .......X. .......X. .X....... .....X... 
......X.. ....X.... .......X. .....X... ..X...... ..X...... .......X. ........X 
....X.... ......X.. .....X... ........X ......X.. ....X.... ....X.... ......X.. 

...X..... ...X..... ...X..... ...X..... ...X..... ...X..... ...X..... ...X..... 
.X....... .X....... .X....... .X....... .X....... .X....... .....X... .....X... 
......X.. ......X.. ......X.. .......X. ........X ........X X........ X........ 
..X...... ........X ........X ..X...... ..X...... ....X.... ....X.... ........X 
X........ X........ X........ ........X .....X... X........ .X....... ....X.... 
.......X. ....X.... .......X. ......X.. .......X. .......X. .......X. .......X. 
....X.... .......X. ....X.... ....X.... X........ .....X... ..X...... .X....... 
........X .....X... ..X...... X........ ....X.... ..X...... ......X.. ......X.. 
.....X... ..X...... .....X... .....X... ......X.. ......X.. ........X ..X...... 

...X..... ...X..... ...X..... ...X..... ...X..... ...X..... ...X..... ...X..... 
.....X... .....X... .....X... .....X... .....X... .....X... .....X... .....X... 
X........ ..X...... ..X...... ..X...... .......X. .......X. .......X. .......X. 
........X ........X ........X ........X .X....... .X....... .X....... ..X...... 
......X.. .X....... .X....... ......X.. ....X.... ....X.... ......X.. X........ 
..X...... ....X.... .......X. X........ X........ ......X.. X........ ......X.. 
.......X. .......X. ....X.... .......X. ........X ........X ..X...... ....X.... 
.X....... X........ ......X.. .X....... ......X.. X........ ....X.... .X....... 
....X.... ......X.. X........ ....X.... ..X...... ..X...... ........X ........X 

... to be continued ...

Answer 3

public class Problem {

  public static boolean isSafe(int board[][], int row, int col) {
    int n = board.length;

    //check vertical line
    for(int i=0; i < board.length; i++) {
      if(i == row) continue;
      if(board[i][col] == 1) return false;
    }

    //check horizontal line
    for(int j=0; j < n; j++) {
      if(j == col) continue;
      if(board[row][j] == 1) return false;
    }

    //check north east
    for(int i=row-1, j=col+1; i >=0  && j < n; i--, j++) {
      if(board[i][j] == 1) return false;
    }

    //check south east
    for(int i=row+1, j=col+1; i < n && j < n; i++, j++) {
      if(board[i][j] == 1) return false;
    }

    //check north west
    for(int i=row-1, j=col-1; i >=0 && j >=0; i--,j--) {
      if(board[i][j] == 1) return false;
    }

    //check south west
    for(int i=row+1, j=col-1; i<n && j >=0; i++,j--) {
      if(board[i][j] == 1) return false;
    }

    return true;
  }

  public static boolean nQueen(int board[][], int row) {
    if(row == board.length) return true;

    for(int j=0; j < board.length; j++) {
      if(isSafe(board, row, j)) {
        board[row][j] = 1;

        boolean nextPlacement = nQueen(board, row + 1);
        if(nextPlacement) return true;
        board[row][j] = 0;
      }
    }
    return false;
  }

  public static void displayResult(int board[][]) {
    int n = board.length;
    for(int i=0; i < n; i++) {
      for(int j=0; j < n; j++) {
        System.out.print(board[i][j] + " ");
      }
      System.out.println();
    }
  }

  public static void util(int board[][]) {
    int n = board.length;
    boolean result = nQueen(board, 0);
    if(result) {
      System.out.println(n + " queens can be placed in following arragement");
      displayResult(board);
    }
    else {
      System.out.println("Not possible to place " + n + " queens in " + n + " X " + n + " board");
    }
    System.out.println();
  }

  public static void main(String[] args) {
    util(new int[3][3]);
    util(new int[4][4]);
    util(new int[2][2]);
    util(new int[5][5]);
    util(new int[8][8]);
    util(new int[16][16]);
  }

}