<br><font size=2 face="sans-serif">I should have added some more :-) :-)
to my note (and not mentioned Cplex).</font>
<br>
<br><font size=2 face="sans-serif">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 :-)</font>
<br>
<br><font size=2 face="sans-serif">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.</font>
<br>
<br><font size=2 face="sans-serif">John Forrest</font>
<br>
<br>
<br>
<table width=100%>
<tr valign=top>
<td width=40%><font size=1 face="sans-serif"><b>Thorsten Koch <koch@zib.de></b>
</font>
<br><font size=1 face="sans-serif">Sent by: coin-lpsolver-bounces@list.coin-or.org</font>
<p><font size=1 face="sans-serif">11/24/2005 12:38 PM</font>
<table border>
<tr valign=top>
<td bgcolor=white>
<div align=center><font size=1 face="sans-serif">Please respond to<br>
koch</font></div></table>
<br>
<td width=59%>
<table width=100%>
<tr>
<td>
<div align=right><font size=1 face="sans-serif">To</font></div>
<td valign=top><font size=1 face="sans-serif">coin-lpsolver@list.coin-or.org</font>
<tr>
<td>
<div align=right><font size=1 face="sans-serif">cc</font></div>
<td valign=top>
<tr>
<td>
<div align=right><font size=1 face="sans-serif">Subject</font></div>
<td valign=top><font size=1 face="sans-serif">[Coin-lpsolver] Sudoku as
IP</font></table>
<br>
<table>
<tr valign=top>
<td>
<td></table>
<br></table>
<br>
<br>
<br><font size=2><tt>> Message: 2<br>
> Date: Thu, 24 Nov 2005 07:12:49 -0500<br>
> From: John J Forrest <jjforre@us.ibm.com><br>
> Subject: [Coin-lpsolver] New branching ideas for Cbc<br>
> Cc: coin-lpsolver@list.coin-or.org<br>
> Message-ID:<br>
> <OF1293B673.B49751B7-ON052570C3.003A1216-052570C3.0043151E@us.ibm.com><br>
> Content-Type: text/plain; charset="us-ascii"<br>
> <br>
> One reason for going to Cbc version 1.00 was to imply a more measured
set <br>
> of changes. One exception I made was that of adding new branching
classes <br>
> etc.<br>
> <br>
> I wanted to see if I could implement a Constraint Programming idea
such as <br>
> "All Different" into Cbc; also I had been asked to make
sure N-way <br>
> branching worked. Finally Irv Lustig had asked - "What
can you do with <br>
> Cbc that you can't do with Cplex?". On the way back from
INFORMS I was <br>
> sitting next to a person solving Su Doku puzzles and I thought - can
you <br>
> write a Su Doku solver with Cplex?<br>
> <br>
> If you live in the UK you must know what a Su Doku puzzle is, for
some <br>
> others - for a 9 x 9 Su Doku puzzle you fill it in using numbers 1
to 9 <br>
> and each row and column must be all different as must the obvious
3x3 <br>
> squares.<br>
> <br>
> I have implemented CbcBranchAllDifferent which stops two general integer
<br>
> variables being the same by imposing two branches x <= y-1 and
x >= y+1. <br>
> Obviously users can modify this to obtain their own cut branch rules.
I <br>
> have also put in a CglAllDifferent cut generator which fixes variables
<br>
> based on the above logic. I may improve the speed of this later.<br>
> <br>
> I found that this was not sufficient to do well at the Independent
super <br>
> Su Doku puzzles (16x16) for which there is a prize. This is
because <br>
> general integer variables at a bound are not enough for the logical
<br>
> fixing. So I have implemented N way branching so that we can
fix the <br>
> general integer variables more easily. And while I was at it
I added a <br>
> trivial CglStored cut class where the user can put any cuts and then
have <br>
> them added in if they are violated and the obvious AllDifferent row
cuts <br>
> could go there. To see more look at the sudoku.cpp example in
<br>
> Cbc/Samples. There is also a simple nway.cpp example.<br>
> <br>
Why doing so much work to solve Sudoku? <br>
I mean to have all-different is nice,<br>
but if you model Sudoku with binary<br>
variables any IP-Solver will easily solve them.<br>
In many cases in the preprocessor.<br>
<br>
Using the model below, I solved about 3000 Sudokus. <br>
I am still looking for a single instance were CPLEX has <br>
to branch to solve it. <br>
(If anybody has such an instance I would be <br>
interested to get it, preferable in line, i.e. ---5---678----8--3... format".<br>
<br>
param p := 3;<br>
<br>
set I := { 1 .. p*p };<br>
set M := { 1 .. p};<br>
<br>
var x[I * I * I] binary;<br>
<br>
# file: row col value<br>
set F := { read "sudoku.dat" as "<1n,2n,3n>"
comment "#" };<br>
<br>
subto c1: forall <i,j> in I*I do sum <k> in I : x[i,j,k] ==
1;<br>
subto c2: forall <j,k> in I*I do sum <i> in I : x[i,j,k] ==
1;<br>
subto c3: forall <i,k> in I*I do sum <j> in I : x[i,j,k] ==
1;<br>
<br>
subto c4: forall <m,n,k> in M*M*I do <br>
sum <i,j> in M*M : x[(m-1)*p+i,(n-1)*p+j,k] == 1;<br>
<br>
# Fix the fixed values<br>
subto c5: forall <i,j,k> in F do x[i,j,k] == 1;<br>
<br>
Best regards,<br>
Thorsten Koch<br>
<br>
_______________________________________________<br>
Coin-lpsolver mailing list<br>
Coin-lpsolver@list.coin-or.org<br>
http://list.coin-or.org/mailman/listinfo/coin-lpsolver<br>
</tt></font>
<br>