Misez p'tit Optimisez n°91 : balade du cavalier

Ici, on fait dans le petit, le LCD qui déchire sa race, on y cause même calculatrices quand on est en manque !

Modérateur : Politburo

Répondre
Avatar de l’utilisateur
ledudu
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5292
Inscription : 26 mars 2009 14:07
Localisation : Ile de France
Contact :

Misez p'tit Optimisez n°91 : balade du cavalier

Message par ledudu » 27 oct. 2019 15:09

Bonjour à tous,

J'ai observé sur la carte météo de l'après-midi une vaste zone MPO :
meteo.png
meteo.png (102.7 Kio) Consulté 5659 fois
Alors pour ceux qui sont dans cette zone, je vous propose un petite récréation au sec : à partir d'une case quelconque de l'échiquier,
déplacer le cavalier sans jamais repasser au même endroit et en couvrant les 64 cases.

La machine doit demander la position initiale et devra afficher ou imprimer pas à pas l'échiquier avec les 64 positions successives du cavalier.

Ceux qui sont hors zone MPO pourront évidemment se consacrer également à ce sujet après le vide grenier du matin ou la promenade en forêt de l'après-midi.

le sommaire des MPO.
Dernière édition par ledudu le 27 oct. 2019 17:04, édité 2 fois.
Toujours préférer l'hypothèse de la connerie à celle du complot.
La connerie est courante. Le complot exige un esprit rare.
Michel Rocard

Avatar de l’utilisateur
Marge
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5221
Inscription : 01 oct. 2008 14:39
Localisation : En bas, tout au fond à gauche.

Re: Misez p'tit Optimisez n°91 : balade du cavalier

Message par Marge » 27 oct. 2019 15:43

Super MPO !

Et ça tombe bien, si je prolonge les parallèles de la carte en bas à gauche, je pourrais bien me trouver dans la zone - sans les nuages cependant... d'où un rythme d'étude probablement fort ralenti... ;)

Edith me souffle qu'il ne doit pas être évident de mettre en place quelque chose - sans raccourci mathématique - pour une machine "inférieure" à la hp-67... mais a-t-elle raison ?
3 hommes, 3 demis, un 3a... Magnéto, Serge !

« Boris », c'est juste Maurice enrhumé.

Avatar de l’utilisateur
C.Ret
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 2286
Inscription : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit Optimisez n°91 : balade du cavalier

Message par C.Ret » 27 oct. 2019 22:05

Oh ! Bien… Très bien...

C'est chouette le Springerproblem !! Ca c'est un bon Rösselsprungrätsel à résoudre par une pluvieuse journée d'octobre !!

Image

Bien, mais avec 64 cases, je vois arriver plus de 26'534'728'821'064 possibilités … Ca va être long avec mon PC-1211 même équipé de sa CE-122.

Je vais donc, vite aller faire un tours du côté de Weltstadt Wermelskirchen. Il parait qu'en 1989 il y a plut pendant 360 jours et qu'il a neigé les cinq autres jours. Je trouverai peut-être un moyen de résoudre ce délicieux problème à l'abri de la pluie ...

Il doit y avoir une solution quelque soit la case où l'on commence !!

Mais comment la trouver ???

:wink:

Wer möchte mit mir kommen, dem böhmischen König H. C. Warnsdorf einen Besuch abstatten und mit Ihrem Exzellenz Schach spielen?


Image
SHARP PC-1211 + CE-121 + CE-122. | VIC 20 Commodore 128D + Printer P-803 + SD2iec. | TI-57 LCD | TI-74 BasiCalc | TI-92 II | HP-28S + HP82240A | HP-41C + (2 memory + stat + IR) modules. | HP Prime Wireless Graphing Calculator | HP-15C | CASIO fx-602p + FA-1. .Sommaire des M.P.O.. . Sommaire du P.C.T.M. .

Avatar de l’utilisateur
ledudu
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5292
Inscription : 26 mars 2009 14:07
Localisation : Ile de France
Contact :

Re: Misez p'tit Optimisez n°91 : balade du cavalier

Message par ledudu » 27 oct. 2019 22:45

Effectivement, j'ai écrit un petit programme de parcours des solutions sur fx-cp400 et avec le plateau 8x8 cases, je ne sais pas s'il arriverait un jour au bout. J'observe en effet qu'il est parti sur une branche de recherche sans solutions (parce qu'il a laissé une case orpheline sur le côté).
J'ai relancé sur un plateau 5x5 - il n'y a pas semble-t-il de résultats à 4x4.
https://fr.wikipedia.org/wiki/Probl%C3%A8me_du_cavalier
Toujours préférer l'hypothèse de la connerie à celle du complot.
La connerie est courante. Le complot exige un esprit rare.
Michel Rocard

Avatar de l’utilisateur
Marge
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5221
Inscription : 01 oct. 2008 14:39
Localisation : En bas, tout au fond à gauche.

Re: Misez p'tit Optimisez n°91 : balade du cavalier

Message par Marge » 27 oct. 2019 23:38

Oh ! là !

Il ne s'agit pas de chercher des solutions qui existeraient chez Wiki ! Ou alors ça n'a aucun intérêt. Ou je n'ai pas compris le but du jeu...

D'après ce que j'ai lu sur le problème (Wiki, certes, mais partie Historique seulement), certaines solutions ont été trouvées au cours des siècles, mais pas toutes, et certaines positions semblent sans issues...

Selon moi, ce qui est intéressant est de demander à un calculateur (je parle d'une machine) de tester certaines possibilités pour parvenir à (au moins) une solution. Le "Comment faire ?" est le plus passionnant à mon avis.

Le reste est certainement soluble par une Prime ou une HP-48 (et supérieures), ou Casio, etc., mais n'a, à mon avis, aucun intérêt... ou alors, pour quelques personnes ici qui se reconnaîtront aisément.
3 hommes, 3 demis, un 3a... Magnéto, Serge !

« Boris », c'est juste Maurice enrhumé.

Avatar de l’utilisateur
gege
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 6932
Inscription : 31 janv. 2008 15:24
Localisation : Banlieue Paârisienne
Contact :

Re: Misez p'tit Optimisez n°91 : balade du cavalier

Message par gege » 27 oct. 2019 23:49

Bonjour,
Une technique raffinée dite "force brute" semble en effet s'imposer sur Prime !
A voir...
G.E.

Avatar de l’utilisateur
C.Ret
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 2286
Inscription : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit Optimisez n°91 : balade du cavalier

Message par C.Ret » 28 oct. 2019 11:33

Bandes de brutes…

Vous faites comme vous voulez, mais j'ai eut la même réflexion que Marge.

Du coup je me suis approché de chevaliers teutoniques proches de chez moi et qui jouent aux échecs depuis le XIV° siècle. Ils m'ont montré comment il procèdent pour résoudre ce problème qui fait partie de la formation dans leur Schachs Klub.

Vu qu'ils s'en sortent très bien avec quelques haricots et des échiquiers en bois. Je pense pouvoir faire cela sans aucun souci avec un équipement aussi perfectionné et puissant qu'un SHARP PC-1211 (muni que son fidèle berceau CE-122).


Mais, bon, si ça marche sur un SHARP du XX°s, cela doit être possible aussi sur une Prime du XXI°
Je ne me presserai donc pas pour publier mes travaux afin de laisser à chacun de plaisir de bien chercher.

Pour commencer, je donne un indice :
Image



P.S.: Question force brute, mes chevaliers teutons ne pèsent pas lourd. Ce doit être l'usure du temps, ou le fait qu'il ont abondonné leurs montures pour se déplacer en Mercedes ?
SHARP PC-1211 + CE-121 + CE-122. | VIC 20 Commodore 128D + Printer P-803 + SD2iec. | TI-57 LCD | TI-74 BasiCalc | TI-92 II | HP-28S + HP82240A | HP-41C + (2 memory + stat + IR) modules. | HP Prime Wireless Graphing Calculator | HP-15C | CASIO fx-602p + FA-1. .Sommaire des M.P.O.. . Sommaire du P.C.T.M. .

Avatar de l’utilisateur
ledudu
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5292
Inscription : 26 mars 2009 14:07
Localisation : Ile de France
Contact :

Re: Misez p'tit Optimisez n°91 : balade du cavalier

Message par ledudu » 28 oct. 2019 12:21

Salut,

Ravi que nous soyons au moins une petite poignée sur le sujet.

Perso, je ne sais pas si je suis d'accord avec Marge vu que j'ai rien compris. :oops: :oops:
Alors je passe. :D

J'ai donc fait tourner une casio fx-CP400 toute la nuit sur un échiquier 5x5 en commençant dans un coin (je l'ai laissée tourner 2 heures avant de me coucher). L'écran affiche l'échiquier au fur et à mesure des déplacements.
Le programme sauvegarde juste l'image de l'écran lorsque l'échiquier est complet.
Et au matin, j'avais une solution avec un joli écran et les 25 positions successives de mon cavalier... mais pas d'info sur la longueur du traitement.
Du coup, j'ai relancé ce matin sur un échiquier 6x6 avant de quitter la maison non sans avoir ajouté deux compteurs que j'affiche à l'écran en fin de traitement:
- le nombre total de coups en avant de mon cavalier,
- le nombre total de coups en arrière (en cas de blocage).

Mon algo est pour l'instant ultra bestial. Les huit déplacements possibles rappelés par c.ret sont numérotés (n = 1...8 ).
J'avance mon cheval sur une case libre en commençant par n=1.
Lorsque je suis bloqué (pas de prochaine case libre), j'annule le précédent déplacement n et je passe au n suivant.
Si je suis déjà à n=8, je remonte encore d'un déplacement et ainsi de suite.

Quelles sont vos pistes d'optimisation ?
J'attends impatiemment vos retours.

De mon côté, je vais essayer de voir si la traque des cases orphelines (c'est à dire impossible à rallier) n'est pas un moyen économe de couper une branche par anticipation. J'ai juste peur que le temps passé à les détecter soit contre-productif.
Je vais peut-être commencer par les cases orphelines sur les côtés, plus rapidement décelables.

Autre optimisation possible mais qui rend l'usage moins sympa et ne respecte pas le cahier des charges : ne rien afficher avant la fin ou seulement tous les NB déplacements. En effet, afficher chaque coup en avant et effacer chaque coup en arrière consomme certainement énormément…

A suivre,

Rem : il est difficile de comparer deux programmes différents. Le nombre de coups pour atteindre la solution dépend du sens de parcours des déplacements possibles à chaque étape.

Les plus belles, les solutions fermées, permettent de rejoindre la première case à partir de la dernière case visitée.
Dans une solution fermée, toute position de départ peux conduire à la solution dans les deux sens de circulation.
Toujours préférer l'hypothèse de la connerie à celle du complot.
La connerie est courante. Le complot exige un esprit rare.
Michel Rocard

Avatar de l’utilisateur
Marge
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5221
Inscription : 01 oct. 2008 14:39
Localisation : En bas, tout au fond à gauche.

Re: Misez p'tit Optimisez n°91 : balade du cavalier

Message par Marge » 28 oct. 2019 13:45

Mon algo est pour l'instant ultra bestial. Les huit déplacements possibles rappelés par c.ret sont numérotés (n = 1...8 ).
J'avance mon cheval sur une case libre en commençant par n=1.
Lorsque je suis bloqué (pas de prochaine case libre), j'annule le précédent déplacement n et je passe au n suivant.
Si je suis déjà à n=8, je remonte encore d'un déplacement et ainsi de suite.

Quelles sont vos pistes d'optimisation ?
J'attends impatiemment vos retours.
Je ne pensais pas à autre chose ; c'est assez brutal en effet, mais il y a peut-être moyen de raffiner tout cela. :wink:
3 hommes, 3 demis, un 3a... Magnéto, Serge !

« Boris », c'est juste Maurice enrhumé.

Avatar de l’utilisateur
ledudu
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5292
Inscription : 26 mars 2009 14:07
Localisation : Ile de France
Contact :

Re: Misez p'tit Optimisez n°91 : balade du cavalier

Message par ledudu » 28 oct. 2019 14:47

Marge a écrit :
28 oct. 2019 13:45
mais il y a peut-être moyen de raffiner tout cela. :wink:
Tu [ne] me trouves pas assez raffiné c'est ça ?
:D :D :D
Toujours préférer l'hypothèse de la connerie à celle du complot.
La connerie est courante. Le complot exige un esprit rare.
Michel Rocard

Avatar de l’utilisateur
Marge
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5221
Inscription : 01 oct. 2008 14:39
Localisation : En bas, tout au fond à gauche.

Re: Misez p'tit Optimisez n°91 : balade du cavalier

Message par Marge » 28 oct. 2019 16:47

ledudu a écrit :
28 oct. 2019 14:47
Marge a écrit :
28 oct. 2019 13:45
mais il y a peut-être moyen de raffiner tout cela. :wink:
Tu [ne] me trouves pas assez raffiné c'est ça ?
:D :D :D

Mais si, mais si... je disais ça juste pour me faire passer pour intelligent. :wink:
3 hommes, 3 demis, un 3a... Magnéto, Serge !

« Boris », c'est juste Maurice enrhumé.

Avatar de l’utilisateur
ledudu
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5292
Inscription : 26 mars 2009 14:07
Localisation : Ile de France
Contact :

Re: Misez p'tit Optimisez n°91 : balade du cavalier

Message par ledudu » 28 oct. 2019 18:30

Marge a écrit :
28 oct. 2019 16:47
Mais si, mais si... je disais ça juste pour me faire passer pour intelligent. :wink:
C'est réussi !
8)
Toujours préférer l'hypothèse de la connerie à celle du complot.
La connerie est courante. Le complot exige un esprit rare.
Michel Rocard

Avatar de l’utilisateur
Marge
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5221
Inscription : 01 oct. 2008 14:39
Localisation : En bas, tout au fond à gauche.

Re: Misez p'tit Optimisez n°91 : balade du cavalier

Message par Marge » 28 oct. 2019 22:30

ledudu a écrit :
28 oct. 2019 18:30
Marge a écrit :
28 oct. 2019 16:47
Mais si, mais si... je disais ça juste pour me faire passer pour intelligent. :wink:
C'est réussi !
8)
Le problème, c'est que même moi, parfois, j'y crois ! :roll:
3 hommes, 3 demis, un 3a... Magnéto, Serge !

« Boris », c'est juste Maurice enrhumé.

Avatar de l’utilisateur
C.Ret
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 2286
Inscription : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit Optimisez n°91 : balade du cavalier (Indice n°2)

Message par C.Ret » 29 oct. 2019 22:00

C'est plus qu'un indice, c'est un détail très important et je suis sûr que plus de la moitié d'entre nous va devoir recommencer ses travaux !


En effet, le but de ce MPO est d'afficher ou d'imprimer un échiquier :
Pour rappel :
ledudu a écrit :
27 oct. 2019 15:09
[…] La machine doit demander la position initiale et devra afficher ou imprimer pas à pas l'échiquier avec les 64 positions successives du cavalier.
[…]
(Je sens que ce MPO va faire grimper le prix du papier thermique et des rouleaux de rubans encreurs !
64 échiquiers conformes à imprimer tout de même.)


Hors, un échiquier du jeu d'échec ce n'est pas n'importe quoi et surtout pas une matrice de 8x8 dessinée au hasard !

Un échiquier c'est quelque chose qui doit ressembler à cela :
Echiquier.jpg
Echiquier.jpg (28.06 Kio) Consulté 5485 fois
Un échiquier est donc une alternance de cases de deux couleurs.
Vous noterez également cher amis que la case A1 se situe en bas à gauche et qu'elle est noire (ou de couleur sombre).


A la rigueur, j'accepterai un échiquier qui ne soit pas une alternance de case noire et blanche, à la limite une alternance de case claires et foncées !
Mais en aucun cas, l'échiquier ne doit être uni et la case A1 ne doit se trouver ailleurs qu'en bas à gauche ou être négligemment décolorée

Et oui, je donne cet indice immédiatement, au début de vos mise aux points avant que vous ne deviez recommencer tout votre programme !

Aucun échiquier farfelu avec une case A1 mal placée ou mal colorée ne pourra être accepté (ce serait, à mon sens, un manque de raffinement ou d'intelligence).

Mais bon, je ne suis pas seul juge ici...
SHARP PC-1211 + CE-121 + CE-122. | VIC 20 Commodore 128D + Printer P-803 + SD2iec. | TI-57 LCD | TI-74 BasiCalc | TI-92 II | HP-28S + HP82240A | HP-41C + (2 memory + stat + IR) modules. | HP Prime Wireless Graphing Calculator | HP-15C | CASIO fx-602p + FA-1. .Sommaire des M.P.O.. . Sommaire du P.C.T.M. .

Avatar de l’utilisateur
ledudu
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5292
Inscription : 26 mars 2009 14:07
Localisation : Ile de France
Contact :

Re: Misez p'tit Optimisez n°91 : balade du cavalier

Message par ledudu » 29 oct. 2019 22:58

Heu, dans mon esprit, j'avais imaginé un seul échiquier et une imprimante style FA-10 qui ajoute la nouvelle position...
Mais bon c'était sans compter tous les retours arrière.

J'enlève officiellement l'imprimante de cette équation :pirat: :pirat: :pirat:
Toujours préférer l'hypothèse de la connerie à celle du complot.
La connerie est courante. Le complot exige un esprit rare.
Michel Rocard

Répondre

Revenir vers « Tous les Pockets »