In the last article there were two Sudoku puzzles where the first one was relatively straight forward but the second one was harder!

What was the difference between solving them?  For me as a non-mathematician the differences were:

1 – Time, the second one took me longer!

2 – I had to guess at times on the second one (and then check my work)!

Just to re-iterate I’m no maths genius and haven’t had a maths lesson for pushing 30 years but to put it into something maths framework:

Sudoku is what is known as a NP problem!

Which basically means it might take time and effort to solve but once it’s solved it’s pretty quick to check that it’s correct.

For all you the mathematically minded people then think of P problems (easily solved by computers) and NP problems which aren’t easily solvable, but if you present a potential solution it’s easy to verify whether it’s correct or not.

So, all P problems are NP problems.

Hold up, Chris – getting a bit technical there!  Let’s put it back into timetabling terms; given time a timetable (schedule) can be generated and it’s easy to check (verify) that it doesn’t break any rules.

That’s great then, the computer/software will generate a timetable for me.  Well yes and no – timetabling is classed as NP-Hard which again for the mathematicians out there will know what that means or you can have a Google.  To try to contextualise what a NP-Hard problem is let’s take a classic NP-hard problem the Travelling Sales Man and have a bit of fun.  The following example if taken from the book ‘The Millennium Problems’ by Keith Devlin

Chris is now a Travelling sales man and is based in City A but has customers in Cities B, C and D to which he has to visit all of them.  To save time and petrol, it makes sense to plan a route so that the total distance travelled is as short as possible.

Here is a table that shows the distance between then cities

Due to one-way systems some journeys aren’t the same distance it all depends on the direction of travel.

Task – order the three cities to minimise distance travelled.

Below is a table showing the different routes i.e. row one is City A to City B, leave City B to go to City C etc

From the table above you can see the shortest route is 249 miles

The number of combinations you had to test was 3 * 2 * 1 = 6 (ignore City A as that is your start/finish).

The above task was relatively straight forward, bit like the Sudoku – given a bit of time and thought and it was completed in five minutes.  Having spent five minutes you get a call saying that City B doesn’t need a visit, but City E has become a prospect.  City E is 45 miles away from City A (in both directions).

How do you feel about this?  Does it impact on your answer/route?

Putting this into real-life timetabling, when you are scheduling you are working on a specific set of data and parameters, if after a days’ worth of work should the data and/or parameters change it might force you to start again!

10 City – salesperson

Let’s up the stakes a bit; If you had a salesperson who had to visit 10 cities then the number of solutions is 10 factorial i.e. 10! Which means

10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 3,628,800

Wow I’m not drawing that out in a table and working out myself!

Can you see where I’m going with this?  How about 100 cities?  We’re in the realms of the number is so great that not even a super-computer can explore and compute them all.

But Chris, this seems a little complicated.  Yes, understanding or trying to quantify the problem is quite complicated but all I can say is for people like me it just means timetabling is a tough task which no computer can look through all the combinations (and check them) in a sensible time!  I’ve been timetabling for the last 20 years and not needed to understand any of the maths so fear not everyone can timetable.  To me it’s having the understanding/strategy correct and as the computer can’t explore all combinations it’s about working in partnership i.e. break the task up and let the computer look at smaller problems.

People might disagree with what I’m going to say but for many schools the software can’t just create a valid timetable given all your constraints i.e let’s type in all our data and press the Schedule button.  Or it can’t create a valid timetable in a sensible timeframe.  All software works in different ways, so treat my text as general thoughts.

Any questions please just ask or more information about the services we offer please click your software solution below.