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 皇后......那么这个算法是如何实现回溯的呢？

4

5 回答 5

6

这里的秘密是递归。

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

（实际上不会发生什么，因为第三个皇后很容易被放置，但它只是需要更多的写作和/或思考才能找到一个实际上会失败的案例）

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

我希望这会有所帮助。

于 2013-11-15T09:56:30.813 回答
1

我刚刚决定用Python语言编写我的N Queens Puzzle解决方案，下面是代码，它非常快，在几十秒内找到 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 ...
于 2020-09-29T06:26:17.893 回答
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]);
  }

}
于 2019-05-06T16:29:44.580 回答
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));
    }
}
于 2019-12-08T18:07:31.600 回答
-1

我有没有使用回溯的代码，但好的是，它给出了 big-oh(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++;
}

该代码运行良好并提供了一个解决方案，但现在我正在寻找使用该算法获得所有可能的解决方案。

于 2017-10-25T10:52:09.793 回答