Group Abstract Group Abstract

Message Boards Message Boards

Solving Sudoku as an integer programming problem

Attachments:
POSTED BY: Frank Kampas
19 Replies

This post is referenced here: "Applying Artificial Intelligence and Machine Learning to Finance and Technology".

(⚠️ : shameless plug.)

POSTED BY: Anton Antonov
Posted 7 years ago

Single line Sudoku solver: https://rosettacode.org/wiki/Sudoku#Mathematica

solve[sudoku_] := 
 NestWhile[
  Join @@ Table[
     Table[ReplacePart[s, #1 -> n], {n, #2}] & @@ 
      First@SortBy[{#, 
           Complement[Range@9, s[[First@#]], s[[;; , Last@#]], 
            Catenate@
             Extract[Partition[s, {3, 3}], Quotient[#, 3, -2]]]} & /@ 
         Position[s, 0, {2}], 
        Length@Last@# &], {s, #}] &, {sudoku}, ! FreeQ[#, 0] &]
POSTED BY: Toomas Tahves

Yep, that is a true algorithm (original by whose author?). Pretty concise. Solves even faster than the mathematical BILP solution. And it also spits out all other solutions, if there are more than 1 solutions to the puzzle. You can substitute the function NestWhileList to see the iterations and how it generates the alternate solutions for the output.

A one-liner! Absolutely mind-blowing. Uses multiple multi-nested pure functions and only basic vocab items. I once tried to dissect/modularize the code and create an annotated 13-liner from it, but failed to do so big time. If i do not understand why the code does the what, to what end, it is impossible to …erh… understand it, duh.

So never mind the dissection or modularization. I don't understand the other Sudoku algorithms in C, C++, Matlab, Python, JavaScript, etc (which are 13-liners or longer) either, and i am not interested at all in understanding Sudoku solving algorithms because I am ignorant hehe. I only understand Frank's method; too bad that it spits out only one solution to the puzzle when alternate solutions exist.

POSTED BY: Raspi Rascal

Much clever thought went into your solution, thanks for sharing! I did not understand at first, what and why was happening in your code and i had to refresh my memory on numerical optimization. Understanding now the principle of your algorithm (maybe it cannot be called an algorithm because it is just setting up the maths to be solved by the solver in 1 step), i actually cannot think of any other alternative sensible way of solving the sudoku puzzle on a computer. I believe that there are many different ways (actual algorithms!) which solve the sudoku puzzle on a computer, e.g. working with permutations and such. But i always wanted to fully understand just one way of getting there, and if it is a mathematical way, the better. And yours is a purely mathematical way, solving a huge system of equations!!

To not lose my train of thought, i've edited your *.nb-file (minor code rearrangements and improvements, added explanations) and am sharing it here as well, please see attached.

Hope this helps, God bless!

Attachments:
POSTED BY: Raspi Rascal

Very cool. I see this post is trending now on Reddit-Programming: https://redd.it/5h1xgq There is a comment there mentioning MS-OML. Just for the sake of comparison i give their code that solves the problem. I wonder if we can learn anything form it.

Model
[
    Parameters[Sets,I,J],
    Parameters[Integers,d[I,J]],
    Decisions[Integers[1,9],x[I,J]],
    Constraints
    [
        FilteredForeach[{i,I},{j,J},d[i,j]>0,x[i,j]==d[i,j]],
        Foreach
        [{i,I},Unequal[Foreach[{j,J},x[i,j]]]],
            Foreach
            [{j,J},Unequal[Foreach[{i,I},x[i,j]]]],
                Foreach
                [{ib,3},
                    Foreach
                    [{jb,3},
                        Unequal[Foreach[{i,ib*3,ib*3+3},{j,jb*3,jb*3+3},x[i,j]
                    ]
                ]
            ]
        ]
    ]
]
POSTED BY: Sam Carrettie

I don't understand why the Foreach statements are nested in the MS-OML code.

POSTED BY: Frank Kampas

Don't shoot the messenger. I just reposted it here verbatim for easy access by Community folks. I do not understand MS-OML language at all. Perhaps some knowledgable folks would be able to comment.

POSTED BY: Sam Carrettie

I am not familiar with MS-OML but it seems clear enough what this particular nesting does. We'll look at one such.

"Foreach [{i,I},Unequal[Foreach[{j,J},x[i,j]]]]"

Taking this apart, for each i in the "row" subscript set, we set up an unequal involving ALL of {x[i,1],x[i,2],...x[i,9]}.

POSTED BY: Daniel Lichtblau
POSTED BY: EDITORIAL BOARD
POSTED BY: Frank Kampas

See also:

http://library.wolfram.com/infocenter/Conferences/6528/

Page 23 of the nb has an ILP-based sudoku solver.

POSTED BY: Daniel Lichtblau

It would be nice if Reduce applied this technique automatically.

POSTED BY: Frank Kampas

Reduce uses exact methods. Which might be somewhat slower than FindMinimum, but still should work for purposes of solving a Sudoku.

POSTED BY: Daniel Lichtblau

using Unequal constraints or Integer Programming?

POSTED BY: Frank Kampas
POSTED BY: Daniel Lichtblau

FindMinimum takes about 0.1 sec. Reduce does not return a solution after 10 minutes.

POSTED BY: Frank Kampas
POSTED BY: Daniel Lichtblau

That's a neat way of doing it! I actually wrote a solved on my last flight (a week ago or so) from USA back to Europe. I was having doubts with the in-flight entertainment system version of Sudoku; it generated non-unique Sudokus...so the puzzles had many many solutions... big shame. I'm still considering sending Delta airlines an email about it...

POSTED BY: Sander Huisman

Some years ago I wrote a "brute force" Sudoku solver which goes row by row, finding all possible solutions. It's in the Library Archive. The Integer programming method runs much faster. I also tried using Reduce with Unequal constraints as well but ran out of patience waiting for it to return.

POSTED BY: Frank Kampas
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard