Latin & Euler squares
I love these puzzles! They are visually appealing, with bright colours and distinct shapes rather than numbers or letters; they require puzzlers to be very clear about which rules they are using; there are thousands of solutions for each level; and solutions can be found via many approaches.
Children are often quicker than adults at finding solutions,which makes them feel justifiably proud of their abilities. Even kindergarten students pick up on the idea, although you might want to start them with 3×3 grids. Once they understand the goal, they often progress quite quickly through several levels.
Also, many other puzzles become accessible once one has internalised the idea of a Latin square. Examples include Futoshiki, Kenken, Towers, Neighbours, and Kakurasu. Sudoku fans will find the idea familiar, as Sudoku is a combination of Latin squares.
Latin square puzzles are best done with pieces of coloured paper or craft foam, as everyone seems to find colour attractive and non-threatening. They can be done with just numbers or letters, but I don’t recommend it to start with.
Euler squares (“oiler”) are Latin squares with two attributes, say colour and shape. They are also known as Graeco-Latin squares because Euler, who seems to have invented them, used two types of letters, Greek and Roman, in each square. That is really hard to see! It was once a popular game to construct Euler squares with regular playing cards, using four cards (say Ace, Joker, Queen, King) in each of the four suits.
For teachers: this is how I usually introduce the puzzles to groups of people.