Ce problème me rend fou ... Placer N évêques sur le tableau NxN d'une manière, où tous les carrés seraient occupés ou attaqués avec au moins un d'entre eux.Backtracking: N Bishops Problème
Quelqu'un pourrait-il m'aider avec un algorithme pour résoudre ce problème?
Pourquoi faire marche arrière? Utilisez le petit nombre de solutions pour obtenir une preuve.
Même un algorithme glouton suffira: Comptez le nombre de carrés accessibles à partir de chaque carré. Choisissez un carré ayant la plus grande portée qui ne chevauche pas une portée précédemment sélectionnée. Répéter.
L'ambiguïté génère des variations horizontales, verticales et latérales. N évêques est seulement suffisant pour atteindre chaque carré avec exactement un évêque. Si vous avez sélectionné des carrés dont la portée se chevauchait, le décompte final des carrés accessibles serait inférieur. Hmm, peut-être que vous avez besoin de quantifier combien plus faible pour un mauvais carré donné. Ça peut être faisable.
Pour un espace de problème aussi important, le retour arrière en force brute ne semble pas prometteur.
J'ai commencé à écrire cet algorithme avec retour en arrière ... Et je pensais qu'il n'y avait pas de meilleure façon . Mais j'aime ton idée! Je vais essayer de l'implémenter. Mais avant cela, le "nombre de cases atteignables" est, essentiellement, le nombre de cases pouvant être attaquées depuis un certain carré, n'est-ce pas? – Cinnamon
@Cinnamon: oui. – Potatoswatter
_ _ _ _ ♗ _ _ _ _ _ _ _ _ ♗ _ _ _ _ _ _ _ _ ♗ _ _ _ _ _ _ _ _ ♗ _ _ _ _ _ _ _ _ ♗ _ _ _ _ _ _ _ _ ♗ _ _ _ _ _ _ _ _ ♗ _ _ _ _ _ _ _ _ ♗ _ _ _ _ _ _ _ _ ♗ _ _ _ _
Le mot «backtracking» suggère que l'OP veut _all_ les arrangements possibles d'évêque. – Vlad
Je connais la solution. J'ai besoin d'aide avec l'algorithme. – Cinnamon
@Cinnamon: L'algorithme - 1) Choisissez n'importe quelle ligne ou colonne. 2) Placez les évêques dans chaque cellule de cette rangée ou colonne. Sérieusement, si ce n'est pas ce que vous voulez, il serait utile si vous avez ajouté un peu plus de détails à votre question. Expliquez: ce que vous voulez, comment et pourquoi le backtracking devrait être utilisé, ce que vous avez essayé, votre code le cas échéant, et les problèmes que vous rencontrez pour le faire fonctionner. –
Il existe une solution minimale et maximale pour ce problème ce n'est pas aussi trivial.
Cochez cette BishopsProblem ou plus detailed
Je suis sûr que vous trouverez facilement un exemple dans c.
Je suppose que vous demandez des optimisations, car l'algorithme de retour arrière est ce qu'il est.
Première chose à remarquer est que vous pouvez séparer le noir et blanc - vous prenez la somme de B_i * W_j où i + j = N. Vous pouvez également visualiser les diagonales sous la forme d'une simple grille (avec des contraintes) car cela rendra le code plus clair et peut-être plus facile à comprendre. Une autre optimisation est de noter que la couleur n'a pas nécessairement d'importance - les résultats pour certains noirs peuvent être utilisés pour certains blancs. Déterminez quand cela arrive et quand ce n'est pas le cas.
Espérons que ceci est un assez bon coup de pouce - devrait être suffisant pour certains N smallish.
Je suis sûr que quelqu'un peut vous aider; où, exactement, êtes-vous coincé? –
Pourquoi ne pas faire marche arrière? :-P – Vlad
Eh bien ... Il y a un problème similaire avec les reines, mais tout ce que vous avez à faire avec elles est de vérifier si la reine en cours de placement est placée sur une case légale. Mais avec les évêques, devez-vous être conscient des carrés vides tout au long de l'algorithme? C'est très inefficace, n'est-ce pas? Comme vous avez besoin de "redessiner" le tableau après avoir placé/enlevé chaque évêque. – Cinnamon