Acht dames probleem

Het acht dames vraagstuk

Bij dit vraagstuk gaat het erom dat je acht dames op een schaakbord zet, zo dat ze elkaar niet kunnen slaan. Je kunt dit vraagstuk heel gemakkelijk met je Arduino oplossen! Met het veel verkochte 8 bij 8 display kun je al een mooie uitvoering maken die alle oplossingen laat zien. Ook maken we een uitvoering waarmee je zelf kunt proberen een oplossing te vinden, mar dat is nog niet klaar.

Regels

De oplossing 04752613

Een dame kan een ander stuk slaan op het schaakbord als dat stuk in dezelfde rij of kolom of op dezelfde diagonaal staat. Als je dus acht dames hebt dan volgt hieruit dat in elke rij precies één dame staat. Een makkelijke manier om een oplossing weer te geven is dat je alleen de positie van de dame in de kolom weergeeft. De oplossing 15863724 betekent dat de eerste dame op het eerste vakje staat in de eerste kolom en de volgende dame in het vijfde vakje van de volgende kolom, en zo verder. Je kunt rijen en kolommen verwisselen, dan blijft de oplossing geldig. In werkelijkheid begint men meestal met 0 te tellen, de oplossing wordt dan 04752613.

Test programma

Als eerste wil je natuurlijk weten of de Arduino alle oplossingen kan vinden en vooral hoe snel. Hiertoe heb ik een sketch gemaakt. Open de seriële monitor van de Arduino als je alle oplossingen wilt zien. Ik heb dit getest met de Arduino nano: geen enkel probleem. Je kunt ook een kijken hoeveel oplossingen er zijn met een kleiner schaakbord. Verklein daartoe de waarde van N boven in het programma.

Klik hier om dit testprogramma te zien

// Dit programma laat alle oplossingen van het 8 (of minder) dames probleem zien
#define N 8 // Je mag N kleiner maken, maar niet groter 

void setup() {
  Serial.begin(9600);
  probeer(0);
  Serial.println("Alle oplossingen zijn berekend.");
}

byte Plaats[N]; // Declareer N plaatsen

bool isVrij(int dame_nr, int doelPlaats) // Ga na of je de dame mag plaatsen
{
  for (int i = 0; i < dame_nr; i++) // Controleer alle eerder geplaatste dames
  {
    int eerderePlaats = Plaats[i]; // De plaats van een andere dame
    if ( eerderePlaats == doelPlaats || // Ga na of ze in dezelfde rij
         eerderePlaats == doelPlaats - (dame_nr - i) || // of diagonaal /
         eerderePlaats == doelPlaats + (dame_nr - i) )  // of diagonaal \ zitten
       return false;
  }
  return true;
}

int nr = 1;
void probeer(int k) {
  if (k == N) { // Alle dames zijn geplaatst !
    Serial.print("Oplossing "); Serial.print(nr); Serial.print(": ");
    for (int i = 0; i < N; i++) Serial.print(Plaats[i]);
    Serial.println(); nr++;
  }
  else {
    for (int i = 0; i < N; i++) { // Bekijk alle mogelijkheden
      if ( isVrij(k, i) ) { // Voordat we dame nr. k in een rij zetten controleren we of dat mag
        Plaats[k] = i; // Het mag, dus plaats de dame
        probeer(k + 1); // Zoek een plaats voor de volgende dame
      }
    }
  }
}

void loop() {
}

Een schaakbord met dames

Een oplossing...

Een 8×8 display is erg geschikt om een schaakbord mee te simuleren. Een display met een MAX7219 chip is hier erg geschikt voor. Sluit het display aan op VCC en GND en verder volgens de tekst in de sketch hieronder. Om het geheel nog mooier te maken kun je een afbeelding van een schaakbord uitprinten met een grootte van ca 31×31 mm. Print dit op fotopapier en knip de afbeelding van het schaakbord aan twee kanten iets te ruim uit zodat je het om het display kunt vouwen. Je kunt nu allerlei varianten maken.

Een schaakbord waarop automatisch alle oplossingen komen

Dit schaakbord laat steeds een oplossing zien, wacht dan twee seconden en laat dan de volgende zien. Om aan te geven dat alle 92 oplossingen voorbij zijn gekomen wordt er even een kort "splash screen" (fantasiescherm) getoond. Uiteraard kun je dit en alle wachttijden zelf gemakkelijk aanpassen naar je eigen smaak.

Klik hier om de sketch te zien

// Alle oplossingen voor het 8 dames probleem
#include "LedControl.h"
#define DataIn 12 // Data In (DIN) van het display gaat naar pin 12
#define CLK 11 // De klok (CLK) van het display gaat naar pin 11
#define CS 10 // Chip Select van het display gaat naar pin 10
#define N 8 
LedControl lc = LedControl(DataIn, CLK, CS); 

void setup() {
  lc.shutdown(0, false); lc.setIntensity(0, 7); lc.clearDisplay(0);
}

byte Plaats[N]; // Declareer N plaatsen

bool isVrij(int dame_nr, int doelPlaats) // Ga na of je de dame mag plaatsen
{
  for (int i = 0; i < dame_nr; i++) // Controleer alle eerder geplaatste dames
  {
    int eerderePlaats = Plaats[i];
    if (eerderePlaats == doelPlaats || // Ga na of ze in dezelfde rij
      eerderePlaats == doelPlaats - (dame_nr - i) || // of diagonaal /
      eerderePlaats == doelPlaats + (dame_nr - i))   // of diagonaal \ zitten
      return false;
  }
  return true;
}
int nr = 1;
void probeer(int k)
{
  if (k == N) // Alle dames zijn geplaatst !
  {
    for (int i = 0; i < N; i++) lc.setRow(0, i, 1 << Plaats[i]);
    delay(2000);
  }
  else
  {
    for (int i = 0; i < N; i++) // Bekijk alle mogelijkheden
    {  
      if (isVrij(k, i)) { // Voordat we dame nr. k in een rij zetten controleren we of dat mag
        Plaats[k] = i;  // Het mag, dus plaats de dame
        probeer(k + 1); // Zoek een plaats voor de volgende dame
      }
    }
  }
}

void loop() {
  probeer(0);
// Een fantasiescherm om aan te geven dat alle oplossingen weergegeven zijn
  lc.clearDisplay(0);
  lc.setRow( 0, 3, B00011000 );
  lc.setRow( 0, 4, B00011000 );
  delay(400);
  lc.setRow( 0, 2, B00111100 );
  lc.setRow( 0, 3, B00100100 );
  lc.setRow( 0, 4, B00100100 );
  lc.setRow( 0, 5, B00111100 );
  delay(400);
  lc.setRow( 0, 1, B01111110 );
  lc.setRow( 0, 2, B01000010 );
  lc.setRow( 0, 3, B01011010 );
  lc.setRow( 0, 4, B01011010 );
  lc.setRow( 0, 5, B01000010 );
  lc.setRow( 0, 6, B01111110 );
  delay(400);
  lc.setRow( 0, 0, B11111111 );
  lc.setRow( 0, 1, B10000001 );
  lc.setRow( 0, 2, B10000001 );
  lc.setRow( 0, 3, B10011001 );
  lc.setRow( 0, 4, B10011001 );
  lc.setRow( 0, 5, B10000001 );
  lc.setRow( 0, 6, B10000001 );
  lc.setRow( 0, 7, B11111111 );
  delay(3000);
}

Schaakbord met een knop

Nu met rode knop, liggend display en Arduino nano 168

In deze variant moet je op een knop drukken om de volgende oplossing te krijgen. De sketch verandert hierdoor nauwelijks. Zet de knop tussen een digitale of analoge pin, bijvoorbeeld A5, en aarde. Als je in de sketch test of de knop is ingedrukt dan komen er een heleboel oplossingen voorbij. Daarom heb ik een klein delay ingevoerd. Hoe groot dat delay moet zijn hangt af van de drukknop en enkele andere factoren, maar een halve seconde is meestal goed. Door de ongelukkige plaatsing van de pinnen is niet mogelijk een liggend display geheel op het breadboard te plaatsen. Als je zo'n display als doe-het-zelf pakket hebt, dan zou je de uitvoerpinnen kunnen weglaten, waardoor het display wel mooi te plaatsen is. Elk display heeft zijn eigen instelling, waardoor je misschien elke oplossing gespiegeld of op zijn kop ziet. Dat maakt niets uit. Je zult altijd alle oplossingen één keer tegenkomen.

Klik hier om de sketch te zien

// Alle oplossingen voor het 8 dames probleem
#include "LedControl.h"
#define DataIn 12 // Data In (DIN) van het display gaat naar pin 12
#define CLK 11 // De klok (CLK) van het display gaat naar pin 11
#define CS 10 // Chip Select van het display gaat naar pin 10
#define N 8 
#define Knop A5 // Kies een vrije analoge of digitale pin voor de drukknop
LedControl lc = LedControl(DataIn, CLK, CS); 

void setup() {
  pinMode(Knop, INPUT_PULLUP); // Dit houdt de input hoog als de knop niet ingedrukt is
  lc.shutdown(0, false); lc.setIntensity(0, 7); lc.clearDisplay(0);
}

byte Plaats[N]; // Declareer N plaatsen

bool isVrij(int dame_nr, int doelPlaats) // Ga na of je de dame mag plaatsen
{
  for (int i = 0; i < dame_nr; i++) // Controleer alle eerder geplaatste dames
  {
    int eerderePlaats = Plaats[i];
    if (eerderePlaats == doelPlaats || // Ga na of ze in dezelfde rij
      eerderePlaats == doelPlaats - (dame_nr - i) || // of diagonaal /
      eerderePlaats == doelPlaats + (dame_nr - i))   // of diagonaal \ zitten
      return false;
  }
  return true;
}
int nr = 1;
void probeer(int k)
{
  if (k == N) // Alle dames zijn geplaatst !
  {
    for (int i = 0; i < N; i++) lc.setRow(0, i, 1 << Plaats[i]);
    while (digitalRead(Knop) == HIGH); // Wacht tot knop is ingedrukt
    delay(500); // Anders gaat de berekening te snel en zie je alle uitkomsten na elkaar
  }
  else
  {
    for (int i = 0; i < N; i++) // Bekijk alle mogelijkheden
    {  
      if (isVrij(k, i)) { // Voordat we dame nr. k in een rij zetten controleren we of dat mag
        Plaats[k] = i;  // Het mag, dus plaats de dame
        probeer(k + 1); // Zoek een plaats voor de volgende dame
      }
    }
  }
}

void loop() {
  probeer(0);
// Een fantasiescherm om aan te geven dat alle oplossingen weergegeven zijn
  lc.clearDisplay(0);
  lc.setRow( 0, 3, B00011000 );
  lc.setRow( 0, 4, B00011000 );
  delay(400);
  lc.setRow( 0, 2, B00111100 );
  lc.setRow( 0, 3, B00100100 );
  lc.setRow( 0, 4, B00100100 );
  lc.setRow( 0, 5, B00111100 );
  delay(400);
  lc.setRow( 0, 1, B01111110 );
  lc.setRow( 0, 2, B01000010 );
  lc.setRow( 0, 3, B01011010 );
  lc.setRow( 0, 4, B01011010 );
  lc.setRow( 0, 5, B01000010 );
  lc.setRow( 0, 6, B01111110 );
  delay(400);
  lc.setRow( 0, 0, B11111111 );
  lc.setRow( 0, 1, B10000001 );
  lc.setRow( 0, 2, B10100101 );
  lc.setRow( 0, 3, B10011001 );
  lc.setRow( 0, 4, B10011001 );
  lc.setRow( 0, 5, B10100101 );
  lc.setRow( 0, 6, B10000001 );
  lc.setRow( 0, 7, B11111111 );
}

Ik heb alleen deze varianten klaar. De rest komt hopelijk snel.