btute force

51NQueens.py

# uses Python3
# The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
#
#
#
# Given an integer n, return all distinct solutions to the n-queens puzzle.
#
# Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.'
# both indicate a queen and an empty space respectively.
#
# [
#  [".Q..",  // Solution 1
#   "...Q",
#   "Q...",
#   "..Q."],
#
#  ["..Q.",  // Solution 2
#   "Q...",
#   "...Q",
#   ".Q.."]
# ]
#[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

class Solution (object):
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        FILLER = 0
        import numpy as np
        import itertools
        from functools import reduce

        matrix = np.ones((2*n-1,2*n-1))#(shape=(2*n-1,2*n-1))
        # matrix = np.zeros ((2 * n - 1, 2 * n - 1))  # (shape=(2*n-1,2*n-1))
        allsols = []#([np.zeros(shape=(n,n))] * (n**2))
        matrix [:,n-1] = FILLER
        matrix [n-1,:] = FILLER
        for i in range(n*2-1):
            matrix[i, i] = FILLER
            matrix[n*2-2-i, i] = FILLER
        matrix[n-1,n-1] =  n**2
        # print(matrix)
        for i in range(n):
            for j in range(n):
                allsols.append(2**(n*i+j)*matrix[i:i+n,j:j+n])
        # for i in range(n**2):
        #     print(allsols[i])
        print(reduce(np.dot, allsols))

        print(len(allsols))
        
        
        # Brute force approach
        # intres = [allsols[i] for i in [14,8,7,1]]
        # print(allsols)
        output = []
        matz00 = np.zeros((n,n))
        allcombos = list(itertools.combinations(list(range(n**2)), n))
        for combos in allcombos:
            intres = [allsols[i] for i in combos]
            # intres = [allsols[i] for i in [14, 8, 7, 1]]
            resultmat = matz00.copy()
            for mat in intres:

                resultmat+=mat
                # condition = np.equal(resultmat, n**2) == True
                # print(resultmat)
                state = resultmat[np.where(resultmat==n**2)]
                # if state != np.array([n**2]):
                if len(state)==0:
                    break
                if len(state) == n:
                    solution = []
                    for sol in resultmat:
                        solution.append (''.join (
                            ['Q' if a == n ** 2 else '.' for a in sol]))
                    output.append (solution)
                # print()
                # input()
            # numofones = 0
            # for row in resultmat:
            #     numofones+=list(row).count(n**2)
            # if numofones == n:
            #     # print(combos)
                # print(resultmat,'\n')

            # print(combos, '\n', resultmat)
            # input ()
        return(output)


a = Solution()
print(a.solveNQueens(4))