Planning problems & sudoku

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

Planning problems & sudoku

Postby evert » Fri Sep 23, 2005 4:32 pm

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

Code: Select all
        mtwtf  mtwtf  mtwtf  mtwtf
evert   000X0  00XX0  000XX  00!00
peter   0!XX0  XXX00  X0000  XX00X
eddy    000!0  00X00  XXXXX  XX0XX
jeffrey 000XX  X!XX0  0XXX0  00X00
mary    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: 187
Joined: 26 August 2005

Re: Planning problems & sudoku

Postby dukuso » Fri Sep 23, 2005 4:43 pm

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


Return to General