MODULE NumberPuzzle; (* Find a 9 digit number containing the digits 1 to 9 once and only once such that the first 1 digit is a multiple of 1, the first 2 digits form a number that is a multiple of 2, the first 3 digits form a number that is a multiple of 3, etc... *) (* John Andrea, Dec.11/91 *) (* This code may be freely used and distributed, it may not be sold. *) FROM InOut IMPORT WriteString, WriteCard, WriteLn; VAR digit_taken :ARRAY [1..9] OF BOOLEAN; attempts, solutions, i :CARDINAL; (* -------------------------------------------------- *) PROCEDURE TrySolve( value, level :CARDINAL ); VAR i :CARDINAL; BEGIN attempts := attempts + 1; (* does the value so far satisfy the conditions *) IF value MOD level = 0 THEN (* ok, it works so far *) IF level = 9 THEN (* all digits taken, this must be a solution *) solutions := solutions + 1; WriteCard( value, 0 ); WriteLn; ELSE (* try all the available digits *) FOR i := 1 TO 9 DO IF NOT digit_taken[i] THEN digit_taken[i] := TRUE; TrySolve( value * 10 + i, level + 1 ); digit_taken[i] := FALSE; END; END; END; END; END TrySolve; BEGIN attempts := 0; solutions := 0; FOR i := 1 TO 9 DO digit_taken[i] := FALSE; END; WriteString( 'Starting to solve the puzzle...' ); WriteLn; WriteLn; FOR i := 1 TO 9 DO digit_taken[i] := TRUE; TrySolve( i, 1 ); digit_taken[i] := FALSE; END; WriteLn; IF solutions = 0 THEN WriteString( 'impossible' ); ELSE WriteCard( solutions, 0 ); WriteString( ' solutions' ); END; WriteLn; WriteString( 'after ' ); WriteCard( attempts, 0 ); WriteString( ' attempts' ); WriteLn; END NumberPuzzle.