N皇后问题的算法

Question

N皇后问题的算法

5

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皇后问题。我认为它可以将两行的前2个皇后放在各自的列中，然后当它遇到第3行的皇后时，由于没有任何皇后需要攻击，所以无法放置，并且将简单地退出算法N皇后...那么这个算法如何实现回溯？

- user2967440

5个回答

1

我刚刚决定用Python语言编写N皇后问题的解决方案。下面是代码，它非常快，可以在几十秒内找到1-8个皇后的所有解决方案，并在几分钟内找到9个皇后的解决方案。它会根据维基百科计算解决方案部分中的参考数字进行测试。

这个解决方案使用递归回溯方法和快速的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 ...

- Arty

0

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]);
  }

}

- Juvenik

0

在这里，我们使用回溯法。其背后的思想是：我们朝着解决方案走一条路径，在不同的决策点上做出选择，如果我们到达了死路（即没有更多的决策点并且我们没有找到正在寻找的解决方案），我们就会回溯——即返回到我们做出决策的最后一个点，并做出不同的选择（如果还有剩余的选择）。

public class nQueens
{

    // Returns the number of solutions found for the n-queens problem.
    public static int solve(int n)
    {
        // We'll place one queen per column. queens[i] will indicate which row the
        // queen from column 'i' occupies.
        int [] queens = new int[n];

        // boolean arrays to keep track of which rows, diagonals,
        // and contradiagonals are already dominated by a queen

        boolean [] used_rows = new boolean[n];
        boolean [] md = new boolean[2 * n];  // main diagonals: \\\

        boolean [] cd = new boolean[2 * n];  // contra-diagonals: ///

        return solve(queens, used_rows, md, cd, 0);
    }


    private static int solve(int [] queens, boolean [] used_rows, boolean [] md, boolean [] cd, int col)
    {
        // Solution is found! So print it out
        if (col == queens.length)
        {
            printSolution(queens);
            return 1;
        }

        // Track the number of solutions found
        int count = 0;

        // Consider placing this queen in each row.
        for (int row = 0; row < queens.length; row++)
        {
            // The formulae for determining which diagonal and contra-
            // diagonal the queen would be occupying. The main diagonals go down
            // and to the right. The contradiagonals go up and to the right.
            int md_index = col + row;
            int cd_index = (col - row) + (queens.length - 1);

            // If this row, diagonal, and contra-diagonal aren't already in use...
            if (!used_rows[row] && !md[md_index] && !cd[cd_index])
            {
                // Place the queen here 
                used_rows[row] = md[md_index] = cd[cd_index] = true;

                // Keep track of which row is occupied by the queen in this column.
                queens[col] = row;

                // Move on to the next column.
                count += solve(queens, used_rows, md, cd, col + 1);

                // As we return, pick up this queen and unmark these positions.
                used_rows[row] = md[md_index] = cd[cd_index] = false;
            }
        }

        // Return the number of solutions we encountered in our recursive calls.
        return count;
    }

    // This prints out the n x n board with '.' in empty spaces and 'Q' wherever
    // there's a queen.
    private static void printSolution(int [] queens)
    {
        System.out.println("Solution:\n");

        for (int row = 0; row < queens.length; row++)
        {
            for (int col = 0; col < queens.length; col++)
                System.out.print((queens[col] == row) ? 'Q' : '.');

            System.out.println();
        }

        System.out.println();
    }

    public static void main(String [] args)
    {
        // If we have a command line argument, use that as 'n'. Otherwise,
        // default to n = 4.
        int n = (args.length < 1) ? 4 : Integer.parseInt(args[0]);
        System.out.println("Number of solutions for " + n + "-queens: " + solve(n));
    }
}

- p_flame

-1

我有代码可以不使用回溯来解决这个问题，但好的一点是，它给出了大O(n)的时间复杂度。

// when n is even...
for(j=1;j<=n/2;j++)
{
    x[j]=2*j;
};
i=1;
for(j=n/2 +1 ;j<=n;j++)
{
    x[j] =i;
    i=(2*i)+1;
}

// when n is odd..
i=0;
for(j=1;j<=(n/2+1);j++)
{
    x[i] = (2*i)+1;
    i++;
}
i=1;
for(j=(n/2+2);j<=n;j++)
{
    x[j] = 2*i;
    i++;
}

这段代码运行良好并给出了一个解决方案，但现在我正在寻求使用此算法获取所有可能的解决方案。

- Rachna Raj

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Bernhard Barker · Accepted Answer

这里的秘密在于递归。

让每个缩进级别表示一级递归。

（实际上不会发生这种情况，因为第三个皇后可以很容易地放置，但要达到实际失败的情况需要更多的编写和/或思考）

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.
      ...

我希望您能从中受益。