Je travaille sur un programme N reines qui permettra à l'utilisateur de saisir une configuration de la reine en tant que chaîne. Par example,
Lorsque vous y êtes invité, l'utilisateur peut entrer quelque chose comme Q .... Q ..... q..q. Lequel lorsqu'il est affiché comme une carte ressemblerait à: Ce programme est simple en ce qu'il suppose que l'utilisateur entrera des informations valides. J'aimerais avoir la partie principale du programme qui fonctionne avant de revenir en arrière et d'ajouter une manipulation des erreurs. Pour ceux qui ne sont pas familiarisés avec le puzzle N reines, vous avez essentiellement N reines sur un tableau N x N. Vous avez une reine par rangée. Un panneau peuplé est une solution si aucune deux reines ne partage la même rangée, la même rangée, la même colonne ou la même diagonale. J'ai mis en œuvre avec succès des contrôles pour les lignes et les colonnes. Cependant, je suis excité sur la façon dont je peux vérifier toutes les diagonales. Je sais comment vérifier les deux diagonales principales, comme dans Tic Tac Toe, mais je ne peux vraiment pas visualiser comment je peux vérifier toutes les diagonales possibles? Peut-on offrir une aide? Voici mon code: merci
En savoir plus: Besoin d'aide avec N Queens Program
3 Réponses :
Je ne pense pas que vous voulez vérifier toutes les diagonales, mais vous pouvez vérifier toutes les reines. Vous pouvez vérifier si deux reines sont sur la même diagonale en vérifiant les différences entre les rangées et les colonnes des deux QS. Si les différences sont les mêmes, elles sont sur la même diagonale. (Fondamentalement, si la pente de la ligne entre les deux reines est + -1, elles sont sur la même diagonale.)
Par exemple, dites que vous avez deux reines Q1 et Q2. Calculez la valeur absolue des différences dans leurs rangées et de leurs colonnes. si juste faire cela pour toutes les N reines. deltaw == deltacol , les reines sont sur la même diagonale. < / p>
Donc, fondamentalement, ce que vous dites, c'est que je peux stocker la valeur X et Y de chaque reine dans un autre tableau 2D, puis effectuez le chèque que vous avez illustré?
@Will: Oui, stockez simplement les X et Y pour chaque reine et effectuez le chèque de chaque paire.
Vous n'avez pas besoin d'une valeur absolue ici?
@kuhaku oui, définitivement! J'ai mis à jour la réponse. Merci.
Les diagonales peuvent être exprimées sous la forme de y = x + c ou y = c-x. Votre conseil 4x4 aura un total de 10 diagonales, 5 pour chaque équation. Déterminez le C (ils varient en fonction de la taille de la carte) et de la boucle sur X, calculent les y.
Vous devrez vérifier les coordonnées inférieures à zéro, les limites supérieures peuvent être évitées en faisant simplement la carte 2 fois plus grosse (dans chaque direction) comme nécessité - les autres carrés sont toujours vides, alors vérifiez que les vérificateurs ne les causent pas. Dommage.
J'ai même mis en œuvre le problème de N reines sans tableau à tout moment - suivre les lignes, les colonnes et les diagonales. À l'époque, c'était plus rapide car l'addition était beaucoup plus rapide que la multiplication, mais ce n'est plus le cas.
Nous pouvons dire que les reines sont sur la même diagonale si la let donc q1 q1 et q2 être des structures de données tenant les positions X et Y de chaque reine: si (math.abs (pente) = = 1) alors ils sont sur la même diagonale.
Ceci est un peu dangereux, si vous divisez des entiers, vous pourriez obtenir un 1 à partir de 3/2.