質問 

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

The above code is for solving N Queens problem using backtracking.I think that it can place the first 2 queens of two rows in respective columns and then when it comes to 3rd row queen it can't be placed as no queen needs to be attacking and it will simply exit from Algorithm N queens...So how is this algorithm implements backtracking?

役に立ちましたか？

解決

The secret here is the recursion.

Let each level of indentation below indicate a level of recursion.

(not what will actually happen, as the third queen can easily be placed, but it just would've taken quite a bit more writing and/or thinking to get to a case that will actually fail)

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

Something more in line with what the code actually does: (still not what will actually happen)

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

I hope that helps.

他のヒント

I've just decided to code my solution of N Queens Puzzle in Python language, down below is code, it is quite fast, in dozens of seconds it finds all solutions for 1-8 queens and in few minutes for 9 queens. It tests agains reference numbers in Counting Solutions section of wiki.

Solution uses recursive back-tracking approach and fast numpy library, also it searches solutions only in lexicographical order of combinations, all permutations of queens in same positions are considered to be same and all permutations except first are not searched at all. So algorithm is quite fast.

Try it online!

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()

It outputs:

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

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

}

Here, we use backtracking. The idea behind it: we take a path towards a solution, making choices at different decision points as we go, and if we reach a dead-end (where there are no more decision points and we haven't found the solution we're looking for), we backtrack -- i.e., go back to the last point where we made a decision, and make a different choice (if there are any remaining). 

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

I have code for this without using backtracking, but the nice thing is, it is giving time complexity of 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++;
}

This code works well and gives one solution, but now I am in search of getting all possible solutions using this algorithm.

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top