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

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
Posted 6 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
Attachments:
POSTED BY: Raspi Rascal

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: Sam Carrettie

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

POSTED BY: Frank Kampas
POSTED BY: Sam Carrettie

enter image description here - you have earned "Featured Contributor" badge, congratulations!

This is a great post and it has been selected for the curated Staff Picks group. Your profile is now distinguished by a "Featured Contributor" badge and displayed on the "Featured Contributor" board.

POSTED BY: Moderation Team

yes, I tried Reduce[ allcons, vars, Integers ].

POSTED BY: Frank Kampas

Difficult for me to comment in the absence of actual code. If it was something like this Reduce[allcons, vars, Integers]; I will agree: exact ILP can be slow. That's why I often write branch-and-prune loops using NMinimize.

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

using Unequal constraints or Integer Programming?

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

It would be nice if Reduce applied this technique automatically.

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
POSTED BY: Frank Kampas

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
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract