''' Created on Feb 4, 2015 @author: Brett Paufler Copyright Brett Paufler Solution to the Eight Queens Problem 'Never get off the boat.' ''' import numpy as np import skimage.io from itertools import permutations #range(1,9) spits out [1,2,3,4,5,6,7,8] #permutations spits out every permutation of same #zipping together gives every possible chessboard combination # with no two pieces in same rank or file boards = [zip(range(1,9),p) for p in permutations(range(1,9))] print len(boards) #40320 print boards[0] #print first possible solution set #Note, rank and file different for each tuple #[(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (7, 7), (8, 8)] def no_diagonals(board): '''given a list of tuples representing a possible solution returns False if any are diagonally aligned, True otherwise ''' for x,y in board: for r in (range(-7,0,1) + range(1,8,1)): if (x+r,y+r) in board: return False elif (x-r,y+r) in board: return False return True #And this is the solution #Take the first list with no overlapping rank and files #And filter with no_diagonals() boards = [b for b in boards if no_diagonals(b)] print len(boards) #92, which is the correct number of answers print boards[0] #A sample solution set #[(1, 1), (2, 5), (3, 8), (4, 6), (5, 3), (6, 7), (7, 2), (8, 4)] def print_board(board): b_board = "-" * 64 for (x,y)in board: #for x,y in b: z = (x-1)*8 + y-1 b_board = b_board[:z] + 'X' + b_board[z+1:] for r in range(0,8): print b_board[r*8:r*8+8] #print board return board print_board(boards[0]) def board_image(board): '''standard board graphic ''' #holding array, 1 being white in grayscale bI = np.ones((100,100), dtype=float) #these are the board grid lines for x in range(10,100,10): bI[x,10:90] = 0.0 bI[10:90,x] = 0.0 #these are the squares for (x,y)in board: bI[x*10:x*10+10,y*10:y*10+10] = 0.0 print bI #debug skimage.io.imsave("eight_queens.png", bI) #save png return bI #return for next funtion def all_boards_image(boards): '''standard boards, full array ''' #make array with full 92 solution set #precomposed into image arrays images = [] for b in boards: images.append(board_image(b)) #arrange the img solution sets #into a 23x4 grid img = np.vstack((np.hstack(images[0:23]), np.hstack(images[23:46]), np.hstack(images[46:69]), np.hstack(images[69:92]))) #save the solution set as an image skimage.io.imsave("eight_queens.png",img) #board_image(boards[0]) def custom_board_image(board, b_type=0): '''standard board graphic ''' bI = np.ones((100,100), dtype=float) #these are the board grid lines if b_type == 0: for x in range(10,100,10): bI[x,10:90] = 0.0 bI[10:90,x] = 0.0 if b_type == 1 or b_type==3: a,b = board[0] for (x,y) in board[1:]: if b < y: #b,y = y,b bI[x*10,b*10:y*10] = 0.0 else: bI[x*10,y*10:(b+1)*10] = 0.0 a,b = x,y if b_type == 2 or b_type==3: #board = [(b,a) for a,b in board] board.sort(key=lambda x: x[1]) a,b = board[0] for (x,y) in board[1:]: if a < x: bI[(a)*10:(x+1)*10,y*10] = 0.0 else: bI[(x)*10:(a+1)*10,y*10] = 0.0 a,b = x,y for (x,y)in board: bI[x*10:x*10+10,y*10:y*10+10] = 0.0 print bI skimage.io.imsave("eight_queens.png", bI) return bI def custom_boards_image(boards): '''standard boards, full array ''' images = [] for c,b in enumerate(boards): images.append(custom_board_image(b, c/23)) img = np.vstack((np.hstack(images[0:23]), np.hstack(images[23:46]), np.hstack(images[46:69]), np.hstack(images[69:92]))) skimage.io.imsave("eight_queens.png",img) #custom_boards_image(boards) #46 2, 23 4, 12 8,