Fondamenti di Informatica - Ingegneria per l'Ambiente e il Territorio - A.A. 97/98

- Quarta esercitazione in laboratorio -

Si consideri il seguente problema: dato un intero positivo n, riempire le n2 celle di una scacchiera n ´ n con i numeri 1, 2, …, n2, rispettando le due seguenti regole:

  1. l’intero 1 può essere posizionato in una cella arbitraria;
  2. se l’intero k è posizionato nella cella (i,j) allora l’intero k+1 può essere posizionato in una e solo una delle seguenti celle: (i,j+3), (i+2,j+2), (i+3,j), (i+2,j-2), (i,j-3), (i-2,j-2), (i-3,j), (i-2,j+2).

Un esempio è il seguente, per n = 6.

1

21

30

2

22

29

35

26

18

36

25

17

14

32

23

28

31

3

6

20

10

7

19

11

34

27

15

33

24

16

13

8

5

12

9

4

Ciò premesso:

Esercizio 4.1

Scrivere un programma in C, che, letti un intero positivo n e una matrice A di interi Î {1,2,…, n2}, stabilisca se A costituisce una soluzione del problema proposto.

Esercizio 4.2

Scrivere un programma in C, che, letto un intero positivo n, calcoli e stampi una soluzione del problema proposto o, in assenza di soluzione, stampi un apposito messaggio.