probleme_8_dames.py

Created on July 15, 2025
5.99 KB
Le problème des 8 dames consiste à placer 8 dames sur un échiquier sans qu’elles ne se menacent mutuellement. Chaque dame menace toute dame qui est sur la même ligne ou sur la même colonne ou sur la même diagonale.
Dans la première phase du jeu, on place une dame dans chaque colonne. Dans la seconde phase, on déplace les dames dans leur colonne respective, pour trouver la solution.
from kandinsky import *
from ion import *
from time import *

def dessine_dame(x,y,clr):
  #fill_rect(10+dX,10+dY,10,10,clr)
  if rectangle==True:
    dX=60+5+25*x
    dY=3+5+25*y
    fill_rect(dX,dY,16,16,clr)
  else:
    dX=60+5+25*x
    dY=3+1+int(25*y)
    fill_rect(dX+7,dY+1,2,2,clr)
    fill_rect(dX+5,dY+3,2,1,clr)
    fill_rect(dX+9,dY+3,2,1,clr)
    fill_rect(dX+4,dY+4,2,1,clr)
    fill_rect(dX+10,dY+4,2,1,clr)
    fill_rect(dX+1,dY+5,2,1,clr)
    fill_rect(dX+4,dY+5,3,1,clr)
    fill_rect(dX+9,dY+5,3,1,clr)
    fill_rect(dX+13,dY+5,2,1,clr)
    fill_rect(dX+2,dY+6,3,1,clr)
    fill_rect(dX+6,dY+6,4,1,clr)
    fill_rect(dX+11,dY+6,3,1,clr)
    fill_rect(dX+3,dY+7,1,2,clr)
    fill_rect(dX+7,dY+7,2,1,clr)
    fill_rect(dX+12,dY+7,1,2,clr)
    fill_rect(dX+4,dY+9,1,2,clr)
    fill_rect(dX+11,dY+9,1,2,clr)
    set_pixel(dX+5,dY+11,clr)
    set_pixel(dX+10,dY+11,clr)
    fill_rect(dX+4,dY+12,8,1,clr)
    fill_rect(dX+3,dY+13,10,1,clr)
    fill_rect(dX+5,dY+14,1,3,clr)
    fill_rect(dX+10,dY+14,1,3,clr)
    fill_rect(dX+4,dY+17,1,3,clr)
    fill_rect(dX+11,dY+17,1,3,clr)
    set_pixel(dX+3,dY+20,clr)
    set_pixel(dX+12,dY+20,clr)
    fill_rect(dX+2,dY+21,12,1,clr)
    fill_rect(dX+1,dY+22,14,1,clr)
  
def dessine_curseur(x,y,clr):
  dX=60+1+25*x
  dY=3+1+25*y
  for k in (0,1):
    fill_rect(dX,dY+23*k,23,1,clr)
    fill_rect(dX+23*k,dY,1,24,clr)
    fill_rect(dX,dY+22*k,4,2,clr)
    fill_rect(dX+20,dY+22*k,4,2,clr)
    fill_rect(dX+22*k,dY,2,4,clr)
    fill_rect(dX+22*k,dY+20,2,4,clr)

def resolu(positions):
  NB_menaces=0
  for p1 in range(7):
    for p2 in range(p1+1,8):
      if positions[p1] == positions[p2]: # 2 dames sur la même ligne
        NB_menaces+=1
      if (p1-p2)**2 == (positions[p1]-positions[p2])**2: # 2 dames sur la même diagonale
        NB_menaces+=1
  return not NB_menaces

def actualise_plateau():
  for i in range(8):
    for j in range(8):
      NB_menaces=1
      for p in range(8):
        if positions[p] == j:
          NB_menaces += 1
        if (p-i)**2 == (positions[p]-j)**2:
          NB_menaces += 1
      fill_rect(60+1+25*i,3+1+25*j,24,24,(155,255+20-20*min(4,NB_menaces),255+20-20*min(4,NB_menaces)))

  for p1 in range(8):
    dessine_dame(p1,positions[p1],"b")
  for p1 in range(7):
    for p2 in range(p1+1,8):
      if positions[p1] == positions[p2]: # 2 dames sur la même ligne
        dessine_dame(p1,positions[p1],"r")
        dessine_dame(p2,positions[p2],"r")
      if (p1-p2)**2 == (positions[p1]-positions[p2])**2: # 2 dames sur la même diagonale
        dessine_dame(p1,positions[p1],"r")
        dessine_dame(p2,positions[p2],"r")

rectangle=False

draw_string("Problème des 8 dames",60,80,"purple")
draw_string("Valider avec OK",85,130,"purple")
for k in range(2): 
  fill_rect(60,50+k*122,200,1,"g")

for k in range(8):
  dessine_dame(-1+3*(k%4),7*(k//4)+0.4,"brgbbgrb"[k])
#for carte in Pioche:
#  DessineCarte(8,20,carte)
#  sleep(1)
#  DessineCarte(8,20,carte,effacement=True)
while not (keydown(KEY_EXE) or keydown(KEY_OK)):1
while keydown(KEY_EXE) or keydown(KEY_OK):1

while 1:
  fill_rect(0,0,320,222,"w")

  #draw_string("Maximiser le nombre de jetons !",3,50,"purple")
  draw_string("Présentation",100,10,(80,150,50))
  Regles=("Il faut placer les 8 dames","sans qu'elles ne se menacent","mutuellement : maximum une","dame par ligne, par colonne","ou sur une même diagonale.","Déplacer les pièces avec OK.")
  for k in range(len(Regles)):
    draw_string(Regles[k],20,33+18*k,"b")

  draw_string("Forme des dames : ",35,160,"b")
  draw_string("<   >",223,160,"r")
  draw_string("Valider avec OK",85,192,"purple")


  # choix du dessin des dames
  chg=1
  rectangle=True
  while not (keydown(KEY_EXE) or keydown(KEY_OK)):
    if chg:
      dessine_dame(7,6,"w")
      rectangle = not rectangle
      dessine_dame(7,6,"b")
      sleep(0.2)
    chg=keydown(KEY_RIGHT)-keydown(KEY_LEFT)
  while keydown(KEY_EXE) or keydown(KEY_OK):1
    

  fill_rect(0,0,320,222,"w")

  for i in range(9):
    fill_rect(60+25*i,3,1,200,"orange")
    fill_rect(60,3+25*i,201,1,"orange")

  positions=[-10 for k in range(8)]

  draw_string("Placer les dames",80,204,"b")

  T=monotonic()

  for k in range(8):
    X,Y=k,1
    chgY=-1
    while not (keydown(KEY_OK) or keydown(KEY_EXE)):
      if chgY:
        dessine_curseur(X,Y,get_pixel(60+3+25*X,3+3+25*Y))
        dessine_dame(X,Y,get_pixel(60+3+25*X,3+3+25*Y))
        Y=(Y+chgY)%8
        positions[k]=Y
        actualise_plateau()
        dessine_curseur(X,Y,"purple")
        sleep(0.2)
      chgY=keydown(KEY_DOWN)-keydown(KEY_UP)
    while keydown(KEY_OK) or keydown(KEY_EXE):1
    dessine_curseur(X,Y,get_pixel(60+3+25*X,3+3+25*Y))

  draw_string("Placer les dames",80,204,"w")

  draw_string("Déplacer les dames",70,204,"b")

  # curseur de sélection
  X,Y=7,0
  chgX,chgY=1,0

  while not resolu(positions):
    if chgX or chgY:
      dessine_curseur(X,Y,get_pixel(60+3+25*X,3+3+25*Y))
      X=(X+chgX)%8
      Y=(Y+chgY)%8
      dessine_curseur(X,Y,"purple")
      sleep(0.2)
    chgX=keydown(KEY_RIGHT)-keydown(KEY_LEFT)
    chgY=keydown(KEY_DOWN)-keydown(KEY_UP)

    if positions[X]==Y and (keydown(KEY_OK) or keydown(KEY_EXE)):
      dessine_curseur(X,Y,(80,150,50))
      dessine_dame(X,Y,(80,150,50))
      while keydown(KEY_OK) or keydown(KEY_EXE):1
      while not (keydown(KEY_OK) or keydown(KEY_EXE)):
        if chgY:
          #dessine_curseur(X,Y,"w")
          #dessine_dame(X,Y,"w")
          #X=(X+chgX)%8
          Y=(Y+chgY)%8
          positions[X]=Y
#          dessine_dame(X,Y,"g")
          actualise_plateau()
          dessine_curseur(X,Y,(80,150,50))
          sleep(0.2)
        #chgX=keydown(KEY_RIGHT)-keydown(KEY_LEFT)
        chgY=keydown(KEY_DOWN)-keydown(KEY_UP)
#      dessine_dame(X,Y,"b")
      actualise_plateau()
      dessine_curseur(X,Y,"b")
      while keydown(KEY_OK) or keydown(KEY_EXE):1

  draw_string("Déplacer les dames",70,205,"w")
  draw_string("Problème résolu en "+str(int(monotonic()-T))+" sec !",20,204,"b")
  while not (keydown(KEY_EXE) or keydown(KEY_OK)):1
  while keydown(KEY_EXE) or keydown(KEY_OK):1