I bought a book The Five Day course in Thinking by the author Edward de Bono when I was at University. It included a seemingly very simple two player strategy game called The L Game. If you’ve heard of the phrase Lateral Thinking that was invented by him back in 1967.
On a 4 x 4 board there are two L shapes and two neutral single pieces. To win you just have to move your L shape and (optionally) one of the neutral pieces so that your opponent can’t move his L shape.
I’ve had a cursory search for C source versions of this game and there are bound to be more than the one I found which was written for an Arduino WifiBoy Pro. There’s a downloadable zip file which contains a file wbpro_chess_L.ino. Despite the extension, it is a C source code text file.
If you are looking for an interesting programming problem then create a computer opponent for a game. The good thing about this is, its so simple graphics wise that you could draw the board in a console with B = Blue, R = red and 1 and 2 the two neutral pieces like this.
1RR. .BR. .BR. .BB2