Braces were introduced by Rump to study non-degenerate involutive set-theoretic solutions of the Yang-Baxter equation. We generalize Rump's braces to the non-commutative setting and use this new structure to study not necessarily involutive non-degenerate set-theoretical solutions of the Yang-Baxter equation. Based on results of Bachiller and Catino and Rizzo, we develop an algorithm to enumerate and construct classical and non-classical braces of small size up to isomorphism. This algorithm is used to produce a database of braces of small size. The paper contains several open problems, questions and conjectures.

16 pages, 6 tables. Title has changed. Final version. Accepted for publication in Mathematics of Computation