<commit_before>#!/usr/bin/python
# -*- coding: utf-8 -*-
"""
    Solve the N queens problem http://en.wikipedia.org/wiki/Eight_queens_puzzle
    using naive constraint propagation.
    
    Usage: 
        python n_queens.py <N>
    e.g.
        python .n_queens.py 20
        
    NOTES:
        1 Uses NumPy and Numba so the best way to run this is to get the latest Anaconda disto
          from https://store.continuum.io/
        2 If you don't want to use Numba then remove the @autojit. 
        3 If you don't want to even use Numpy then make board a list of lists.
        4 This program only works for N with value up to about 900 (on Windows 64 bit) due to 
          stack size limitations in python. If you want to solve for large values of N then convert
          add_queen() from a recursive to an iterative function.
        5 Alternative solutions include
            Local search http://en.wikipedia.org/wiki/Min-conflicts_algorithm#Example
            MIP: http://scip.zib.de/download/files/scip_intro_01.pdf 
            A solver: e.g Comet: http://www.hakank.org/comet/queensn.co
"""
from __future__ import division
import numpy as np
import sys, random
from numba import autojit


def make_board(N):
    """Create a N x N chessboard
        Returns: An N X N integer NumPy array
    """    
    return np.zeros((N, N), dtype=np.int)
    

@autojit
def propagate(N, board, x, y, d):
    """Propagate the constraints that arise from adding (d = +1) or removing (d = -1) a queen to the 
        board at (x, y)
        
        N: Width of chessboard
        board: State of chessboard for current queens which does not include the one at (x, y). 
               board[a, b] = 1 if (a, b) is threatened by any of the queens
               board will be updated to inclue the queen at (x, y) when this function returns
        x, y: Coordinates of queen to be added/removed
        d: +1 to add a queen, -1 to remove a queen
    """

    # Add d to the elements in the column and row that intersect (x, y) including (x, y)
    board[x, :] += d
    board[:, y] += d
    board[x, y] -= d

    # Add d to the elements in the diagonals that intersect (x, y) excluding (x, y)
    # This looks at a bit funny because of the current limitations of Numba but this is the 
    #  inner loop of this script so we put up with the odd looking code for the speed.
    x1 = x - 1
    y1 = y - 1
    x2 = x + 1
    y2 = y - 1
    x3 = x - 1
    y3 = y + 1
    x4 = x + 1
    y4 = y + 1       

    while x1 >= 0 and y1 >= 0:
        board[x1, y1] += d
        x1 -= 1
        y1 -= 1    

    while x2 < N and y2 >= 0:
        board[x2, y2] += d
        x2 += 1
        y2 -= 1
      
    while x3 >= 0 and y3 < N:
        board[x3, y3] += d
        x3 -= 1
        y3 += 1 
   
    while x4 < N and y4 < N:
        board[x4, y4] += d
        x4 += 1
        y4 += 1     


def add_queen(N, queens, board):
    """Add a queen to board
        Board is filled from left column to right.
        This function called recursively. 
        It gets called with a valid list of queens and attempts to add one more queen. 
        
        N: Width of chessboard
        queens: List of queens that have been placed so far. queens[i] = row of queen on column i
        board: State of chessboard. board[x, y] = 1 if (x, y) is threatened by any of queens
        Returns: Valid list of N queens if one has been found, None otherwise
        
        Note: board gets modified then restored to its state at entry to this function.
    """
    # The queens are valid by design. If there are N of them so we must have a full solution.
    if len(queens) == N:
        return queens

    # Checking rows in random order makes this run fast
    row_order = list(range(N))
    random.shuffle(row_order) 
    
    x = len(queens)
    for y in row_order:
        # Don't check threatened positions. The efficiency of this program is basically due to the
        # pruning of the search space that results from this.
        if board[x, y] != 0:
            continue
        
        # Add the contraints for the new queen at (x, y)
        propagate(N, board, x, y, 1)
        # Recurse
        valid_queens = add_queen(N, queens + [y], board)
        # Undo the constraints added for queen at x, y
        propagate(N, board, x, y, -1)
        
        # If we found a valid board deeper in the recursion just return it.
        if valid_queens:
            return valid_queens
            
    # If we got here then queens could be not be extended to a valid N queens list 
    return None
    
    
def solve(N):
    """Solve the N queens problem with constraint propagation
        queens = solve(N) => queens[i] is the row of the queen in column i
                           where 0 <= row < N and 0 <= column < N
        Returns: List of rows for queens. 
    """
    return add_queen(N, [], make_board(N))

    
if __name__ == '__main__':    
    if len(sys.argv) != 2:
        print __doc__
        exit()
        
    N = int(sys.argv[1])
    print 'Solving %d queens problem' % N
    
    queens = solve(N)
    <commit_msg>comments<commit_after>#!/usr/bin/python
# -*- coding: utf-8 -*-
"""
    Solve the N queens problem http://en.wikipedia.org/wiki/Eight_queens_puzzle
    using naive constraint propagation.
    
    Usage: 
        python n_queens.py <N>
    e.g.
        python .n_queens.py 20
        
    NOTES:
        1 Uses NumPy and Numba so the best way to run this is to get the latest Anaconda distro
          from https://store.continuum.io/
        2 If you don't want to use Numba then remove the @autojit. 
        3 If you don't even want to use Numpy then make board a list of lists.
        4 This program only works for N with values up to about 900 (on Windows 64 bit) due to 
          stack size limitations in python. If you want to solve for largee values of N then convert
          add_queen() from a recursive to an iterative function.
        5 Alternative methods for solving N queens include
            Local search http://en.wikipedia.org/wiki/Min-conflicts_algorithm#Example
            MIP: http://scip.zib.de/download/files/scip_intro_01.pdf 
            A solver: e.g Comet: http://www.hakank.org/comet/queensn.co
"""
from __future__ import division
import numpy as np
import sys, random
from numba import autojit


def make_board(N):
    """Create a N x N chessboard
        Returns: An N X N integer NumPy array
    """    
    return np.zeros((N, N), dtype=np.int)
    

@autojit
def propagate(N, board, x, y, d):
    """Propagate the constraints that arise from adding (d = +1) or removing (d = -1) a queen to the 
        board at (x, y)
        
        N: Width of chessboard
        board: State of chessboard for current queens which does not include the one at (x, y). 
               board[a, b] > 0 if (a, b) is threatened by any of the queens, == 0 otherwise
               board will be updated to include the queen at (x, y) when this function returns
        x, y: Coordinates of queen to be added/removed
        d: +1 to add a queen, -1 to remove a queen
    """

    # Add d to the elements in the column and row that intersect (x, y) including (x, y)
    board[x, :] += d
    board[:, y] += d
    board[x, y] -= d

    # Add d to the elements in the diagonals that intersect (x, y) excluding (x, y)
    # This looks at a bit funny because of the current limitations of Numba but this is the 
    #  inner loop of this script so we put up with the odd looking code for the speed.
    x1 = x - 1
    y1 = y - 1
    x2 = x + 1
    y2 = y - 1
    x3 = x - 1
    y3 = y + 1
    x4 = x + 1
    y4 = y + 1       

    while x1 >= 0 and y1 >= 0:
        board[x1, y1] += d
        x1 -= 1
        y1 -= 1    

    while x2 < N and y2 >= 0:
        board[x2, y2] += d
        x2 += 1
        y2 -= 1
      
    while x3 >= 0 and y3 < N:
        board[x3, y3] += d
        x3 -= 1
        y3 += 1 
   
    while x4 < N and y4 < N:
        board[x4, y4] += d
        x4 += 1
        y4 += 1     


def add_queen(N, queens, board):
    """Add a queen to the column to right of the queens that have been placed on the board so far.
        Queens are added from left column to right. 
        This function gets called recursively with a valid list of queens and attempts to add one 
        more queen immediately the right of those in the list.
        It only gets called if queens are all in feasible positions (i.e. not threatened by each
        other)
        
        N: Width of chessboard
        queens: List of queens that have been placed so far. queens[i] = row of queen on column i
        board: State of chessboard. board[x, y] = 1 if (x, y) is threatened by any of queens
        Returns: Valid list of N queens if one has been found, None otherwise
        
        Note: board gets modified then restored to its state at entry to this function.
    """
    # The queens are in feasible locations by design. If there are N of them so we must have a full 
    #  solution so we return it.
    if len(queens) == N:
        return queens

    # Checking rows in random order makes this run faster. Why?
    row_order = list(range(N))
    random.shuffle(row_order) 
    
    x = len(queens)
    for y in row_order:
        # Don't check threatened positions. The efficiency of this program is basically due to the
        #  pruning of the search space that results from this.
        if board[x, y] != 0:
            continue
        
        # Add the contraints for the new queen at (x, y)
        propagate(N, board, x, y, 1)
        # Recurse
        valid_queens = add_queen(N, queens + [y], board)
        # Undo the constraints added for queen at x, y
        propagate(N, board, x, y, -1)
        
        # If we found a feasible full board deeper in the recursion then return it.
        if valid_queens:
            return valid_queens
            
    # If we got here then queens could be not be extended to a feasible N queens list 
    return None
    
    
def solve(N):
    """Solve the N queens problem with constraint propagation
        queens = solve(N) => queens[i] is the row of the queen in column i
                           where 0 <= row < N and 0 <= column < N
        Returns: List of rows for queens. 
    """
    return add_queen(N, [], make_board(N))

    
if __name__ == '__main__':    
    if len(sys.argv) != 2:
        print __doc__
        exit()
        
    N = int(sys.argv[1])
    print 'Solving %d queens problem' % N
    
    queens = solve(N)
    
{'fraction_non_alphanumeric': 0.07902217168845935, 'fraction_numerical': 0.015254879666477166, 'mean_word_length': 1.8989288656962373, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 16, 'https://': 2, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5340810', 'n_tokens_mistral': 3374, 'n_tokens_neox': 3196, 'n_words': 1470}