{"id":3139,"date":"2022-08-06T22:01:02","date_gmt":"2022-08-07T01:01:02","guid":{"rendered":"https:\/\/www.geekosas.com\/?p=3139"},"modified":"2023-03-26T23:55:55","modified_gmt":"2023-03-27T02:55:55","slug":"sudoku","status":"publish","type":"post","link":"https:\/\/geekosas.com\/index.php\/es\/2022\/08\/06\/sudoku\/","title":{"rendered":"Sudoku"},"content":{"rendered":"

Mi primera prueba de optimizaci\u00f3n tuvo como primera pregunta plantear el modelo matem\u00e1tico para resolver un Sudoku, bueno, en ese momento comet\u00ed un error garrafal, puse restricciones no lineales obteniendo 0 puntos y bueno como este fue uno de mis ramos favoritos, siempre me acorde de la mala experiencia.<\/p>\n

Es por eso que hoy vengo a corregir aquel error del pasado.<\/p>\n

Un Sudoku es un juego de ingenio que en reglas es muy simple, pero la verdad para mi es dif\u00edcil de resolver, consiste en una grilla de 9×9 donde vienen unos n\u00fameros en algunas celdas mientras que otras est\u00e1n vacias, el puzle consiste el rellenar en cada fila hay y cada columna con numeros del 1 al 9 sin que se repitan.<\/p>\n

La condici\u00f3n anterior tambien debe cumplirse para cada uno de los cuadrilateros de 3×3 de la siguiente imagen, donde se puede ver el puzle y su soluci\u00f3n a la derecha:<\/p>\n

\"\"<\/p>\n

Bueno esto matem\u00e1ticamente se puede plantear del siguiente modo, e ir\u00e9 mostrando como se programa lo mismo en Python usando PuLP. Al final pondr\u00e9 todo el c\u00f3digo en un repositrio GIT<\/p>\n

Inicializar el problema matem\u00e1tico
\nprob = pulp.LpProblem("prob", pulp.LpMaximize)<\/code><\/p>\n

Indices:<\/h4>\n

Fila f \\in 1..9<\/code>
\nfila = [x for x in range(9)]<\/code>
\nColumna c \\in 1..9<\/code>
\ncolum = [x for x in range(9)]<\/code>
\nValor v \\in 1..9<\/code>
\nval = [x for x in range(9)]<\/code><\/p>\n

Variables de decisi\u00f3n<\/h4>\n

G_{f,c,v} \\in [0,1]<\/code> donde 1 significa que en la fila f, columna c se asigna el valor v.<\/p>\n

game = [[[pulp.LpVariable(cat ='Binary', name ='fila {}, col {} es {}'.format(f, c, v+1)) for f in fila] for c in colum] for v in val]<\/code><\/pre>\n
Par\u00e1metros<\/h4>\n
P_{f,c,v} \\in [0,1]<\/code> donde 1 significa que en la fila f, columna c se debe asignar el valor v.<\/p>\n
wb = load_workbook("sudoku.xlsx", data_only=True)\nsh = wb.worksheets[0]\npuzzle = [[[0 for k in range(9)] for j in range(9)] for i in range(9)]\nfor f,c,v in product(range(9),range(9),range(9)):\n    if sh.cell(f+1,c+1).value == v+1:\n        puzzle[f][v] = 1<\/code><\/pre>\n
Funci\u00f3n Objetivo<\/h4>\n
max \\sum_{f,c,v} G_{f,c,v}<\/code> Maximizar el n\u00famero de valores asignados<\/p>\n
prob += pulp.lpSum(game)<\/code><\/pre>\n
Restricciones:<\/h4>\n
Se debe respetar el puzle<\/h5>\n
\\forall f,c,v  G_{f,c,v}  \\ge P_{f,c,v}<\/code><\/p>\n
for f,c,v in product(fila,colum,val):\n    prob += game[f][v] >= puzzle[f][v]<\/code><\/pre>\n
En cada celda solo puede haber un valor<\/h5>\n
\\forall f,c  \\sum_v G_{f,c,v}  \\le 1<\/code><\/p>\n
for f,c in product(fila,colum):\n    prob += pulp.lpSum([game[f][v] for v in val]) <= 1<\/code><\/pre>\n
Cada Fila puede contener solo una vez cada valor<\/h5>\n
\\forall f,v  \\sum_c G_{f,c,v}  \\le 1<\/code><\/p>\n
for f,v in product(fila,val):\n    prob += pulp.lpSum([game[f][v] for c in colum]) <= 1<\/code><\/pre>\n
Cada Columna puede contener solo una vez cada valor<\/h5>\n
\\forall c,v  \\sum_f G_{f,c,v}  \\le 1<\/code><\/p>\n
for c,v in product(fila,val):\n    prob += pulp.lpSum([game[f][v] for f in fila]) <= 1<\/code><\/pre>\n
Cada cuadril\u00e1tero debe tener una vez cada valor<\/h5>\n
cc = indice del cuadril\u00e1tero en columna
\ncf = indice del cuadril\u00e1tero en fila
\nf = fila del cuadril\u00e1tero
\nc = columna del cuadril\u00e1tero
\n`$$ \\forall cf,cc,v \\in [1,2,3],[1,2,3],val  \\sum{f\\in[1,2,3],c\\in[1,2,3],v} G<\/em>{f+3cf,f+3<\/em>cc,v}  \\le 1 $$<\/p>\n
for cf,cc,v in product(range(3),range(3),val):\n    prob += pulp.lpSum([game[f+3*cf][v] for f,c in product(range(3),range(3))]) <= 1<\/code><\/pre>\n
Resolver el problema y obtener resultados<\/h4>\n
solver = pulp.getSolver('PULP_CBC_CMD')\nprob.solve(solver)\n\nsol = [[0 for k in range(9)] for j in range(9)]\nfor f,c,v in product(fila,colum,val):\n    if(pulp.value(game[f][v]) > 0.9):\n        sol[f] = v + 1\n\nfor f in fila:\n    print(sol[f])<\/code><\/pre>\n
[6, 4, 3, 5, 1, 7, 9, 2, 8]\n[8, 1, 5, 3, 2, 9, 7, 4, 6]\n[2, 9, 7, 8, 6, 4, 3, 1, 5]\n[9, 2, 8, 1, 7, 5, 6, 3, 4]\n[4, 7, 1, 6, 3, 2, 5, 8, 9]\n[5, 3, 6, 9, 4, 8, 1, 7, 2]\n[7, 5, 9, 4, 8, 3, 2, 6, 1]\n[3, 6, 4, 2, 5, 1, 8, 9, 7]\n[1, 8, 2, 7, 9, 6, 4, 5, 3]<\/code><\/pre>\n
Que es igual al ejemplo:
\n\"\"<\/p>\n
Puedes encontrar el c\u00f3digo completo en mi github:
\nhttps:\/\/github.com\/danielfm123\/sudoku_solver<\/a><\/p>\n
Saludos!<\/p>\n","protected":false},"excerpt":{"rendered":"
Mi primera prueba de optimizaci\u00f3n tuvo como primera pregunta plantear el modelo matem\u00e1tico para resolver un Sudoku, bueno, en ese momento comet\u00ed un error garrafal, […]<\/a><\/p>\n<\/div>","protected":false},"author":1,"featured_media":3158,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[1],"tags":[],"class_list":["post-3139","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-sin-categoria"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"https:\/\/i0.wp.com\/geekosas.com\/wp-content\/uploads\/2022\/08\/puzle.jpg?fit=310%2C153&ssl=1","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/s8vjqF-sudoku","jetpack-related-posts":[{"id":2269,"url":"https:\/\/geekosas.com\/index.php\/es\/2017\/12\/18\/estimacion-repartija-de-votos-segunda-vuelta-presidenciales-chile-2017\/","url_meta":{"origin":3139,"position":0},"title":"Estimaci\u00f3n repartija de votos segunda vuelta presidenciales Chile 2017","author":"Daniel Fischer","date":"2017-12-18","format":false,"excerpt":"Este Articulo fu\u00e9 hecho apurado y con pocos datos, el definitivo est\u00e1 en\u00a0Quien vot\u00f3 por cada Candidato? Despu\u00e9s de la primera vuelta de las elecciones presidenciales de Chile, es tradicional que cada uno de los candidatos comienza a \"rematar\" los votos de sus seguidores a aquel candidato con el que\u2026","rel":"","context":"In "Sin categor\u00eda"","block_context":{"text":"Sin categor\u00eda","link":"https:\/\/geekosas.com\/index.php\/category\/sin-categoria\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/geekosas.com\/wp-content\/uploads\/2017\/12\/segunda-vuelta.jpg?fit=710%2C399&ssl=1&resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/geekosas.com\/wp-content\/uploads\/2017\/12\/segunda-vuelta.jpg?fit=710%2C399&ssl=1&resize=350%2C200 1x, https:\/\/i0.wp.com\/geekosas.com\/wp-content\/uploads\/2017\/12\/segunda-vuelta.jpg?fit=710%2C399&ssl=1&resize=525%2C300 1.5x, https:\/\/i0.wp.com\/geekosas.com\/wp-content\/uploads\/2017\/12\/segunda-vuelta.jpg?fit=710%2C399&ssl=1&resize=700%2C400 2x"},"classes":[]},{"id":2067,"url":"https:\/\/geekosas.com\/index.php\/es\/2016\/03\/27\/que-son-las-redes-neuronales\/","url_meta":{"origin":3139,"position":1},"title":"Que son las redes neuronales?","author":"Daniel Fischer","date":"2016-03-27","format":false,"excerpt":"Muchos han escuchado alguna vez hablar sobre las redes neuronales o la \"inteligencia artificial\" y hemos de ser honestos que cuando alguien utiliza aquellas palabras, suena como todo un Einstein de la computaci\u00f3n sacado de Terminator 2. B\u00e1sicamente, las redes neuronales, se aplican cuando el desarrollador no tiene la m\u00e1s\u2026","rel":"","context":"In "Uncategorized"","block_context":{"text":"Uncategorized","link":"https:\/\/geekosas.com\/index.php\/es\/category\/uncategorized-es\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/geekosas.com\/wp-content\/uploads\/2016\/03\/ai.jpg?fit=608%2C211&ssl=1&resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/geekosas.com\/wp-content\/uploads\/2016\/03\/ai.jpg?fit=608%2C211&ssl=1&resize=350%2C200 1x, https:\/\/i0.wp.com\/geekosas.com\/wp-content\/uploads\/2016\/03\/ai.jpg?fit=608%2C211&ssl=1&resize=525%2C300 1.5x"},"classes":[]},{"id":21,"url":"https:\/\/geekosas.com\/index.php\/es\/2016\/04\/11\/como-elegir-celular\/","url_meta":{"origin":3139,"position":2},"title":"Como elegir celular?","author":"Daniel Fischer","date":"2016-04-11","format":false,"excerpt":"Pasamos m\u00e1s tiempo con nuestro celular que con nuestra familia, es m\u00e1s, lo usamos para comunicarlos con ella y para muchos es una herramienta fundamental de trabajo. Un celular, quiera admitirlo o no, es un compa\u00f1ero de vida, que seg\u00fan sea la relaci\u00f3n te podr\u00eda acompa\u00f1ar el ba\u00f1o por varios\u2026","rel":"","context":"In "Sin categor\u00eda"","block_context":{"text":"Sin categor\u00eda","link":"https:\/\/geekosas.com\/index.php\/category\/sin-categoria\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/geekosas.com\/wp-content\/uploads\/2016\/04\/mensagens_amor_namorados_para_celular.jpg?fit=400%2C225&ssl=1&resize=350%2C200","width":350,"height":200},"classes":[]},{"id":2639,"url":"https:\/\/geekosas.com\/index.php\/es\/2019\/02\/12\/r-y-pc-superdorerosos\/","url_meta":{"origin":3139,"position":3},"title":"R y PC super-porerosos","author":"Daniel Fischer","date":"2019-02-12","format":false,"excerpt":"R y python est\u00e1n muy de moda \u00faltimamente, pero te haz preguntado si le est\u00e1s sacan totalmente el jugo a esos lenguajes, es m\u00e1s, seguramente para trabajar con ellos tienes un PC super-poderoso, bueno, la verdad es que si est\u00e1s entrando al mundo del Analytics, posiblemente aun no lo est\u00e9s\u2026","rel":"","context":"In "Sin categor\u00eda"","block_context":{"text":"Sin categor\u00eda","link":"https:\/\/geekosas.com\/index.php\/category\/sin-categoria\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/geekosas.com\/wp-content\/uploads\/2019\/02\/2922898-a.jpg?fit=350%2C350&ssl=1&resize=350%2C200","width":350,"height":200},"classes":[]},{"id":2278,"url":"https:\/\/geekosas.com\/index.php\/es\/2017\/12\/23\/quien-voto-por-cada-candidato\/","url_meta":{"origin":3139,"position":4},"title":"Quien vot\u00f3 por cada Candidato?","author":"Daniel Fischer","date":"2017-12-23","format":false,"excerpt":"El domingo pasado se eligi\u00f3 presidente de Chile, por ende muchos opin\u00f3logos intentaron explicar como se repartieron los votos de la primera vuelta a la segunda vuelta. Como el voto es secreto, nadie puede estar mal. Por eso decid\u00ed dar un aproach distinto al standard, recurriendo a un modelo matem\u00e1tico\u2026","rel":"","context":"In "Sin categor\u00eda"","block_context":{"text":"Sin categor\u00eda","link":"https:\/\/geekosas.com\/index.php\/category\/sin-categoria\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/geekosas.com\/wp-content\/uploads\/2017\/12\/1511132848-untitled-collage-3.jpg?fit=1200%2C675&ssl=1&resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/geekosas.com\/wp-content\/uploads\/2017\/12\/1511132848-untitled-collage-3.jpg?fit=1200%2C675&ssl=1&resize=350%2C200 1x, https:\/\/i0.wp.com\/geekosas.com\/wp-content\/uploads\/2017\/12\/1511132848-untitled-collage-3.jpg?fit=1200%2C675&ssl=1&resize=525%2C300 1.5x, https:\/\/i0.wp.com\/geekosas.com\/wp-content\/uploads\/2017\/12\/1511132848-untitled-collage-3.jpg?fit=1200%2C675&ssl=1&resize=700%2C400 2x, https:\/\/i0.wp.com\/geekosas.com\/wp-content\/uploads\/2017\/12\/1511132848-untitled-collage-3.jpg?fit=1200%2C675&ssl=1&resize=1050%2C600 3x"},"classes":[]},{"id":664,"url":"https:\/\/geekosas.com\/index.php\/es\/2016\/04\/18\/jugando-con-redes-neuronales\/","url_meta":{"origin":3139,"position":5},"title":"Jugando con Redes Neuronales","author":"Daniel Fischer","date":"2016-04-18","format":false,"excerpt":"Hace unos d\u00edas escrib\u00ed sobre las redes neuronales\u00a0intentando explicar de manera simple como funcionan y por que este tipo de tecnolog\u00eda es llamado \"inteligencia artificial\". Lo importante de esta t\u00e9cnica y lo que la hace tan revolucionaria es el concepto de entrenamiento, pero muchas veces es dif\u00edcil imaginar como sucede\u2026","rel":"","context":"In "Uncategorized"","block_context":{"text":"Uncategorized","link":"https:\/\/geekosas.com\/index.php\/es\/category\/uncategorized-es\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/geekosas.com\/wp-content\/uploads\/2016\/04\/tensorflow.png?fit=1200%2C715&ssl=1&resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/geekosas.com\/wp-content\/uploads\/2016\/04\/tensorflow.png?fit=1200%2C715&ssl=1&resize=350%2C200 1x, https:\/\/i0.wp.com\/geekosas.com\/wp-content\/uploads\/2016\/04\/tensorflow.png?fit=1200%2C715&ssl=1&resize=525%2C300 1.5x, https:\/\/i0.wp.com\/geekosas.com\/wp-content\/uploads\/2016\/04\/tensorflow.png?fit=1200%2C715&ssl=1&resize=700%2C400 2x, https:\/\/i0.wp.com\/geekosas.com\/wp-content\/uploads\/2016\/04\/tensorflow.png?fit=1200%2C715&ssl=1&resize=1050%2C600 3x"},"classes":[]}],"_links":{"self":[{"href":"https:\/\/geekosas.com\/index.php\/wp-json\/wp\/v2\/posts\/3139","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/geekosas.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/geekosas.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/geekosas.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/geekosas.com\/index.php\/wp-json\/wp\/v2\/comments?post=3139"}],"version-history":[{"count":8,"href":"https:\/\/geekosas.com\/index.php\/wp-json\/wp\/v2\/posts\/3139\/revisions"}],"predecessor-version":[{"id":3174,"href":"https:\/\/geekosas.com\/index.php\/wp-json\/wp\/v2\/posts\/3139\/revisions\/3174"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/geekosas.com\/index.php\/wp-json\/wp\/v2\/media\/3158"}],"wp:attachment":[{"href":"https:\/\/geekosas.com\/index.php\/wp-json\/wp\/v2\/media?parent=3139"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/geekosas.com\/index.php\/wp-json\/wp\/v2\/categories?post=3139"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/geekosas.com\/index.php\/wp-json\/wp\/v2\/tags?post=3139"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}