<jupyter_start><jupyter_text>n-queens  problemhttps://en.wikipedia.org/wiki/Eight_queens_puzzle![Solution](https://upload.wikimedia.org/wikipedia/commons/1/1f/Eight-queens-animation.gif)https://www.geeksforgeeks.org/n-queen-problem-backtracking-3/<jupyter_code># so if we were going to use completely brute force we would need  to look at C(8,64) solutions
# we can use our friend memoized function from last week
import functools
@functools.lru_cache(maxsize=None)
def C_mem(n,k):
    if k == 0: return 1
    if n == 0: return 0
    return C_mem(n-1,k-1) + C_mem(n-1,k)
C_mem(64,8)
# Python3 program to solve N Queen 
# Problem using backtracking 
global N # kind of ugly global state
N = 4

def printSolution(board): 
    for i in range(N): 
        for j in range(N): 
            print (board[i][j], end = " ") 
        print() 

# A utility function to check if a queen can 
# be placed on board[row][col]. Note that this 
# function is called when "col" queens are 
# already placed in columns from 0 to col -1. 
# So we need to check only left side for 
# attacking queens 
def isSafe(board, row, col): 
    # Check this row on left side 
    for i in range(col): 
        if board[row][i] == 1: 
            return False

    # Check upper diagonal on left side 
    for i, j in zip(range(row, -1, -1), 
                    range(col, -1, -1)): 
        if board[i][j] == 1: 
            return False

    # Check lower diagonal on left side 
    for i, j in zip(range(row, N, 1), 
                    range(col, -1, -1)): 
        if board[i][j] == 1: 
            return False

    return True

def solveNQUtil(board, col): 

    # base case: If all queens are placed 
    # then return true 
    if col >= N: 
        return True

    # Consider this column and try placing 
    # this queen in all rows one by one 
    for i in range(N): 

        if isSafe(board, i, col): 

            # Place this queen in board[i][col] 
            board[i][col] = 1

            # recur to place rest of the queens 
            if solveNQUtil(board, col + 1) == True: 
                return True

            # If placing queen in board[i][col 
            # doesn't lead to a solution, then 
            # queen from board[i][col] 
            board[i][col] = 0

    # if the queen can not be placed in any row in 
    # this colum col then return false 
    return False

# This function solves the N Queen problem using 
# Backtracking. It mainly uses solveNQUtil() to 
# solve the problem. It returns false if queens 
# cannot be placed, otherwise return true and 
# placement of queens in the form of 1s. 
# note that there may be more than one 
# solutions, this function prints one of the 
# feasible solutions. 





# This code is contributed by <NAME> 

def solveNQ(board = tuple([0,0,0,0] for n in range(4)), print_board=True): # passing in default 4x4
#     board = [ [0, 0, 0, 0], 
#             [0, 0, 0, 0], 
#             [0, 0, 0, 0], 
#             [0, 0, 0, 0] ] 

    if solveNQUtil(board, 0) == False: 
        #print ("Solution does not exist") 
        return False

    if print_board:
        printSolution(board) 
    return True
# Driver Code 
solveNQ() 
N = 6
[[0]*N for _ in range(N)]
N = 5 # ack global
solveNQ([[0]*N for _ in range(N)])
N = 6 # ack global
solveNQ([[0]*N for _ in range(N)])
N = 7 # ack global
solveNQ([[0]*N for _ in range(N)])
for n in range(4,17):
    N = n
    solveNQ([[0]*N for _ in range(N)])
    print("-"*40)
N = 8 # ack global
solveNQ([[0]*N for _ in range(N)])
N = 8 # ack global
solveNQ([[0]*N for _ in range(N)])
# since we choose our paths deterministically we get the same solution always
# we could flip the board around to get mirror and rotated solutions

board = [[0]*N for _ in range(N)]
board
N = 8
%%timeit
solveNQ([[0]*N for _ in range(N)], print_board=False)
# reason we got a solution does not exist is that we already prefilled the board after first run :)<jupyter_output><empty_output><jupyter_text>Idea - choose path at random among all remaining pathsWe are still going to check all paths (until we find a solution)<jupyter_code>import random
def solveNQUtilRandom(board, col): 

    # base case: If all queens are placed 
    # then return true 
    if col >= N: 
        return True

    # Consider this column and try placing 
    # this queen in all rows one by one 
    for i in random.sample(list(range(N)),k=N): 

        if isSafe(board, i, col): 

            # Place this queen in board[i][col] 
            board[i][col] = 1

            # recur to place rest of the queens 
            if solveNQUtil(board, col + 1) == True: 
                return True

            # If placing queen in board[i][col 
            # doesn't lead to a solution, then 
            # queen from board[i][col] 
            board[i][col] = 0

    # if the queen can not be placed in any row in 
    # this colum col then return false 
    return False

def solveNQRandom(board = tuple([0,0,0,0] for n in range(4)), print_board=True): # passing in default 4x4
#     board = [ [0, 0, 0, 0], 
#             [0, 0, 0, 0], 
#             [0, 0, 0, 0], 
#             [0, 0, 0, 0] ] 

    if solveNQUtilRandom(board, 0) == False: 
        #print ("Solution does not exist") 
        return False

    if print_board:
        printSolution(board) 
    return True
random.choices(list(range(N)),k=N) # no good we got dupes
random.sample(list(range(N)),k=N) # this what we want a random sample of uniques
N = 8
solveNQRandom([[0]*N for _ in range(N)])
N = 8
solveNQRandom([[0]*N for _ in range(N)])
%%timeit
solveNQRandom([[0]*N for _ in range(N)], print_board=False)
# what does it mean that our randomized solution worked faster than hardcoded selection?
# random is about twice as fast in this case
N=10
%%timeit
solveNQRandom([[0]*N for _ in range(N)], print_board=False)
%%timeit
solveNQ([[0]*N for _ in range(N)], print_board=False)
N=16
# with larger Ns random path selection might not be the best anymore
%%timeit
solveNQRandom([[0]*N for _ in range(N)], print_board=False)
%%timeit
solveNQ([[0]*N for _ in range(N)], print_board=False)
# we could try going the other way
list(range(N-1,-1,-1))
list(range(N))
def solveNQUtilReverse(board, col): 

    # base case: If all queens are placed 
    # then return true 
    if col >= N: 
        return True

    # Consider this column and try placing 
    # this queen in all rows one by one 
    # we still want to consider all possible solutions but choosing from other end first
    for i in range(N-1,-1,-1): 

        if isSafe(board, i, col): 

            # Place this queen in board[i][col] 
            board[i][col] = 1

            # recur to place rest of the queens 
            if solveNQUtil(board, col + 1) == True: 
                return True

            # If placing queen in board[i][col 
            # doesn't lead to a solution, then 
            # queen from board[i][col] 
            board[i][col] = 0

    # if the queen can not be placed in any row in 
    # this colum col then return false 
    return False

def solveNQReverse(board = tuple([0,0,0,0] for n in range(4)), print_board=True): # passing in default 4x4
#     board = [ [0, 0, 0, 0], 
#             [0, 0, 0, 0], 
#             [0, 0, 0, 0], 
#             [0, 0, 0, 0] ] 

    if solveNQUtilReverse(board, 0) == False: 
        #print ("Solution does not exist") 
        return False

    if print_board:
        printSolution(board) 
    return True
N=8
solveNQReverse([[0]*N for _ in range(N)])
%%timeit
solveNQReverse([[0]*N for _ in range(N)], print_board=False)
N =8
%%timeit
solveNQReverse([[0]*N for _ in range(N)], print_board=False)
N=10
%%timeit
solveNQReverse([[0]*N for _ in range(N)], print_board=False)
%%timeit
solveNQ([[0]*N for _ in range(N)], print_board=False)
%%timeit
solveNQRandom([[0]*N for _ in range(N)], print_board=False)
N=16
%%timeit
solveNQReverse([[0]*N for _ in range(N)], print_board=False)
%%timeit
solveNQ([[0]*N for _ in range(N)], print_board=False)
%%timeit
solveNQRandom([[0]*N for _ in range(N)], print_board=False)
%%timeit
solveNQRandom([[0]*N for _ in range(N)], print_board=False)
# Branch and Bound approach

""" Python3 program to solve N Queen Problem
using Branch or Bound """
 
N = 8
 
""" A utility function to prsolution """
def printSolutionBB(board):
    for i in range(N):
        for j in range(N):
            print(board[i][j], end = " ")
        print()

""" A Optimized function to check if
a queen can be placed on board[row][col] """
def isSafeBB(row, col, slashCode, backslashCode,
           rowLookup, slashCodeLookup,
                       backslashCodeLookup):
    if (slashCodeLookup[slashCode[row][col]] or
        backslashCodeLookup[backslashCode[row][col]] or
        rowLookup[row]):
        return False
    return True
 
""" A recursive utility function
   to solve N Queen problem """
def solveNQueensUtilBB(board, col, slashCode, backslashCode,
                     rowLookup, slashCodeLookup,
                     backslashCodeLookup):
                         
    """ base case: If all queens are
       placed then return True """
    if(col >= N):
        return True
    for i in range(N):
        if(isSafeBB(i, col, slashCode, backslashCode,
                  rowLookup, slashCodeLookup,
                  backslashCodeLookup)):
                     
            """ Place this queen in board[i][col] """
            board[i][col] = 1
            rowLookup[i] = True
            slashCodeLookup[slashCode[i][col]] = True
            backslashCodeLookup[backslashCode[i][col]] = True
             
            """ recur to place rest of the queens """
            if(solveNQueensUtilBB(board, col + 1,
                                slashCode, backslashCode,
                                rowLookup, slashCodeLookup,
                                backslashCodeLookup)):
                return True
             
            """ If placing queen in board[i][col]
            doesn't lead to a solution,then backtrack """
             
            """ Remove queen from board[i][col] """
            board[i][col] = 0
            rowLookup[i] = False
            slashCodeLookup[slashCode[i][col]] = False
            backslashCodeLookup[backslashCode[i][col]] = False
             
    """ If queen can not be place in any row in
    this colum col then return False """
    return False
 
""" This function solves the N Queen problem using
Branch or Bound. It mainly uses solveNQueensUtil()to
solve the problem. It returns False if queens
cannot be placed,otherwise return True or
prints placement of queens in the form of 1s.
Please note that there may be more than one
solutions,this function prints one of the
feasible solutions."""
def solveNQueensBB(debug=False):
    board = [[0 for i in range(N)]
                for j in range(N)]
     
    # helper matrices
    slashCode = [[0 for i in range(N)]
                    for j in range(N)]
    backslashCode = [[0 for i in range(N)]
                        for j in range(N)]
     
    # arrays to tell us which rows are occupied
    rowLookup = [False] * N
     
    # keep two arrays to tell us
    # which diagonals are occupied
    x = 2 * N - 1
    slashCodeLookup = [False] * x
    backslashCodeLookup = [False] * x
     
    # initialize helper matrices
    for rr in range(N):
        for cc in range(N):
            slashCode[rr][cc] = rr + cc
            backslashCode[rr][cc] = rr - cc + 7
     
    if(solveNQueensUtilBB(board, 0, slashCode, backslashCode,
                        rowLookup, slashCodeLookup,
                        backslashCodeLookup) == False):
        print("Solution does not exist")
        return False
         
    # solution found
    if debug:
        printSolutionBB(board)
    return True
 
# Driver Cde
solveNQueensBB(debug=True)
 
# This code is contributed by SHUBHAMSINGH10
%%timeit
solveNQueensBB()
N = 12
solveNQueens(debug=True)
for n in range(8, 17):
    N = n
    solveNQueens(debug=True)
N=12

%%timeit
solveNQueensBB()
%%timeit
solveNQ([[0]*N for _ in range(N)], print_board=False)
N=16
solveNQ([[0]*N for _ in range(N)])
%%timeit
solveNQ([[0]*N for _ in range(N)], print_board=False)
%%timeit
solveNQueensBB()
N=20
solveNQueensBB(debug=True)
%%timeit
solveNQueensBB()
N=20
solveNQRandom([[0]*N for _ in range(N)])
%%timeit
solveNQRandom([[0]*N for _ in range(N)], print_board=False)<jupyter_output>The slowest run took 101.48 times longer than the fastest. This could mean that an intermediate result is being cached.
5.04 s ± 4.6 s per loop (mean ± std. dev. of 7 runs, 1 loop each)
{'fraction_non_alphanumeric': 0.10881652104845115, 'fraction_numerical': 0.016918189038919777, 'mean_word_length': 2.414971521562246, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 13, 'https://': 3, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '507830', 'license': 'MIT', 'n_tokens_mistral': 4287, 'n_tokens_neox': 3942, 'n_words': 1423, 'path': 'topics/N Queens.ipynb', 'repo_name': 'ValRCS/RTU_Algorithms_DIP321', 'size': '12599'}