The map-colouring problem (which is a constraint satisfaction problem) is often solved using the backtracking search. The backtracking search has the following functions: SELECT-UNASSIGNED-VARIABLE ORDER-DOMAIN-VALUES INFERENCE Variables: WA, NT, Q, NSW, V, SA, T Domains: Di={red,green,blue} Constraints: adjacent regions must have different colours.

1) SELECT-UNASSIGNED-VARIABLE

WA is coloured with red and NT with green. Before the assignment to the rightmost state, which state (region) should be chosen and what principle is used to do so? [2 marks]

2) ORDER-DOMAIN-VALUES

WA is coloured with red and NT with green. What colour should be chosen for Queensland and what principle is used to do so? [2 marks]

NT Northern Territory Queensland WA Western Australia South Australia SA NSW) New South Wales Victoria V Tasmania T