[Coin-lpsolver] Sudoku as IP

[John J Forrest]

I should have added some more :-) :-) to my note (and not mentioned 
Cplex).

The purpose was to test N way branching and cut branching - not really to 
obtain a Su Doku solver.  In fact I find it slightly worrying that such 
things exist :-)

I agree all the 9 x 9 examples in newspapers could be made to solve at 
root node.  The 16 x 16 I tried did not (using 0-9,A-F) but I was not 
using strongest formulation as I wanted some branching.

John Forrest



Thorsten Koch <koch at zib.de> 
Sent by: coin-lpsolver-bounces at list.coin-or.org
11/24/2005 12:38 PM
Please respond to
koch


To
coin-lpsolver at list.coin-or.org
cc

Subject
[Coin-lpsolver] Sudoku as IP






> Message: 2
> Date: Thu, 24 Nov 2005 07:12:49 -0500
> From: John J Forrest <jjforre at us.ibm.com>
> Subject: [Coin-lpsolver] New branching ideas for Cbc
> Cc: coin-lpsolver at list.coin-or.org
> Message-ID:
> <OF1293B673.B49751B7-ON052570C3.003A1216-052570C3.0043151E at us.ibm.com>
> Content-Type: text/plain; charset="us-ascii"
> 
> One reason for going to Cbc version 1.00 was to imply a more measured 
set 
> of changes.  One exception I made was that of adding new branching 
classes 
> etc.
> 
> I wanted to see if I could implement a Constraint Programming idea such 
as 
> "All Different" into Cbc; also I had been asked to make sure N-way 
> branching worked.  Finally Irv Lustig had asked - "What can you do with 
> Cbc that you can't do with Cplex?".  On the way back from INFORMS I was 
> sitting next to a person solving Su Doku puzzles and I thought - can you 

> write a Su Doku solver with Cplex?
> 
> If you live in the UK you must know what a Su Doku puzzle is, for some 
> others - for a 9 x 9 Su Doku puzzle you fill it in using numbers 1 to 9 
> and each row and column must be all different as must the obvious 3x3 
> squares.
> 
> I have implemented CbcBranchAllDifferent which stops two general integer 

> variables being the same by imposing two branches x <= y-1 and x >= y+1. 

> Obviously users can modify this to obtain their own cut branch rules.  I 

> have also put in a CglAllDifferent cut generator which fixes variables 
> based on the above logic.  I may improve the speed of this later.
> 
> I found that this was not sufficient to do well at the Independent super 

> Su Doku puzzles (16x16) for which there is a prize.  This is because 
> general integer variables at a bound are not enough for the logical 
> fixing.  So I have implemented N way branching so that we can fix the 
> general integer variables more easily.  And while I was at it I added a 
> trivial CglStored cut class where the user can put any cuts and then 
have 
> them added in if they are violated and the obvious AllDifferent row cuts 

> could go there.  To see more look at the sudoku.cpp example in 
> Cbc/Samples.  There is also a simple nway.cpp example.
> 
Why doing so much work to solve Sudoku? 
I mean to have all-different is nice,
but if you model Sudoku with binary
variables any IP-Solver will easily solve them.
In many cases in the preprocessor.

Using the model below, I solved about 3000 Sudokus. 
I am still looking for a single instance were CPLEX has 
to branch to solve it. 
(If anybody has such an instance I would be 
interested to get it, preferable in line, i.e. ---5---678----8--3... 
format".

param p := 3;

set I := { 1 .. p*p };
set M := { 1 .. p};

var x[I * I * I] binary;

# file: row col value
set F := { read "sudoku.dat" as "<1n,2n,3n>" comment "#" };

subto c1: forall <i,j> in I*I do sum <k> in I : x[i,j,k] == 1;
subto c2: forall <j,k> in I*I do sum <i> in I : x[i,j,k] == 1;
subto c3: forall <i,k> in I*I do sum <j> in I : x[i,j,k] == 1;

subto c4: forall <m,n,k> in M*M*I do 
   sum <i,j> in M*M : x[(m-1)*p+i,(n-1)*p+j,k] == 1;

# Fix the fixed values
subto c5: forall <i,j,k> in F do x[i,j,k] == 1;

Best regards,
Thorsten Koch

_______________________________________________
Coin-lpsolver mailing list
Coin-lpsolver at list.coin-or.org
http://list.coin-or.org/mailman/listinfo/coin-lpsolver

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/clp/attachments/20051127/d523c754/attachment.html>