La résolution de la n-reine de puzzle
Je viens de résoudre le nqueen problème en python. La solution sorties le nombre total de solutions pour placer n reines sur un échiquier nXn mais en essayant avec n=15 prend plus d'une heure pour obtenir une réponse. Quelqu'un peut-il prendre un coup d'oeil au code et de me donner des conseils sur l'accélération de ce programme...... Un novice en python programmeur.
#!/usr/bin/env python2.7
##############################################################################
# a script to solve the n queen problem in which n queens are to be placed on
# an nxn chess board in a way that none of the n queens is in check by any other
#queen using backtracking'''
##############################################################################
import sys
import time
import array
solution_count = 0
def queen(current_row, num_row, solution_list):
if current_row == num_row:
global solution_count
solution_count = solution_count + 1
else:
current_row += 1
next_moves = gen_nextpos(current_row, solution_list, num_row + 1)
if next_moves:
for move in next_moves:
'''make a move on first legal move of next moves'''
solution_list[current_row] = move
queen(current_row, num_row, solution_list)
'''undo move made'''
solution_list[current_row] = 0
else:
return None
def gen_nextpos(a_row, solution_list, arr_size):
'''function that takes a chess row number, a list of partially completed
placements and the number of rows of the chessboard. It returns a list of
columns in the row which are not under attack from any previously placed
queen.
'''
cand_moves = []
'''check for each column of a_row which is not in check from a previously
placed queen'''
for column in range(1, arr_size):
under_attack = False
for row in range(1, a_row):
'''
solution_list holds the column index for each row of which a
queen has been placed and using the fact that the slope of
diagonals to which a previously placed queen can get to is 1 and
that the vertical positions to which a queen can get to have same
column index, a position is checked for any threating queen
'''
if (abs(a_row - row) == abs(column - solution_list[row])
or solution_list[row] == column):
under_attack = True
break
if not under_attack:
cand_moves.append(column)
return cand_moves
def main():
'''
main is the application which sets up the program for running. It takes an
integer input,N, from the user representing the size of the chessboard and
passes as input,0, N representing the chess board size and a solution list to
hold solutions as they are created.It outputs the number of ways N queens
can be placed on a board of size NxN.
'''
#board_size = [int(x) for x in sys.stdin.readline().split()]
board_size = [15]
board_size = board_size[0]
solution_list = array.array('i', [0]* (board_size + 1))
#solution_list = [0]* (board_size + 1)
queen(0, board_size, solution_list)
print(solution_count)
if __name__ == '__main__':
start_time = time.time()
main()
print(time.time()
Vous vous rendez compte que votre algorithme est O(N!), droit? Il n'y a aucune raison de croire que vous obtiendrez quelque chose de plus qu'un facteur constant pressé d'en sortir.
N'ai pas vérifier, mais le wiki dit il y a 45k solutions pour n = 14. Puisque c'est un expotential augmentation, vous pouvez parier qu'il est encore plus pour n = 15. Que prendre un certain temps, indépendamment de l'algorithme (même avec un algorithme optimal, c'est un problème complexe - et le vôtre est probablement pas optimale). Essayez pour un beaucoup plus petit n (8).
durangobill.com/N_Queens.html contient les numéros de solutions pour N=26.
Dans le cas où certains se poseraient la question, j'ai fait le calcul. Avec la prise de 60m, le temps moyen pour calculer une seule solution correcte avec N=15 (2,279,184 solutions correctes) est 1.579513 mme.
N'ai pas vérifier, mais le wiki dit il y a 45k solutions pour n = 14. Puisque c'est un expotential augmentation, vous pouvez parier qu'il est encore plus pour n = 15. Que prendre un certain temps, indépendamment de l'algorithme (même avec un algorithme optimal, c'est un problème complexe - et le vôtre est probablement pas optimale). Essayez pour un beaucoup plus petit n (8).
durangobill.com/N_Queens.html contient les numéros de solutions pour N=26.
Dans le cas où certains se poseraient la question, j'ai fait le calcul. Avec la prise de 60m, le temps moyen pour calculer une seule solution correcte avec N=15 (2,279,184 solutions correctes) est 1.579513 mme.
OriginalL'auteur | 2011-01-27
Vous devez vous connecter pour publier un commentaire.
La mandature algorithme pour les N-Reines problème est factoriel de l'algorithme dans le pire des cas. Ainsi pour N=8, 8! nombre de solutions sont vérifiées dans le pire des cas, N=9 fait 9!, etc. Comme on peut le voir, le nombre de solutions possibles pousse très grandes, très vite. Si vous ne me croyez pas, allez simplement à l'aide d'une calculatrice et de débuter la multiplication des nombres consécutifs, en commençant à 1. Permettez-moi de savoir à quelle vitesse la calculatrice est à court de mémoire.
Heureusement, pas toutes les solutions possibles doivent être vérifiés. Malheureusement, le nombre de solutions correctes suit toujours à peu près un factorielle modèle de croissance. Ainsi, le temps d'exécution de l'algorithme de croissance factorielle rythme.
Car vous avez besoin de trouver toutes les solutions correctes, il n'y a vraiment pas beaucoup qui peut être fait à propos de la vitesse du programme. Vous avez déjà fait un bon travail dans l'élagage impossible branches de l'arbre de recherche. Je ne pense pas qu'il y a autre chose qui aura un effet majeur. C'est tout simplement une lente algorithme.
OriginalL'auteur cledoux
Le nombre de solutions peut être estimée à l'aide de Donald Knuth de randomisation méthode d'estimation.
À partir de n reines placées le nombre de postes pour la ligne suivante est n.
Choisir au hasard l'une des positions et de calculer le nombre de positions (p) pour la prochaine ligne et plusieurs ce en n et l'enregistrer comme le nombre total de solutions (total = n * p) , puis choisir au hasard l'un de ces postes.
Pour cette ligne, calculer le nombre de positions (p) pour la rangée suivante et mutiple le nombre total de solutions par cette (total *= p). Répétez cette opération jusqu'à ce que le conseil d'administration ne peut pas être résolu, dans ce cas le nombre de solutions est égal à zéro, ou jusqu'à ce que le conseil d'administration est résolu.
Répétez cette opération plusieurs fois, et calculer le nombre moyen de solutions (y compris les zéros). Cela devrait vous donner un moyen rapide et assez bonne approximation du nombre de solutions avec le rapprochement d'améliorer le plus de points que vous faites.
J'espère que cela a un sens 😉
OriginalL'auteur Matt Clarke
Je vous suggère d'oeil à la
test_generators.py
à partir de la source Python pour une alternative de mise en œuvre de la N-Reines problème.OriginalL'auteur tzot
Juste vu cette question. Je voudrais contribuer 2 solutions.
Celle-ci rentre toutes les solutions distinctes
Celle-ci rentre la première solution valable trouvé
Retour est apprécié. Cheers
OriginalL'auteur Olumuyiwa akin-ogundeji
Ci-dessous est mon PYTHON de mise en œuvre. Vous pouvez utiliser PYPY pour plus de vitesse.
Sa vitesse est aidé par l'aide d'un O(1) méthode de calcul en temps pour vérifier si la prochaine reine est attaqué par ceux qui sont déjà placées sur le plateau.
En supposant que le programme est "nqueen.py" un exemple à l'autre il est "python nqueen.py 6", où 6 est la taille d'un 6x6 conseil d'administration.
OriginalL'auteur user5818263
Nous pouvons résoudre les n-reines des algorithmes génétiques. Ce qui est décrit ici https://youtu.be/l6qll5OldHQ, dans l'une des conférences de l'objectif de cours ColumbiaX: CSMM.101x Intelligence Artificielle (IA).
La fonction objectif essaie d'optimiser le nombre de non-attaque paires de reines.
L'animation ci-dessous montre un exemple de solution dans R avec n=20. Plus de détails sur la façon de résoudre des n-reines avec les algorithmes génétiques peuvent être trouvés ici: https://sandipanweb.wordpress.com/2017/03/09/solving-the-n-queen-puzzle-with-genetic-algorithm-in-r/?frame-nonce=76cf9b156a.
OriginalL'auteur Sandipan Dey