Tu peux t´en sortir avec conio.h en effet 
C´est de la que vient textcolor :
avec ça, tu manipules le texte, et déplace le curseur ou tu veux, ce qui fait que tu peux écrire n´importe ou a n´importe quel moment
Conio.h est a utiliser sous DOS/windows
alors que twk te propose ncurses, qui est sous linux.
Apres, pour les algos je te conseille de te faire un tableau bidimentionnel de bits ( met des chars, pour te simplifier), représentant le statut du jeu, quant aux pieces, a toi de les prédéfinir !
Je te laisse réfléchir la dessus !