{"id":3216,"date":"2026-05-16T16:03:46","date_gmt":"2026-05-16T14:03:46","guid":{"rendered":"https:\/\/geekosas.com\/?p=3216"},"modified":"2026-05-16T16:17:17","modified_gmt":"2026-05-16T14:17:17","slug":"3216","status":"publish","type":"post","link":"https:\/\/geekosas.com\/index.php\/2026\/05\/16\/3216\/","title":{"rendered":"Sudoku"},"content":{"rendered":"

The first question on my first optimization exam was to formulate a mathematical model for solving a Sudoku puzzle. Well, at that moment I made a huge mistake: I included nonlinear constraints, which resulted in a score of 0. And since this was one of my favorite subjects, I\u2019ve always remembered that bad experience.<\/p>\n

That\u2019s why I\u2019m here today to correct that past mistake.<\/p>\n

A Sudoku is a puzzle game with very simple rules, but honestly, I find it difficult to solve. It consists of a 9×9 grid where some cells contain numbers while others are empty. The puzzle involves filling in each row and each column with the numbers 1 through 9 without repeating them.<\/p>\n

The above condition must also be met for each of the 3×3 squares in the following image, where you can see the puzzle and its solution on the right:<\/p>\n

\"\"<\/p>\n

Well, mathematically this can be formulated as follows, and I\u2019ll show how to program the same thing in Python using PuLP. At the end, I\u2019ll put all the code in a GIT repository<\/p>\n

Initialize the mathematical problem
\nprob = pulp.LpProblem(\u201cprob\u201d, pulp.LpMaximize)<\/code><\/p>\n

Indices:<\/h4>\n

Row f \\in 1..9<\/code>
\nrow = [x for x in range(9)]<\/code>
\nColumn c \\in 1..9<\/code>
\ncol = [x for x in range(9)]<\/code>
\nValue v \\in 1..9<\/code>
\nval = [x for x in range(9)]<\/code><\/p>\n

Decision variables<\/h4>\n

G_{f,c,v} \\in [0,1]<\/code> where 1 means that the value v is assigned to row f, column c.<\/p>\n

game = [[[pulp.LpVariable(cat =\u2018Binary\u2019, name =\u2018row {}, col {} is {}\u2019.format(f, c, v+1)) for f in row] for c in colum] for v in val]<\/code><\/pre>\n
Parameters<\/h4>\n
P_{f,c,v} \\in [0,1]<\/code> where 1 means that the value v must be assigned to row f, column c.<\/p>\n
wb = load_workbook(\u201csudoku.xlsx\u201d, 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
Objective Function<\/h4>\n
max \\sum_{f,c,v} G_{f,c,v}<\/code> Maximize the sum of assigned values<\/p>\n
prob += pulp.lpSum(game)<\/code><\/pre>\n
Constraints:<\/h4>\n
The puzzle must be satisfied<\/h5>\n
\\forall f,c,v  G_{f,c,v}  \\ge P_{f,c,v}<\/code><\/p>\n
for f,c,v in product(row,col,val):\n    prob += game[f][v] >= puzzle[f][v]<\/code><\/pre>\n
Each cell can only contain one value<\/h5>\n
\\forall f,c  \\sum_v G_{f,c,v}  \\le 1<\/code><\/p>\n
for f,c in product(row,col):\n    prob += pulp.lpSum([game[f][v] for v in val]) <= 1<\/code><\/pre>\n
Each row can contain each value only once<\/h5>\n
\\forall f,v  \\sum_c G_{f,c,v}  \\le 1<\/code><\/p>\n
for f,v in product(row,val):\n    prob += pulp.lpSum([game[f][v] for c in colum]) <= 1<\/code><\/pre>\n
Each column can contain each value only once<\/h5>\n
\\forall c,v  \\sum_f G_{f,c,v}  \\le 1<\/code><\/p>\n
for c,v in product(row,val):\n    prob += pulp.lpSum([game[f][v] for f in row]) <= 1<\/code><\/pre>\n
Each quadrilateral must have each value exactly once<\/h5>\n
cc = index of the quadrilateral in the column
\ncf = index of the quadrilateral in the row
\nf = row of the quadrilateral
\nc = column of the quadrilateral
\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
Solve the problem and obtain results<\/h4>\n
solver = pulp.getSolver(\u2018PULP_CBC_CMD\u2019)\nprob.solve(solver)\n\nsol = [[0 for k in range(9)] for j in range(9)]\nfor f,c,v in product(row,colum,val):\n    if(pulp.value(game[f][v]) > 0.9):\n        sol[f] = v + 1\n\nfor f in row:\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
Which is the same as the example:
\n\"\"<\/p>\n
You can find the complete code on my GitHub:
\nhttps:\/\/github.com\/danielfm123\/sudoku_solver<\/a><\/p>\n
Best regards!<\/p>\n
Translated with DeepL.com (free version)<\/p>\n","protected":false},"excerpt":{"rendered":"
The first question on my first optimization exam was to formulate a mathematical model for solving a Sudoku puzzle. Well, at that moment I made […]<\/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_feature_clip_id":0,"_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-3216","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-3216","jetpack-related-posts":[{"id":3271,"url":"https:\/\/geekosas.com\/index.php\/2016\/05\/23\/metroidvania-games\/","url_meta":{"origin":3216,"position":0},"title":"Metroidvania Games","author":"Daniel Fischer","date":"2016-05-23","format":false,"excerpt":"When I was a kid, around 10 years old, I first put a new cartridge I had received for Christmas into my beloved Super Nintendo. This game was very strange: it was an orange character that appeared from a spaceship and could go in any direction. There were no stages,\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\/metroidvania.png?fit=799%2C318&ssl=1&resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/geekosas.com\/wp-content\/uploads\/2016\/04\/metroidvania.png?fit=799%2C318&ssl=1&resize=350%2C200 1x, https:\/\/i0.wp.com\/geekosas.com\/wp-content\/uploads\/2016\/04\/metroidvania.png?fit=799%2C318&ssl=1&resize=525%2C300 1.5x, https:\/\/i0.wp.com\/geekosas.com\/wp-content\/uploads\/2016\/04\/metroidvania.png?fit=799%2C318&ssl=1&resize=700%2C400 2x"},"classes":[]},{"id":3227,"url":"https:\/\/geekosas.com\/index.php\/2026\/05\/13\/como-se-repartieron-los-votos-en-la-segunda-vuelta-en-chile\/","url_meta":{"origin":3216,"position":1},"title":"How were the votes distributed in the runoff election in Chile?","author":"Daniel Fischer","date":"2026-05-13","format":false,"excerpt":"Acknowledgments: I would like to begin this article by thanking Hernan Aburto (huaburto@gmail.com) for his assistance. We worked together to refine the model and polish the conclusions. His version of the article on his blog: https:\/\/www.grialprofano.cl\/flyto\/97\/que-paso-con-los-votos-de-la-primera-vuelta-en-el-balotaje\/ How were the votes distributed? In the most recent elections held on Sunday, December\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\/2021\/12\/FRCN3F5FY6BYLWSLIY4NSVWH5E.jpg?fit=900%2C600&ssl=1&resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/geekosas.com\/wp-content\/uploads\/2021\/12\/FRCN3F5FY6BYLWSLIY4NSVWH5E.jpg?fit=900%2C600&ssl=1&resize=350%2C200 1x, https:\/\/i0.wp.com\/geekosas.com\/wp-content\/uploads\/2021\/12\/FRCN3F5FY6BYLWSLIY4NSVWH5E.jpg?fit=900%2C600&ssl=1&resize=525%2C300 1.5x, https:\/\/i0.wp.com\/geekosas.com\/wp-content\/uploads\/2021\/12\/FRCN3F5FY6BYLWSLIY4NSVWH5E.jpg?fit=900%2C600&ssl=1&resize=700%2C400 2x"},"classes":[]},{"id":3238,"url":"https:\/\/geekosas.com\/index.php\/2026\/05\/12\/back-to-office-post-covid19-2\/","url_meta":{"origin":3216,"position":2},"title":"Back to Office Post-Covid19","author":"Daniel Fischer","date":"2026-05-12","format":false,"excerpt":"Before starting this article I want to thank Tristan Riquelme for giving me the idea, he is someone who always has excellent ideas about where to apply mathematical tools to real problems. Now starting with the article: Although we find a definitive cure for COVID-19, it has already created cultural\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\/2021\/09\/dressed_0617-780x710-1.jpg?fit=780%2C710&ssl=1&resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/geekosas.com\/wp-content\/uploads\/2021\/09\/dressed_0617-780x710-1.jpg?fit=780%2C710&ssl=1&resize=350%2C200 1x, https:\/\/i0.wp.com\/geekosas.com\/wp-content\/uploads\/2021\/09\/dressed_0617-780x710-1.jpg?fit=780%2C710&ssl=1&resize=525%2C300 1.5x, https:\/\/i0.wp.com\/geekosas.com\/wp-content\/uploads\/2021\/09\/dressed_0617-780x710-1.jpg?fit=780%2C710&ssl=1&resize=700%2C400 2x"},"classes":[]},{"id":3317,"url":"https:\/\/geekosas.com\/index.php\/2017\/05\/23\/who-voted-for-each-candidate-chilean-elections-2017\/","url_meta":{"origin":3216,"position":3},"title":"Who voted for each candidate? (Chilean Elections 2017)","author":"Daniel Fischer","date":"2017-05-23","format":false,"excerpt":"Last Sunday, the president of Chile was elected, so many pundits tried to explain how the votes from the first round were distributed to the second round. Since the vote is secret, no one can be wrong. That is why I decided to take a different approach from the standard\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":3235,"url":"https:\/\/geekosas.com\/index.php\/2020\/05\/23\/best-practices-when-programming-with-code\/","url_meta":{"origin":3216,"position":4},"title":"Best Practices When Programming (with code)","author":"Daniel Fischer","date":"2020-05-23","format":false,"excerpt":"Best Practices When Programming (with code) Many enjoy programming and solving algorithmic mazes in their favorite language, but what nobody likes is diving into old code or even worse, code written by someone else. I've had to do it several times, sometimes it was bad, other times worse, many times\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\/2022\/05\/logo.png?fit=1200%2C600&ssl=1&resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/geekosas.com\/wp-content\/uploads\/2022\/05\/logo.png?fit=1200%2C600&ssl=1&resize=350%2C200 1x, https:\/\/i0.wp.com\/geekosas.com\/wp-content\/uploads\/2022\/05\/logo.png?fit=1200%2C600&ssl=1&resize=525%2C300 1.5x, https:\/\/i0.wp.com\/geekosas.com\/wp-content\/uploads\/2022\/05\/logo.png?fit=1200%2C600&ssl=1&resize=700%2C400 2x, https:\/\/i0.wp.com\/geekosas.com\/wp-content\/uploads\/2022\/05\/logo.png?fit=1200%2C600&ssl=1&resize=1050%2C600 3x"},"classes":[]},{"id":3232,"url":"https:\/\/geekosas.com\/index.php\/2026\/05\/11\/hasta-cuanto-sabe-contar-el-ordenador-2\/","url_meta":{"origin":3216,"position":5},"title":"How well can a computer count?","author":"Daniel Fischer","date":"2026-05-11","format":false,"excerpt":"My 2-year-old son knows how to count up to 10; after that he starts to \u201cimprovise,\u201d so I can say he knows how to count up to 10. With computers it is similar: if you repeatedly add 1 to a number, eventually the PC will make a mistake. Yes, the\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\/2021\/10\/vocab-10256-counting.jpg?fit=800%2C460&ssl=1&resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/geekosas.com\/wp-content\/uploads\/2021\/10\/vocab-10256-counting.jpg?fit=800%2C460&ssl=1&resize=350%2C200 1x, https:\/\/i0.wp.com\/geekosas.com\/wp-content\/uploads\/2021\/10\/vocab-10256-counting.jpg?fit=800%2C460&ssl=1&resize=525%2C300 1.5x, https:\/\/i0.wp.com\/geekosas.com\/wp-content\/uploads\/2021\/10\/vocab-10256-counting.jpg?fit=800%2C460&ssl=1&resize=700%2C400 2x"},"classes":[]}],"_links":{"self":[{"href":"https:\/\/geekosas.com\/index.php\/wp-json\/wp\/v2\/posts\/3216","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=3216"}],"version-history":[{"count":5,"href":"https:\/\/geekosas.com\/index.php\/wp-json\/wp\/v2\/posts\/3216\/revisions"}],"predecessor-version":[{"id":3221,"href":"https:\/\/geekosas.com\/index.php\/wp-json\/wp\/v2\/posts\/3216\/revisions\/3221"}],"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=3216"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/geekosas.com\/index.php\/wp-json\/wp\/v2\/categories?post=3216"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/geekosas.com\/index.php\/wp-json\/wp\/v2\/tags?post=3216"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}