If you are looking for a high school-level book, you might consider The Mathematics of Choice: Or, How to Count Without Counting by Ivan Niven. I don't think it covers coverings of chessboards, so far as I can recall, but it covers all the other topics in your list. You can buy the book direct from the Mathematical Association of America: http://www.maa.org/publications/maa-reviews/mathematics-of-choice-or-how-to-count-without-counting
This book was my first introduction to combinatorics, way back when I was in high school, and I remember it fondly.
Well as a former math contestant I wanted to share my thoughts on this question.
First and foremost you have to understand that the competition and the result you'll achieve are by no means a measurement of your mathematical ability. A very nice example is a friend of mine. In my life I've participated in about 40 math contests (regional, county, national, international and even IMO). Since my friend was the same age as me, he also participated in all this contests and he was simply dominant. I mean of the 40 or so contests I've participated in he was better ranked in all of them, as far as I can remember. Actually there were around 10 instances when I was second only to him (few times we were tied, simply because both of us had perfect scores). So you would say that he was a better mathematician than me. Well, I believe that's not the case. We both chased a math degree on university and he had problems with topics that were not required for math competitions, such as calculus, differential equations... So at the end he decided to give up on math and he started studying computer science. So because of this I believe that he was the better math competitor of the two, but not the better mathematician. So the math competitions certainly help you to develop your math genius, but your success (or failure) there doesn't necessary translates to your further math career.
Since I come from a relatively small country, I noticed that we failed miserably at almost every international competition (both on individual and team scale). So I tried to investigate and find out why this is happening. Certainly the fact that the talent pool in my country is small plays a big role. On every international contest there are countries that have 100 to 500 times more population than my country, so I guess there is a greater probability that a math genius will be born in let say USA or China than in my country. But this wasn't the only reason. Compared to countries as big as mine, we still had very bad results. So I talked to other contestants and I asked them what's their formula to success. What I found out was astonishing.
Since our country is small, we believe that we have a deficit of talents, so we try to make up for it by practicing and practicing. So we learn a lot of theory and techniques. Actually when I asked some of the guys that won a gold or silver medal at the IMO, they had little or no clue about some techniques. That suprised me. But unlike in my country, where there are only 4 contests per year(regional, county, national and selection test), other countries have 15-20 contests or at least "friendly" contest (where students solve problems in an IMO athmosphere, but they receive no awards for the results). So I concluded that although I (simularly as every contestant in my country) had much more theoretical knowledges I failed to put it in practice or to implement it in a solution. But with the expereince they had others don't have this problem. So I would say that experience is as important as practice. So maybe the reason why you couldn't solve a Olympiad problem is because you didn't participate in math contest as a youngster.
Also what I found out is that most of the successful math contestant have a "competition mindset", i.e. they go on compeitions and they do their work for 4.5 hours. So as a competitor I wasn't able to establish this mindset in me, so what usualy was happening to me is that I was great on preparations camps or when I was practising and I was able to solve some tough IMO problems by myself. But when I was at the IMO I wasn't able to recreate the same success and I believe that was because of the pressure that I was feeling and of course the time constraint.
So since now occasionally I'm working with young math talents in the first few classes I teach them about this mental thing and I want them to get this "competition mindset", before the procede to learning techniques and "tricks" if they want to be successful on math contests.
Best Answer
Here is a list of books for perfect olympiad combinatorics preparation.
For general study:
(1) A Path to Combinatorics for Undergraduates
(2) Principles and Techniques in Combinatorics
(3) Problem-Solving Methods in Combinatorics: An Approach to Olympiad Problems
For practising problem-solving:
(1) 102 Combinatorial Problems
(2) Combinatorics: A Problem-Based Approach
(3) The IMO Compendium: A Collection of Problems Suggested for The International Mathematical Olympiads: 1959-2009 Second Edition
For Olympiad Graph theory:
Olympiad uses of graph theory is a bit different from formal graph theory taught in university courses. The best book for this is
(1) Graph Theory: In Mathematical Olympiad And Competitions
(2) IMO Training 2008: Graph Theory
For probabilistic methods in olympiad combinatorics:
(1) Expected uses of probability
(2) Unexpected uses of probability
For generating functions and recurrence relations:
Generatingfunctionology
For combinatorial inequality type problems:
Combinatorial Extremization
For various advanced techniques:
Extremal Combinatorics
For elementary combinatorial problems with geometric flavour:
Elementary Combinatorial Geometry
For ultimate problem solving (hard):
Problems from the Book
Pranav A. Sriram's book contains more than enough higher combinatorics contents which are only needed to tackle notoriously difficult (but not so elegant) Chinese TST problems. But what I have listed is enough for achieving success in EGMO or even in IMO!
Happy Problem Solving!