## Planning problems & sudoku

Everything about Sudoku that doesn't fit in one of the other sections

### Planning problems & sudoku

Few days ago I tried to exchange a duty with a colleague:

Code: Select all
`        mtwtf  mtwtf  mtwtf  mtwtfevert   000X0  00XX0  000XX  00!00peter   0!XX0  XXX00  X0000  XX00Xeddy    000!0  00X00  XXXXX  XX0XXjeffrey 000XX  X!XX0  0XXX0  00X00mary    0X00X  XX!XX  000XX  00X00! = scheduled/0 = available/X = not available`

The only person I could exchange with was peter because he
had time available on the day of my duty and vice versa.

So in the scheme I had to look for a square like
Code: Select all
`0..!!..0`

This is a very little bit similar to finding subsudoku's in sudoku grids
like 1-9 with c1r1-c5r8:
Code: Select all
`1;7;4;5;9;6;8;2;3;5;6;2;8;3;4;7;9;1;3;8;9;1;7;2;4;6;5;4;9;3;6;5;1;2;7;8;7;2;5;9;4;8;1;3;6;8;1;6;7;2;3;5;4;9;2;5;1;4;6;9;3;8;7;9;4;8;3;1;7;6;5;2;6;3;7;2;8;5;9;1;4;`

Does this give a connection between sudoku maths and scheduling and planning problems?
evert

Posts: 186
Joined: 26 August 2005

### Re: Planning problems & sudoku

evert wrote:Does this give a connection between sudoku maths and scheduling and planning problems?

these are very similar.
You can convert a sudoku into a constraint satisfaction problem
or an exact cover problem
or a SAT-instance

and then use some standard software to solve it.

The same is done with planning, scheduling problems etc.
dukuso

Posts: 479
Joined: 25 June 2005