Sudoku

[rm633]

Bonjour,

J'ai fait une recherche sur le forum et il semble que ce sujet n'aie pas fait l'objet d'un fil de discussion en soi.

Je ne suis pas très patient dans la vie. Moi les sudoku, ça me frustre. Alors j'ai fait une chose que je sais faire pas si mal et j'ai développé une macro en Excel pour les solutionner.

Depuis, je cherche à faire "sauter" ma solution. Je cherche les sudoku réputés très difficiles. Parait que celui nommé AI Escargot est le plus difficile. C'est celui-ci.

1 * *| * * 7| * 9 *
* 3 *| * 2 *| * * 8
* * 9| 6 * *| 5 * *
-------------------
* * 5| 3 * *| 9 * *
* 1 *| * 8 *| * * 2
6 * *| * * 4| * * *
-------------------
3 * *| * * *| * 1 *
* 4 *| * * *| * * 7
* * 7| * * *| 3 * *

Mon algorithme l'a solutionné en 104 itérations, ce qui n'est rien !

En revanche, celui-ci s'est avéré plus corsé.
4 * 2 | * 5 * | * * 6
* * * | * * * | * * 7
* * 8 | * * 7 | 4 * *
--------------------
* 2 6 | 4 * * | * * *
* * 5 | * * * | * * *
8 * * | 9 * * | * 7 5
--------------------
* * * | * * * | * * 9
* 6 * | 2 4 * | * * 3
2 * * | * 7 * | * 5 *

Il a fallu plus de 2600 itérations à mon algorithme pour trouver la solution.

Alors si vous croyez connaître des sudoku insolubles (insolutionnables ? insolvables ?), je suis preneur.

[embtw]

Salut rm633,

En voilà un, tu me diras le nombre d'itérations nécessaire.

9 * 8 | * 1 * | 2 * *
2 3 * | * 5 * | 6 * 8
* * 1 | * * * | * * 9
------------------------
5 * * | 7 * * | 1 * *
* * 4 | * 2 * | 5 * *
* * 3 | * * 1 | * * 2
------------------------
3 * * | * * * | 8 * *
7 * 2 | * 6 * | * 9 1
* * 9 | * 3 * | 7 * 5

[rm633]

132.

Vous voulez la solution ?

[embtw]

Non, non, c'est juste pour le fun.

J'en remettrais d'autres plus tard

[rm633]

Pour ceux et celles que ça intérèsse, celui-ci a requis 46 526 itérations.

* * *|* * *|* * *
* * *|* * 3|* 8 5
* * 1|* 2 *|* * *
------------------
* * *|5 * 7|* * *
* * 4|* * *|1 * *
* 9 *|* * *|* * *
------------------
5 * *|* * *|* 7 3
* * 2|* 1 *|* * *
* * *|* 4 *|* * 9

C'est un sudoku qui a été conçu justement pour déjouer certains types d'algorithmes, ceux dit de force brute.

[Wooden Ali]

salut rm633,
C'est curieux, qu'il soit si long à résoudre. A la main, il n'est pas particulièrement difficile : je l'ai résolu en 6 minutes ce qui correspond à un peu plus de deux fois ma moyenne pour résoudre les grilles "expert" de SimpleSudoku.

[embtw]

salut rm633,
C'est curieux, qu'il soit si long à résoudre. A la main, il n'est pas particulièrement difficile : je l'ai résolu en 6 minutes ce qui correspond à un peu plus de deux fois ma moyenne pour résoudre les grilles "expert" de SimpleSudoku.

Ceui que j'ai donné plus haut est une grille expert de SimpleSudoku

[rm633]

C'est curieux, qu'il soit si long à résoudre. A la main, il n'est pas particulièrement difficile : je l'ai résolu en 6 minutes ce qui correspond à un peu plus de deux fois ma moyenne pour résoudre les grilles "expert" de SimpleSudoku.

Comme je l'ai écrit, ce sudoku a été conçu pour embêter certains types d'algorithmes, sans qu'il soit nécessairement difficile à résoudre par un humain. L'inverse est vrai : un sudoku embêtant pour un humain sera résolu en quelques tours de manivelles par un certain type d'algo.

D'ailleurs, les sudoku les plus simples à résoudre "à la main" sont parfois très difficiles à résoudre par algorithmie. Celui-ci, pourtant simple, teste des conditions limites de mon algorithme.

5 3 * | * 7 * |* * *
6 * * |1 9 5 |* * *
* 9 8 |* * * |* 6 3
-----------------
8 * * |* 6 * |* * 1
4 * * |8 * 3 |* * 6
7 * * |* 2 * |* * *
-----------------
* 6 * |* * * |2 8 *
* * * |4 1 9 |* * 5
* * * |* 8 * |* 7 9

C'est amusant à constater.

[Chiwaw]

Ah! J'adore écrire des petits algos pour me permettre de résourdre des trucs que ma déficience en math m'empêche de faire.

Un copain m'avais expliqué une technique pour la Roulette pour lui assurer victoire à long terme. Bien entendu j'étais sceptique à l'os, évidemment si un jeu comme la Roulette avait une faille contre le Casino, il y a fort longtemps qu'elle aurait été exploité.

Pourtant, sur papier ça avais l'air de se tenir (compte tenu que je ne suis pas hyper connaissant en terme de probabilité/statistiques).

J'ai donc fait un simulateur de Roulette, avec un simple AI qui joue précisément suivant la "technique" du copain. Je l'ai fait rouler quelques millions de fois.

Au total, à long terme, ça m'a donné une efficacité d'environ 47.4%, soit exactement la même probabilité que de gagner en misant rouge ou noir (sur une table à double zéro). Et 48.6% d'efficacité sur une table à simple zéro.

Considérant qu'il faut une probabilité de plus de 50% pour avoir des chances (purement statistique) de gagner à long terme, j'ai renvoyé le copain refaire ses devoirs.

[curieux]

Salut Chiwaw

sur cette page (4eme ligne à télécharger : CasinoInstall.exe) http://www.finalkeno.freesurf.fr/cool/charger.php
ça permet d'étudier quelques méthodes soi-disant infaillibles pour gagner à la roulette.

Et sur celles-ci je détaille pourquoi les martingales ne marchent pas.
http://www.finalkeno.freesurf.fr/ameliora.php

[Denis]

Salut curieux,

J'ai essayé d'ouvrir tes deux liens, mais tout ce que j'ai reçu, c'est ça. Misère!

Je suppose que mon "package de protections" est trop performant et qu'il suffirait d'en désactiver quelques fonctions pour que tout soit dziguidou. Mais je ne souffre pas beaucoup de ne pas pouvoir les ouvrir. Dans un sens, ça me simplifie la vie.

Sur le forum, j'ai déjà expliqué pourquoi j'ai inclus "Martingales gagnantes à la roulette de casino" dans la liste officieuse des thèmes canoniques du forum.

Essentiellement, les raisons tournent autour de ça :

• Si un joueur de roulette se présente au casino avec un capital initial Ci (fini et positif) en poche et prévoit jouer jusqu'à ce que son montant en poche atteigne (ou dépasse) le capital final Cf (avec Cf > Ci), et ainsi faire un profit P au moins égal à Cf - Ci, alors, quelle que soit sa façon de jouer,
  
  1) Sa probabilité d'atteindre son but avant d'être ruiné est < Ci/Cf.
  2) Sa probabilité d'être ruiné avant d'atteindre son but est > (Cf-Ci)/Cf.

Par exemple, s'il arrive au casino avec $1000 en poche et qu'il prévoit jouer jusqu'à ce que son capital atteigne (ou dépasse) $5000, alors, quelle que soit sa façon de jouer,

1) Sa probabilité d'atteindre son but avant d'être ruiné est < 1/5.
2) Sa probabilité d'être ruiné avant d'atteindre son but est > 4/5.

En fait, mon argument-bulldozer pourrait être résumé par : On ne se bat pas contre un théorème.

Denis

[rm633]

J'ai trouvé mon plus corsé à ce jour. Il m'a permis de trouver un petit bogue dans mon algo.

Un coup corrigé, il a tout de même requis que l'algo effectue 68 699 itérations pour trouver la solution. À 38 itérations par seconde, environ, il a donc fallu un peu plus de 30 minutes pour le solutionner.

* * *|* * *|* * 1
* * *|* * *|* 2 3
* * 4|* * 5|* * *
------------------
* * *|1 * *|* * *
* * *|* 3 *|6 * *
* * 7|* * *|5 8 *
------------------
* * *|* 6 7|* * *
* 1 *|* * 4|* * *
5 2 *|* * *|* * *

Comment se solutionne-t-il à la main ?

ps : comment se fait-il qu'un fil de discussion dédié au sudoku ait viré en discussion sur la roulette

[curieux]

ps : comment se fait-il qu'un fil de discussion dédié au sudoku ait viré en discussion sur la roulette

C'est aussi une application des maths qu'on peut automatiser grâce à de la programmation. Pourquoi se casser la tête à calculer ce qu'on peut faire faire à une machine ?

[curieux]

Salut Denis

en effet, mais au moment où je postais ça fonctionnait. Bof.

[embtw]

L'hébergeur est en train de faire une mise à jour :

Wir fuehren gerade einige Aktualisierungen an den aelteren Redhat 4 Systemen durch. Diese erfordern in den naechsten Stunden einen Neustart des Systems fuer ca

Demain, cela devrait être bon, j'imagine.

[Wooden Ali]

Comment se solutionne-t-il à la main ?

Comme je l'ai déjà dis, rm633, j'utilise SimpleSudoku. Les aides ergonomiques sont très bonnes car il affiche toute les solutions possibles dans chaque case et permet de colorer les cases par chiffre.
Sinon la dernière grille que tu as donnée ne présente aucune difficulté : je l'ai résolu en 5'44" et je ne suis pas une flêche.

Essaye celle là, elle est classée en difficulté "extrême". J'ai mis 10'10" à la résoudre.
x7x 6xx x3x
xx4 3xx 9xx
32x xx7 56x
x4x x1x xxx
xxx xxx xxx
xxx x3x xxx
x62 3xx x19
xx7 xx9 6xx
x8x xx3 x7x

[curieux]

Tu es sûr de la ligne 7 ?
x62 3xx x19
le chiffre 3 est en conflit avec celui de la 2eme ligne.

c'est marrant Wooden Ali, après correction mon programme (en VB6) solutionne cette grille sans problème.

[Wooden Ali]

Tu as raison, curieux, c'est probablement une erreur. Peut être un 8 ?
Il est classé dans les extrêmes car on doit reconnaître un "swordfish pattern" pour le résoudre. Ce qui n'est pas toujours évident.
Les algorithmes manuels et programmés étant différents, ce n'est en définitive pas étonnant que "difficile" ne veuille pas dire la même chose dans ces deux modes de résolutions.
Je viens de voir qu'on peut utiliser le coupé-collé sous le format que vous avez utilisé. Ça m'évitera à l'avenir ce genre d'erreur.

[Zwielicht]

• Si un joueur de roulette se présente au casino avec un capital initial Ci (fini et positif) en poche et prévoit jouer jusqu'à ce que son montant en poche atteigne (ou dépasse) le capital final Cf (avec Cf > Ci), et ainsi faire un profit P au moins égal à Cf - Ci, alors, quelle que soit sa façon de jouer,
  
  1) Sa probabilité d'atteindre son but avant d'être ruiné est < Ci/Cf.
  2) Sa probabilité d'être ruiné avant d'atteindre son but est > (Cf-Ci)/Cf.

Par exemple, s'il arrive au casino avec $1000 en poche et qu'il prévoit jouer jusqu'à ce que son capital atteigne (ou dépasse) $5000, alors, quelle que soit sa façon de jouer,

1) Sa probabilité d'atteindre son but avant d'être ruiné est < 1/5.
2) Sa probabilité d'être ruiné avant d'atteindre son but est > 4/5.

Et s'il prévoit jouer jusqu'à ce que ses gains atteignent 10$ et qu'il a 1270$ en poche, sa probabilité d'accomplir son objectif est de ~99%. Sa chance d'être ruiné est de ~1%.

On ne se bat pas contre un théorème, mais on n'assimile pas n'importe quoi à n'importe quel théorème non plus.

Mais les casinos mettent des plafonds pour éviter ce genre de martingale... (probablement parce qu'ils n'aiment pas gagner de l'argent??!?!)

[Denis]

Salut Zwielicht,

Je comprends mal le sens de ta réplique. Peux-tu la reformuler en d'autres mots ?

Ce que j'y comprends, c'est qu'avec un capital initial Ci de 1270$ et, en guise d'objectif, un capital final Cf de 1280$, il est possible de jouer de telle sorte qu'on soit presque certain d'atteindre l'objectif. Ton ~99% me va (au premier niveau) puisqu'il ne contredit pas le théorème qui assure que cette probabilité est < Ci/Cf = 99.219%.

Ce que le théorème dit, c'est qu'il n'existe pas de stratégie de jeu qui permettrait, sans grand risque, d'accroître substantiellement son capital de départ.

Par "accroître substantiellement", j'entends "le multiplier par un nombre nettement plus grand que 1". Par exemple, le doubler ou le tripler.

La "substantialité" du profit est relative (au capital initial). Un profit de 1000$, à partir d'un Ci d'un million de $ n'est pas un profit substantiel (c'est un profit relatif de 0.1% seulement). On peut le réaliser sans grands risques.

Par contre, un profit de 1000$ à partir d'un Ci de $100 est un profit substantiel, 10 fois plus grand que la mise initiale. Ça, on a moins qu'une chance sur 11 de le réaliser, quelle que soit la façon de jouer.

Si tu trouves une martingale qui donne plus qu'une chance sur deux de doubler son capital initial (ou plus qu'une chance 10 de le décupler), explique-la clairement. J'essayerai de voir où tu t'es trompé.

Denis

[Zwielicht]

Ce que le théorème dit, c'est qu'il n'existe pas de stratégie de jeu qui permettrait, sans grand risque, d'accroître substantiellement son capital de départ.

Je n'ai pas lu ce théorème énoncé comme tel. Si je fais une recherche écran sur le radical substantiel, il n'apparait que dans ton dernier message. Ce que j'ai lu de ta part est que les martingales gagnantes sont du domaine zozo.

Or cette martingale, à faible gain relatif, est plutôt gagnante.

C'est à toi d'accorder ce que dit ton théorème et l'entrée que tu fais à cette martingale dans ta liste de thèmes canoniques. Gagnant ne veut pas dire : gagner au moins la moitié de son capital. Gagner veut dire gagner, un point c'est tout.

Si tu trouves une martingale qui donne plus qu'une chance sur deux de doubler son capital initial (ou plus qu'une chance 10 de le décupler), explique-la clairement. J'essayerai de voir où tu t'es trompé.

Si tu trouves une façon de voyager plus vite que la lumière, explique-la clairement. J'essayerai de voir où tu t'es trompé.

[Denis]

Salut Zwielicht,

Tu dis :

Ce que le théorème dit, c'est qu'il n'existe pas de stratégie de jeu qui permettrait, sans grand risque, d'accroître substantiellement son capital de départ.

Je n'ai pas lu ce théorème énoncé comme tel. Si je fais une recherche écran sur le radical substantiel, il n'apparait que dans ton dernier message. Ce que j'ai lu de ta part est que les martingales gagnantes sont du domaine zozo.

Or cette martingale, à faible gain relatif, est plutôt gagnante.

C'est à toi d'accorder ce que dit ton théorème et l'entrée que tu fais à cette martingale dans ta liste de thèmes canoniques. Gagnant ne veut pas dire : gagner au moins la moitié de son capital. Gagner veut dire gagner, un point c'est tout.

Techniquement, tu n'as pas tort.

Au lieu de dire "ce que le théorème dit", j'aurais dû être plus précis et dire "ce qu'on peut déduire du théorème".

Quand on dit~affirme quelque chose, on dit~affirme aussi, implicitement TOUT ce qui peut être logiquement déduit de ce quelque chose. Non ? Si je dis que ma chatte est dehors, je dis aussi, implicitement, qu'elle n'est pas dans la maison. Non ?

Quant à l'inclusion de "Martingales gagnantes à la roulette de casino" dans la liste des thèmes canoniques, je te réfère à l'avant-propos de cette liste :

Dans certains cas (ex. la lévitation, les fantômes ou le Père Noël), c'est l'existence même du machin qui est contestée.

Dans d'autres (ex. les crop circles, le suaire de Turin ou les ovnis), c'est plutôt le folklore pété qui les enrobe qui est contesté.

Les "Martingales gagnantes à la roulette de casino" tombent dans la seconde catégorie, avec les crop circles et le suaire de Turin, qui existent.

Dans le cas des martingales gagnantes au casino, c'est le folklore zozo-pété qui les enrobe qui est contesté. Et ce folklore zozo-pété, c'est qu'il existerait des martingales permettant, sans grands risques, de s'enrichir de façon substantielle (i.e. le quotient Cf/Ci serait significativement plus grand que 1).

Suggères-tu que je retire les crops circles et le suaire de Turin de la liste sous prétexte qu'ils existent ?

Faut dire que, dans cette liste, j'ai des contraintes de concision. Jusqu'ici, l'item le plus long est :

Effet Coriolis observable dans une cuve de toilette (contraste Nord-Sud)

J'hésite à battre ce record. Faudrait quand même pas qu'un item prenne 2~3 lignes.

Je devrais peut-être écrire Martingales substantiellement gagnantes à la roulette de casino, sans risque substantiel, mais ça battrait l'ancien record par 14 caractères (accroissement relatif substantiel de près de 20%).

Ça aurait quand même l'avantage de faire passer l'item du Cas 2 (on conteste le folklore zozo-pété) au Cas 1 (on conteste l'existence).

Devrait-on faire la même chose pour les crop circles et le suaire de Turin ? Si tu trouves des formulations en moins de 70~80 caractères, je suis preneur.

Denis

[Zwielicht]

Ce n'est pas la première fois qu'on a cette conversation, mais d'y introduire ton avant-propos ne change rien.. le problème est dans l'adjectif gagnant.

J'avais déjà proposé, il y a 3 ans de cela

Mais pour martingales, je suggère la formule : "martingales assurées".. pour faire concret

Donc je propose, pour ta liste, "martingales assurées". Ou "recettes pour s'enrichir à la loterie"

Et aujourd'hui je rajouterais:
martingales pour s'enrichir à coup sur à la roulette / loterie

D'ailleurs il me semble que j'avais quelque chose à voir dans la longueur de l'item sur Coriolis

[Denis]

Salut Zwielicht,

Tu suggères la formulation :

Martingales pour s'enrichir à coup sur à la roulette / loterie

En pinaillant à ta façon, je lui trouve de gros défauts.

Si on a 99.99999% de chance de gagner, est-ce "à coup sûr" ? Techniquement, non.

Si, en investissant 1000000000$, on fait un profit de 1¢, s'est-on enrichi ? Techniquement, oui.

Faudrait corriger le tir et écrire plutôt :

Martingales permettant, à la roulette, de s'enrichir substantiellement à coup presque sûr

Mais ça battrait quand même l'ancien record par 17 caractères et le mot "substantiellement" (qui est important) resterait encore à préciser. Il faudrait qu'il soit clair qu'on parle d'enrichissement relatif au capital de départ.

Selon le capital de départ, un profit de 100$ sera substantiel ou ne le sera pas.

Si, dans la liste des thèmes canoniques, je mettais Martingales permettant, à la roulette, de s'enrichir substantiellement à coup presque sûr, ça t'irait ?

Tu ne chiâlerais plus ?

Denis

[Zwielicht]

Salut Denis

En pinaillant à ta façon, je lui trouve de gros défauts.

Tu ne pinailles pas à ma façon, mais à la tienne. Tu utilises un argument qu'on retrouve souvent chez les gens qui n'admettent jamais aucun tort.

B est proposé pour remplacer A. Or tu prouves que B n'est pas parfait afin de rejeter la proposition et garder A. Alors qu'il faudrait montrer que B n'est pas mieux que A et pire à certains égards.

S'enrichir ne signifie pas devenir plus riche, mais rendre riche. Gagner 10$ ne rend pas riche !

Si le à coup sûr t'embête, enlève-le ou plutôt, ajoutes-y le "presque" si tu tiens tant à démontrer que ma suggestion est ridicule car elle mène à une formulation rigolote et maladroite.