The New Sudoku Players' Forum

[nickle]

It is possible to solve Sudoku problems by linear programming and the simplex algorithm.

The real problem is how to solve the uniqueness constraints of only having one example in each block, column or row of the digits.

For each cell, you need 9 integer variables taking the value 0 or 1.

One constraint is to have the sum of these come to 1, enforcing 1 digit per cell.

Similarly, you can do the same to make sure that only one 1 appears in each column, row or block.

The last part, making sure the totals come to 45 is again easy. just multiply the appropriate 0/1 number by the value of the digit, total and equate to 45.

Lastly there is the question of the known values. Here you can specify the appropriate values are 0 or 1 to force there use.

here are some examples of the constraints.

r111 is a variable, 0 or 1.

If its 1 then the cell (1,1) = 1, if its 0, then its another digit.

T11: r111 + r112 + r113 + r114 + r115 + r116 + r117 + r118 + r119 = 1;

This enforces the 1 digit per cell.

R1: 1 r111 + 2 r112 + 3 r113 + 4 r114 + 5 r115 + 6 r116 + 7 r117 + 8 r118 + 9 r119
+ 1 r121 + 2 r122 + 3 r123 + 4 r124 + 5 r125 + 6 r126 + 7 r127 + 8 r128 + 9 r129
+ 1 r131 + 2 r132 + 3 r133 + 4 r134 + 5 r135 + 6 r136 + 7 r137 + 8 r138 + 9 r139
+ 1 r141 + 2 r142 + 3 r143 + 4 r144 + 5 r145 + 6 r146 + 7 r147 + 8 r148 + 9 r149
+ 1 r151 + 2 r152 + 3 r153 + 4 r154 + 5 r155 + 6 r156 + 7 r157 + 8 r158 + 9 r159
+ 1 r161 + 2 r162 + 3 r163 + 4 r164 + 5 r165 + 6 r166 + 7 r167 + 8 r168 + 9 r169
+ 1 r171 + 2 r172 + 3 r173 + 4 r174 + 5 r175 + 6 r176 + 7 r177 + 8 r178 + 9 r179
+ 1 r181 + 2 r182 + 3 r183 + 4 r184 + 5 r185 + 6 r186 + 7 r187 + 8 r188 + 9 r189
+ 1 r191 + 2 r192 + 3 r193 + 4 r194 + 5 r195 + 6 r196 + 7 r197 + 8 r198 + 9 r199 = 45;

This is an example of a row constraint. Its the same format for columns and blocks.

CU11: r111 + r211 + r311 + r411 + r511 + r611 + r711 + r811 + r911 = 1;

This is an example enforcing that in column 1, there is only one 1

Lastly

K111: r111 = 0;
K112: r112 = 0;
K113: r113 = 0;
K114: r114 = 0;
K115: r115 = 0;
K116: r116 = 0;
K117: r117 = 1;
K118: r118 = 0;
K119: r119 = 0;

This enforces that in cell (1,1) the given digit is 7

I used a package called lpsolve to solve the solution. It takes about 7 seconds.

To generate the constraints, I used Python to read a small file containing the problem, and that generates the constraints file to solve.

To analyse and pretty print the solution, I used Excel.

Nick

[Tony Williams]

It is possible to solve Sudoku problems by linear programming and the simplex algorithm.

..~~~~~~~~~~~~~~...

I used a package called lpsolve to solve the solution. It takes about 7 seconds.

To generate the constraints, I used Python to read a small file containing the problem, and that generates the constraints file to solve.

To analyse and pretty print the solution, I used Excel.

Nick

I think I understand this, but is it sufficient to solve all the Puzzles, or only those for which your constraint rules are sufficient eg each Digit must occur once per row/col/SQ. Many of the more complex puzzles require recognition of patterns that exclude certain digits as 'candidates' for certain cells, but don't directly result in a decision. Following a set of 'exclusions' then the 'constraint rules' can be reapplied to see if the puzzle is solveable ?

Be very interested to have access to the code to give a go with more complex puzzles
Tony

[Guest]

Nickle,

Interesting stuff. In your R1:... constraint, why do you multiply each element by its digit? Could you just add them together (as per T11), at constrain it to 9?

[nickle]

R1 Constraint.

I think you are right. You don't need to multiply, just add and set a different rhs.

http://groups.yahoo.com/group/lp_solve/

is the group for lp solve.

This is the python program that generates the lpsolve file to be solved. I used the lpsolve gui to import and solve.

[PS I'm writting a little python framework to try different methods of solving. LP, Logic, brute force search, constrained search etc]

The problem file is in this format

Code: Select all

75..9..46
9.1...3.2
.........
2..6.1..7
.8.....2.
1..3.8..5
.........
3.9...2.4
84..3..79

Code: Select all

def WriteKnownVariables (f,fname):
    inf = open (fname,'r')
    for r in range (1,10):
        l = inf.readline()
        for c in range (1,10):
            if l[c-1] <> ".":
                for x in range (1,10):
                    if x == int(l[c-1]):
                        f.write ("K%d%d%d: r%d%d%d = 1;\n" % (r,c,x,r,c,x))
                    else:
                        f.write ("K%d%d%d: r%d%d%d = 0;\n" % (r,c,x,r,c,x))
   
def WriteObjective (f):
    f.write ( "min: ")
    f.write (";\n")

def WriteVariables (f):
    for r in range (1,10):
        for c in range (1,10):
            for x in range (1,10):
                f.write ( "int r%d%d%d;\n" % (r,c,x))

def WriteLowerBounds (f):
    for r in range (1,10):
        for c in range (1,10):
            for x in range (1,10):
                f.write ( "L%d%d%d: r%d%d%d >= 0;\n" % (r,c,x,r,c,x))

def WriteUpperBounds (f):
    for r in range (1,10):
        for c in range (1,10):
            for x in range (1,10):
                f.write ( "L%d%d%d: r%d%d%d <= 1;\n" % (r,c,x,r,c,x))

def WriteTotalBounds (f):
    for r in range (1,10):
        for c in range (1,10):
            f.write ("T%d%d: " % (r,c))
            for x in range (1,10):
                f.write ( "r%d%d%d" % (r,c,x))
                if x <> 9:
                    f.write ( " + " )
            f.write (" = 1;\n")
           
def WriteRowConstraints(f):
    for r in range (1,10):
        f.write ( "R%d: " % r)
        for c in range (1,10):
            for x in range (1,10):
                f.write ( "%d r%d%d%d" % (x,r,c,x))
                if x <> 9 or c <> 9:
                    f.write (" + ")
        f.write (" = 45;\n")

def WriteRowUniqueness(f):
    for r in range (1,10):
        for x in range (1,10):
            f.write ( "RU%d%d: " % (r,x))
            for c in range (1,10):
                f.write ( "r%d%d%d" % (r,c,x))
                if c <> 9:
                    f.write (" + ")
            f.write (" = 1;\n")

def WriteColConstraints(f):
    for c in range (1,10):
        f.write ( "C%d: " % c)
        for r in range (1,10):
            for x in range (1,10):
                f.write ( "%d r%d%d%d" % (x,r,c,x))
                if x <> 9 or r <> 9:
                    f.write (" + ")
        f.write (" = 45;\n")

def WriteColUniqueness(f):
    for c in range (1,10):
        for x in range (1,10):
            f.write ( "CU%d%d: " % (c,x))
            for r in range (1,10):
                f.write ( "r%d%d%d" % (r,c,x))
                if r <> 9:
                    f.write (" + ")
            f.write (" = 1;\n")

def WriteBoxConstraints(f):
    for x in range (0,3):
        for y in range (0,3):
            f.write ( "B%d: " % (3*x + y+1))
            for a in range (1,4):
                for b in range (1,4):
                    r = x * 3 + a
                    c = y * 3 + b
                    for z in range (1,10):
                        f.write ( "%d r%d%d%d" % (z,r,c,z))
                        if a <> 3 or a <> 3:
                            f.write ( " + " )
            f.write ( " = 45;\n" )

def WriteBoxUniqueness(f):
    for z in range (1,10):
        for x in range (0,3):
            for y in range (0,3):
                f.write ( "BU%d%d: " % ((3*x + y+1),z))
                for a in range (1,4):
                    for b in range (1,4):
                        r = x * 3 + a
                        c = y * 3 + b
                        f.write ( "r%d%d%d" % (r,c,z))
                        if a <> 3 or b <> 3:
                            f.write ( " + " )
                f.write ( " = 1;\n" )

f = open ('lp.lp','w')
WriteObjective(f)
WriteLowerBounds(f)
WriteUpperBounds(f)
WriteTotalBounds(f)
WriteRowConstraints(f)
WriteColConstraints(f)
WriteBoxConstraints(f)
WriteColUniqueness(f)
WriteRowUniqueness(f)
WriteBoxUniqueness(f)
WriteKnownVariables (f,'p77.txt')
WriteVariables(f)
f.close()