PROBLEMA 1:

Esta version del juego de Nim tiene un cierto parecido con la version que 
vimos en clase. Aunque el objetivo de este problema era una implementacion 
del tipo busqueda con retroceso, se puede tambien resolver de una forma 
matematica. Traten de demostrar por induccion que si N%5 es igual a 0 o 1 
entonces gana el segundo jugador y si es igual a 2, 3 o 4 gana el primero.

int nim23(int n)
{
  int gana = 0;

  if (n <= 1) return 0;
  if (n >= 2) gana = gana || !nim23(n-2);
  if (n >= 3) gana = gana || !nim23(n-3);
  return gana; /* 0 => gana el segundo, 1 => gana el primero */
}

PROBLEMA 2:

Definitivamente, lo mas facil es escribir una implementacion del tipo de 
busqueda con retroceso. Sin embargo, lo mas probable es que esta resulte 
demasiado lenta. Pueden notar que el juego es simetrico (es claro que se 
puede intercambiar M con N). En este juego "casi siempre" gana el primer 
jugador. Los menores valores de M y N que se necesitan para que gane el 
segundo jugador son (1, 2), (3, 5), (4, 7), (6, 10), (8, 13) y (9, 15). 
Este juego tambien se conoce como juego de Wythoff y tambien se puede 
resolver matematicamente http://mathworld.wolfram.com/WythoffsGame.html 
(por cierto, las cinco respuestas deben de ser "primer jugador gana").

int nimin(int m, int n)
{
  int i, gana = 0;

  if (n+m <= 0) return 0;
  for (i = 0; !gana && (i < m); i++)
    gana = gana || !nimin(i, n);
  for (i = 0; !gana && (i < n); i++)
    gana = gana || !nimin(m, i);
  for (i = 1; !gana && (i <= m) && (i <= n); i++)
    gana = gana || !nimin(m-i, n-i);
  return gana;
}

PROBLEMA 3:

Nuevamente, lo mas facil es usar busqueda con retroceso: podemos pensar 
que las casillas del tablero estan numeradas de la 1 a la N^2 (por ejemplo 
de izquierda a derecha y de arriba a abajo) y entonces intentamos poner 
rey por rey. Cada vez que lo logramos contamos una solucion y regresamos 
cada vez que no se puede colocar el siguiente rey. De cualquier forma, los 
menores valores se pueden intentar a mano para ver que todo va bien. Las 
respuestas correctas son: #[2,1] = 4, #[3,2] = 16, #[4,3] = 140, #[5,3] = 
964 y #[10,10] = 423677826986 (aunque no fue necesario calcular la ultima 
respuesta para evaluar el examen).

#include <stdio.h>

unsigned long long int sol = 0;

/* esta funcion revisa los vecinos de la casilla (i,j) */

int rey(int n, int i, int j, int t[12][12])
{
  int p;

  if (t[i-1][j]) return 0;
  for (p = i-1; p <= i+1; p++)
    if (t[p][j-1]) return 0;
  return 1;
}

/* esta funcion intenta poner k reyes a partir de la casilla (i,j) */

void reyes(int n, int i, int j, int t[12][12], int k)
{
  int p, q;

  if (k > 0) {
    for (q = j; q <= n; q++)
      for (p = 1; p <= n; p++)
        if (q > j || p >= i)
	  if (rey(n, p, q, t)) {
	    t[p][q] = 1;
	    reyes(n, p+2, q, t, k-1);
	    t[p][q] = 0;
	  }
  } else sol++;
}

int main(void)
{
  int i, j, n, k;
  int t[12][12];

  scanf("%d%d", &n, &k);
  for (i = 0; i <= n+1; i++)
    for (j = 0; j <= n+1; j++)
      t[i][j] = 0;
  reyes(n, 1, 1, t, k);
  printf("%llu\n", sol);
  return 0;
}

Hay un problema mucho mas facil que es el de determinar cual es el mayor 
valor de K para el que existe alguna solucion en un tablero de N por N. 
Este se conoce como el "problema de los reyes" y pueden aprender mas de el 
si visitan http://mathworld.wolfram.com/KingsProblem.html