A jouer aux reines avec une calculette de presque 40 ans !
Modérateur : Politburo
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3419
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: A jouer aux reines avec une calculette de presque 40 ans !
Sympa ce code.
Et oui, je réalise que dans l'article il s'agit bien d'une Ti-58 et non d'une Ti-58C ce qui serait une bonne explication pour la différence de vitesse. Il peut y avoir de variation entre les machines d'une même époque ou entre des machines issues de séries différente (éloignées dans le temps ou ayant profiter d'avancée technique ou modification des circuits), mais pas d'un ratio aussi élevé.
Concernant la vitesse sur fx-602p, il y a peut-être quelque choix d'organisation du code ou sens d'un test qui expliquerait une différence du rendement. Ce n'est pas toujours évident de concevoir au plus rapide. Parfois une solution que l'on trouve efficace ne l'est pas tant que ça, voir parfois une astuce est un faux ami.
J'attends avec impatience la version pour l'Amstrad CPC. Elle me donnera peut-être l'envie de faire pour Commodore C128D avec graphique et language machine.
Et oui, je réalise que dans l'article il s'agit bien d'une Ti-58 et non d'une Ti-58C ce qui serait une bonne explication pour la différence de vitesse. Il peut y avoir de variation entre les machines d'une même époque ou entre des machines issues de séries différente (éloignées dans le temps ou ayant profiter d'avancée technique ou modification des circuits), mais pas d'un ratio aussi élevé.
Concernant la vitesse sur fx-602p, il y a peut-être quelque choix d'organisation du code ou sens d'un test qui expliquerait une différence du rendement. Ce n'est pas toujours évident de concevoir au plus rapide. Parfois une solution que l'on trouve efficace ne l'est pas tant que ça, voir parfois une astuce est un faux ami.
J'attends avec impatience la version pour l'Amstrad CPC. Elle me donnera peut-être l'envie de faire pour Commodore C128D avec graphique et language machine.
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Re: A jouer aux reines avec une calculette de presque 40 ans !
J’ai édité le code du msg précédent pour résoudre toute taille d’echiquier.C.Ret a écrit : ↑14 août 2022 11:28
Concernant la vitesse sur fx-602p, il y a peut-être quelque choix d'organisation du code ou sens d'un test qui expliquerait une différence du rendement. Ce n'est pas toujours évident de concevoir au plus rapide. Parfois une solution que l'on trouve efficace ne l'est pas tant que ça, voir parfois une astuce est un faux ami.
Pour optimiser la vitesse sur 602 il y a un truc utile à savoir. Un GOTO cherche toujours son label en « montant » vers le haut du code, si il ne trouve pas il repart du GOTO et cherche vers le bas. J’ai gagné 45 secondes pour la première solution 8x8 en prenant ça en compte et en adaptant le code.
A noter aussi les séquences x=0 x=F équivalent à x<>0 quand MRF n’est pas nul.c’est bien la seule chose que je reproche la gamme 501->603 : l’absence de certains tests même si on s’en sort toujours.
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49g+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+ CM14 et MM12 / Alice 32
Re: A jouer aux reines avec une calculette de presque 40 ans !
Bonjour Shraf. Je me demande bien à quoi sert le passage en mode degré (DEG) au beau milieu du code.Schraf a écrit : ↑29 juil. 2022 16:57 Vu aujourd'hui dans cette vidéo consacrée à la calculatrice scientifique Casio fx-5800P
Ou alors c’est un NOP (no opération)? Mais dans ce cas pourquoi pas DSZ Y GOTO 0 ?
ÉDIT : je ne suis pas encore bien réveillé mais je vous laisse chercher.
ça semble le même code que celui que j’utilise basé sur les benchmark de Xerxes. Perso je changerai l’affichage final pour afficher la solution d’un bloc sur une ligne
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49g+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+ CM14 et MM12 / Alice 32
Re: A jouer aux reines avec une calculette de presque 40 ans !
Bonjour. J'ai écrit une version graphique (et récursive) du problèmes des n-reines sur Amstrad CPC+.
https://youtu.be/VAKbfoKBBW8
Le fichier .dsk (fonctionne avec gotek) avec les sources et exécutables (reines.com) est ici :https://drive.google.com/file/d/1j1C3l6 ... sp=sharing
Ça tourne en Cpm3, pour lancer le programme :
|Cpm reines
et une vidéo:https://youtu.be/VAKbfoKBBW8
Le fichier .dsk (fonctionne avec gotek) avec les sources et exécutables (reines.com) est ici :https://drive.google.com/file/d/1j1C3l6 ... sp=sharing
Ça tourne en Cpm3, pour lancer le programme :
|Cpm reines
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49g+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+ CM14 et MM12 / Alice 32
Re: A jouer aux reines avec une calculette de presque 40 ans !
Passer en revue toutes les options prend beaucoup de temps. Il existe une autre stratégie.
Nous mettons la reine sur a1, la suivante sur le champ disponible le plus proche de la colonne voisine est b3 (c'est aux coordonnées +1+2), la suivante est c5. Nous nous trouvons maintenant dans une situation qui n’a pas de solution valable pour 8 dames.
Retirez la reine c5 et placez-la sur la case ci-dessus. Nous vérifions si le poste a une solution. Sinon, on réorganise à nouveau la reine sur la c. Si la reine c ne peut se tenir sur aucune case, alors réorganisons la reine b.
Nous mettons la reine sur a1, la suivante sur le champ disponible le plus proche de la colonne voisine est b3 (c'est aux coordonnées +1+2), la suivante est c5. Nous nous trouvons maintenant dans une situation qui n’a pas de solution valable pour 8 dames.
Retirez la reine c5 et placez-la sur la case ci-dessus. Nous vérifions si le poste a une solution. Sinon, on réorganise à nouveau la reine sur la c. Si la reine c ne peut se tenir sur aucune case, alors réorganisons la reine b.
"N'importe quel programme peut être raccourci d'une pas": — un vieux dicton des programmeurs.
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3419
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: A jouer aux reines avec une calculette de presque 40 ans !
cela est très vrai ! Surtout sur une Ti-58C qui n'est pas une machine supersonique.
Par contre, passer ne revue toutes les options de cette façon a le mérite de n'utiliser que très peu (un minimum ?) de registres mémoires.
Et je suis d'accord, il a certainement suffisamment de registres dans une Ti-58 (et certainement dans une Ti-59) pour envisager une stratégie plus efficace et utilisant un peu plus de registres.
Mais, même un échiquier de petite taille utilise n² cases. Pour aller vite, il faut que le codage des positions possibles se fasse facilement (en un minimum d'instructions). Avec cette contrainte, même un l'échiquier faisant 8x8 cases nécessite 64 registres (ou cases) et cela ne tient plus dans une ti-58. Et je ne parle que des registres nécessaires pour coder l'état des case, il faut certainement ajouter autant de registre pour code les HEAP qui per met de trouver sans avoir à parcourir inlassablement en long et en large tout l'échiquier pour trouver la solution la plus proche suivante !
N'oublions pas que le code utilisé permet d'étudier des solutions sur des échiquiers plus ou moins grands. Etre limité à un échiquier 4x4 pour avoir une recherche rapide n'est pas très intéressant.
Mais, je suis preneur d'un meilleurs algorithme, comme celui indiqué par Trypilec, mais je ne sais pas comment l'implanter efficacement dans le ventre tout petit d'une Ti-58c. Surtout sans perdre un temps presque infini à coder ou compresser l'information par des calculs longs ou complexes à chaque changement de l'état binaire d'une case.
Par contre, sur d'autres machines, comme par exemple un SHARP PC-1360 ou un HP-28S, qui ont une arithmétique binaire et des instructions logiques pouvant traiter l'état de plusieurs cases simultanément; alors là oui, je sais comment implémenter quelque algorithme plus astucieux. Malheureusement, ces algorithmes deviennent lents et poussifs sur une machine AOS de 1977.
Peut-être Trypilec sait comment faire ?
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Re: A jouer aux reines avec une calculette de presque 40 ans !
théoriquement 8 registres pour les reines, 64 pour les casés, 16 pour les lignes et colonnes et 16 pour les diagonales. Mais vous pouvez faire moins. Pour le champ, 8 registres suffisent, où le nombre 11111111 signifie que tous les champs ne sont pas disponibles, et 11001111, que les champs d'ordonnées 5 et 6 sont disponibles. Mais alors il est difficile de vérifier si tous les champs de la ligne sont occupé. Et il est quelque peu difficile de remarquer que les champs diagonaux sont brisés. Deux cycles sont nécessaires. Est-ce que tout le monde est occupé dans la colonne:
frac{log(11111111-n)}=0 — si c'est le cas, alors tout le monde est occupé.
frac{log(11111111-n)}=0 — si c'est le cas, alors tout le monde est occupé.
"N'importe quel programme peut être raccourci d'une pas": — un vieux dicton des programmeurs.
Re: A jouer aux reines avec une calculette de presque 40 ans !
l'algorithme n'est pas le mien. Je l'ai copié de l'article Problème concernant les 8 reines. Un nouveau look. Étape 1 + 1/2. Nous réduisons le nombre d'étapes de recherche de trois fois et demie (langue russe)
"N'importe quel programme peut être raccourci d'une pas": — un vieux dicton des programmeurs.
Re: A jouer aux reines avec une calculette de presque 40 ans !
Pour marquer en diagonale les champs inaccessibles, il faut deux cycles pour les nombres en colonnes et deux pour les nombres en lignes. Seules les colonnes et les lignes peuvent être vérifiées pour un seul champ ou l'indisponibilité des champs. Mais 4 cycles, c'est aussi du temps supplémentaire. Y aura-t-il une victoire ? Cela sera possible pour les calculatrices à arithmétique binaire, mais le sera-t-il pour les calculatrices ordinaires ? Bien que, selon un tel algorithme, il soit plus rapide de trouver toutes les solutions sans calculatrice
"N'importe quel programme peut être raccourci d'une pas": — un vieux dicton des programmeurs.