I've recently solved the famous N-Queens problem: Can you place \$N\$ chess queens on a \$N × N\$ board in such a way that no one attacks another queen? The idea here is based on the ideas from several blogposts describing a bitwise approach - approaching the board row by row, keeping track of bits of 3 numbers - columns, major and minor diagonals: ``` class Solution(object): def totalNQueens(self, n): all_ones = 2 ** n - 1 def helper(ld, column, rd, count=0): if column == all_ones: # filled out all vacant positions return 1 possible_slots = ~(ld | column | rd) # mark possible vacant slots as 1s while possible_slots & all_ones: current_bit = possible_slots & -possible_slots # get first 1 from the right possible_slots -= current_bit # occupy a slot # mark conflicts in the next row next_column_bit = column | current_bit next_rd_bit = (rd | current_bit) > 1 count += helper(next_ld_bit, next_column_bit, next_rd_bit) return count return helper(0, 0, 0) ``` The solution was accepted by the LeetCode OJ and actually beats 98.97% of Python solutions. But, can we optimize it even further? What would you improve code-quality/readability wise? Another follow-up concern is that I don't see an easy way for this problem to instead of counting possible board arrangements, collect all possible distinct board configurations.

I created a recursive, optimized, N-Queens implementation in CPP. Any suggestions for improvement? ``` /* * Filename : queens.cpp * Author : Kevin F. * License : CopyLeft, Feb 2017 * Eight Queens : Print solutions which have N non-attacking queens placed on NxN chess board * Input : Adjust BOARD_SIZE to change the size of the N * Output : ASCII printed board and runtime statistics * Requires : C++11 * Compilation : g++ -std=c++11 -O3 -o queens queens.cpp * Source : http://pastebin.com/qy483BEi * Speed : Found: 92 solutions in: 0.002582 seconds using: 2747 recursions * Without Opt : Found: 92 solutions in: 0.132239 seconds using: 139049 recursions */ #include #include #include #define BOARD_SIZE 8 using namespace std; struct queen_t { uint8_t x; uint8_t y; }; static vector > _boards; static uint32_t _num_recursions; /* Forward declare for validate_and_continue */ void recurse(vector *board, set *avail_x, set *avail_y, uint16_t cur_iteration); void print_board(vector *board){ /* Sample Output * |12345678 * 1|xxxxxQxx * 2|xxxQxxxx * 3|xxxxxxQx * 4|Qxxxxxxx * 5|xxxxxxxQ * 6|xQxxxxxx * 7|xxxxQxxx * 8|xxQxxxxx */ /* Generate empty board */ vector rows = {" |"}; for(int i=1; i begin(), board->end(), [&](const queen_t queen){ rows[queen.y].replace(queen.x+1, 1, "Q"); // +1 to skip #| }); for(int i=0; i x == 0 || second_queen->x == 0){ return false; } return abs(second_queen->y - first_queen->y) == abs(second_queen->x - first_queen->x); } /* Return true when new queen(s) trigger a diagonal attack */ bool can_attack(const vector *board, const queen_t *first_queen, const queen_t *second_queen){ for(const queen_t &queen : *board){ if (diagonal_slope(first_queen, &queen) == true || diagonal_slope(&queen, second_queen) == true){ return true;

I was learning backtracking algorithms earlier today, and was excited and wrote this code for n-Queens problem. Being my first try at backtracking algorithms, I would appreciate if you guys could chip in some suggestions/flaws in my code. Also, I had a really tough time getting this to work - I struggled mainly in trying to debug so many recursive calls and often got lost in analyzing which ones were waiting for "return value" from the other deeper function calls. — any help on how to get started/thinking about recursion while writing code would be very helpful. ``` package com.komal.backtracking; import java.util.concurrent.TimeUnit; public class Nqueens { static boolean[][] chessBoard; static int size; static int boundary; public void initChessBoard() { chessBoard = new boolean[size][size]; boundary = size - 1; } static int noOfBacktrackCalls; public static void main(String[] args) { size = 8; Nqueens nQueens = new Nqueens(); nQueens.initChessBoard(); long startTime = System.nanoTime(); if (!nQueens.backTrackRoutine(0, 0)) { System.out.println("Cannot be solved!!"); } for (boolean[] i : chessBoard) { System.out.print("\n{"); for (boolean i1 : i) { System.out.print(i1 + ","); } System.out.print("}"); } long timeTaken = TimeUnit.NANOSECONDS.toMillis(System.nanoTime() - startTime); System.out.println("\nCompleted in :" + timeTaken + " milli sec"); System.out.println("\nTook " + noOfBacktrackCalls + " backtrack calls for completion!"); } public boolean backTrackRoutine(int row, int col) { noOfBacktrackCalls++; boolean flag = true; if (col == size || row == size) { return false; } if (canPlace(row, col)) { System.out.println("Placing queen at Row- " + row + " , col-" + col);

I want to increase the efficiency and reduce the time complexity for the n-queen problem in n*n matrix chess. I am able to run only still (11*11) in normal time otherwise for the big number it is taking much more time. How can I improve performance? ``` import time start_time = time.time() def queensproblem(rows, columns): solutions = [[]] for row in range(rows): solutions = add_one_queen(row, columns, solutions) return solutions def add_one_queen(new_row, columns, prev_solutions): return [solution + [new_column] for solution in prev_solutions for new_column in range(columns) if no_conflict(new_row, new_column, solution)] def no_conflict(new_row, new_column, solution): return all(solution[row] != new_column and solution[row] + row != new_column + new_row and solution[row] - row != new_column - new_row for row in range(new_row)) count = 0 r = input("Enter number of ROWS for Chess/Matrix: ") c = input("Enter number of COLUMNS for Chess/Matrix: ") for solution in queensproblem(int(r), int(c)): count += 1 print(solution) print("\n Total number of solution is: ", count) print("--- Time: %s seconds ---" % (time.time() - start_time)) ``` Output For a 4x4 matrix `Enter number of ROWS for Chess/Matrix: 4 Enter number of COLUMNS for Chess/Matrix: 4 [1, 3, 0, 2] [2, 0, 3, 1] Total number of solution is: 2 --- Time: 2.3161020278930664 seconds --- ` For a 12x12 matrix `Enter number of ROWS for Chess/Matrix: 12 Enter number of COLUMNS for Chess/Matrix: 12 [0, 2, 4, 7, 9, 11, 5, 10, 1, 6, 8, 3] [0, 2, 4, 9, 7, 10, 1, 11, 5, 8, 6, 3] Total number of solution is: 14200 --- Time: 29.522358894348145 seconds --- `

I wrote a Haskell program to solve the N-queens problem by bruteforce. It works and I find it reasonably readable But it is pretty slow: - 5 seconds for one solution of 8 queens. - 1 minute for one solution for 9 queens. - Crash for 10 queens. I fear that `allFalseOneTrue` gives memory problems as it uses permutations. I would like to hear both improvements on readability and performance: ``` import Control.Monad import Data.List -- True indicates that there is a queen, False that there is not. type QueenBoard = [[Bool]] count :: Eq a => a -> [a] -> Int count x = length . filter (==x) fAnd :: (a -> Bool) -> (a -> Bool) -> (a -> Bool) fAnd = liftM2 (&&) rotate90 :: [[a]] -> [[a]] rotate90 = map reverse . transpose noQueensinSameRow :: QueenBoard -> Bool noQueensinSameRow board = not (any (\row -> count True row > 1) board) noQueensinSameColumn :: QueenBoard -> Bool noQueensinSameColumn = noQueensinSameRow . rotate90 -- Attribution to http://stackoverflow.com/questions/32465776/getting-all-the-diagonals-of-a-matrix-in-haskell diagonals :: [[a]] -> [[a]] diagonals [] = [] diagonals ([]:xss) = xss diagonals xss = zipWith (++) (map ((:[]) . head) xss ++ repeat []) ([]:(diagonals (map tail xss))) allDiagonals :: [[a]] -> [[a]] allDiagonals xss = (diagonals xss) ++ (diagonals (rotate90 xss)) noQueensinSameDiagonal :: QueenBoard -> Bool noQueensinSameDiagonal = noQueensinSameRow . allDiagonals isQueenSolution :: QueenBoard -> Bool isQueenSolution = (noQueensinSameRow `fAnd` noQueensinSameColumn `fAnd` noQueensinSameDiagonal) allFalseOneTrue :: Int -> [[Bool]] allFalseOneTrue length = nub $ permutations ( [True] ++ (replicate (length - 1) False) ) allProduct = sequence :: [[a]] -> [[a]] allPossibleBoards :: Int -> [QueenBoard] allPossibleBoards size = allProduct (replicate size (allFalseOneTrue size)) solveQueens :: Int -> [QueenBoard] solveQueens = (filter isQueenSolution) . allPossibleBoards main :: IO()

I coded a linear (without threads) app, which looks ok and has normal solving speed. Also, I coded a multithreaded app, and it is ok when I use 2 processors and 2 threads. It is also fine when I use 4 processors and 4 threads. But when I try to solve with 6 processors and 6 threads, I am not satisfied with the solving speed. How can I make it faster? Main.java: ``` import java.util.Scanner; public class Main { public static void main(String[] args) throws InterruptedException { // TODO Auto-generated method stub //Scanner scanner = new Scanner(System.in); //System.out.println("Iveskite N:"); //int n = Integer.parseInt(scanner.nextLine()); int n = Integer.parseInt(args[0]); int maxThreads = Integer.parseInt(args[1]); Karalienes.setMaxGSK(maxThreads); Karalienes queens = new Karalienes(n, 1, new int[n+1]); long startedTime = System.currentTimeMillis(); queens.start(); queens.join(); System.out.println("Solutions: "+Karalienes.getVariantuSkaiciu()); //queens.print(); System.out.println("Working time: "+(float)(System.currentTimeMillis()-startedTime)/1000 + " s."); } } ``` Karalienes.java: ``` import java.util.Stack; public class Karalienes extends Thread { private int n; private int places[]; private int column; private static Integer solutions = new Integer(0); private static Integer startedThreads = 0; private static int maxThreads; private Stack stack; public Karalienes(int n,int column, int places[]) { this.n = n; this.column = column; this.places = places; stack = new Stack(); } public static void setMaxGSK(int sk) { this.maxThreads = sk; } private boolean arOk(int row, int column) { boolean ok = true; int tmpColumn = column-1; for(; tmpColumn>=1; tmpColumn--) { if ((places[tmpColumn]-row)==0) {

Figure 2.8: A solution to the eight-queens puzzle. The ``eight-queens puzzle'' asks how to place eight queens on a chessboard so that no queen is in check from any other (i.e., no two queens are in the same row, column, or diagonal). One possible solution is shown in figure 2.8. One way to solve the puzzle is to work across the board, placing a queen in each column. Once we have placed k - 1 queens, we must place the kth queen in a position where it does not check any of the queens already on the board. We can formulate this approach recursively: Assume that we have already generated the sequence of all possible ways to place k - 1 queens in the first k - 1 columns of the board. For each of these ways, generate an extended set of positions by placing a queen in each row of the kth column. Now filter these, keeping only the positions for which the queen in the kth column is safe with respect to the other queens. This produces the sequence of all ways to place k queens in the first k columns. By continuing this process, we will produce not only one solution, but all solutions to the puzzle. We implement this solution as a procedure queens, which returns a sequence of all solutions to the problem of placing n queens on an n× n chessboard. Queens has an internal procedure queen-cols that returns the sequence of all ways to place queens in the first k columns of the board. ``` (define (queens board-size) (define (queen-cols k) (if (= k 0) (list empty-board) (filter (lambda (positions) (safe? k positions)) (flatmap (lambda (rest-of-queens) (map (lambda (new-row) (adjoin-position new-row k rest-of-queens)) (enumerate-interval 1 board-size))) (queen-cols (- k 1)))))) (queen-cols board-size)) ``` In this procedure rest-of-queens is a way to place k - 1 queens in the first k - 1 co