Canvas 2D

Letzte Änderung: 12.01.2016

Umgesetzte Punkte

  • Canvas 2D
  • Rekursion

Acht Damen Problem

Verteilung von acht Damen ohne gegenseitige Schlagmöglichkeit.

Leider unterstützt Ihr Browser das canvas-Element nicht.


<canvas id="playground" height=50 width=50></canvas>
<script>
function showInHtml ()
{
  var firstColumn = document.getElementById("column").selectedIndex;

  init(firstColumn);
  findPosition(1);
  paintArea(document.getElementById("playground"));
}
document.getElementById("berechnen").onclick = showInHtml;
</script>
  

achtdamen.js

download
/**
 * @description Suchen der Positionen von acht Damen auf einem Schachbrett
 * Nach dem finden einer Position ohne gegenseitige Schlagmöglichkeit wird 
 * die Suche beendet.
 * Für die erste Spalte ist die Position der Dame vorgebbar.
 * 
 * @author Thomas Thielemann www.th-thielemann.de
 */

var m_queens = [0, 0, 0, 0, 0, 0, 0, 0];    //!< Position der Damen innerhalb einer Spalte
var m_moveCounter = 0;                      //!< Anzahl der benötigten Züge    

/**
 * Werte zurücksetzen
 * @param firstColumn Position 0...7 in der ersten Spalte
 */
function init(firstColumn)
{
  m_queens = [0, 0, 0, 0, 0, 0, 0, 0];
  if (0 <= firstColumn && firstColumn < 8) {
    m_queens[0] = firstColumn;
  }
  m_moveCounter = 0;    
}

/**
 * Spielfeld zeichnen
 * @param element Canvas Element
 */
function paintArea(element)
{
    if (! element) {
        console.log("Context 2d is not supported.");
        return;
    }
    var ctx = element.getContext('2d');
        
    ctx.font = "16px sans-serif";
    var size = element.height / 9;
    for (var row = 0; row < 8; ++row) {
        ctx.fillStyle = "#222222";
        ctx.fillText(8 - row, 10, (size * row) + size - 10);
        for (var col = 1; col < 9; ++col) {
            ctx.fillStyle = ((row + col) % 2) === 0 ? "#222222" : "#CCCCCC";
            ctx.fillRect(size * col, size * row, size, size);
        }
    }              
    ctx.fillStyle = "#222222";
    for (var col = 1; col < 9; ++col) {
        ctx.fillText(String.fromCharCode(64 + col), size * col + size/2, (size * 8) + size/2);
    }
    for (var row = 0; row < 8; ++row) {
        ctx.fillStyle = "#FF2222";
        ctx.beginPath();
        ctx.arc(size * row + 1.5 * size, size * (m_queens[row]) + 0.5 * size, size / 2.2, 0, 6.3, true);
        ctx.fill();
        ctx.closePath();
        ctx.fillStyle = "#222222";
        ctx.beginPath();
        ctx.arc(size * row + 1.5 * size, size * (m_queens[row]) + 0.5 * size, size / 2.6, 0, 6.3, true);
        ctx.fill();
        ctx.closePath();
        ctx.fillStyle = "#FF2222";
        ctx.beginPath();
        ctx.arc(size * row + 1.5 * size, size * (m_queens[row]) + 0.5 * size, size / 3.0, 0, 6.3, true);
        ctx.fill();
        ctx.closePath();
        ctx.fillStyle = "#222222";
        ctx.beginPath();
        ctx.arc(size * row + 1.5 * size, size * (m_queens[row]) + 0.5 * size, size / 3.4, 0, 6.3, true);
        ctx.fill();
        ctx.closePath();
        ctx.fillStyle = "#FF2222";
        ctx.beginPath();
        ctx.arc(size * row + 1.5 * size, size * (m_queens[row]) + 0.5 * size, size / 4.0, 0, 6.3, true);
        ctx.fill();
        ctx.closePath();
    }              
}  

/**
 * Überprüfe die Position der Dame
 * @param queenIndex Index der Dame innerhalb von m_queens
 * @return Position ist gültig
 */
function checkQueen(queenIndex)
{
    var queenColumn = queenIndex;
    var queenRow = m_queens[queenIndex];

    // Steht in den Feldern links von der Dame eine andere Dame?
    for (var row = 0; row < queenColumn; ++row) {
        if (m_queens[row] === queenRow) {
            return false;
        }
    }
    // Steht in den Feldern diagonal nach links unten von der Dame eine andere Dame?
    while (0 <= queenColumn && 0 <= queenRow) {
        --queenColumn;
        --queenRow;
        if (m_queens[queenColumn] === queenRow) {
            return false;
        }
    }

    // Steht in den Feldern diagonal nach links oben von der Dame eine andere Dame?
    queenColumn = queenIndex;
    queenRow = m_queens[queenIndex];
    while (0 <= queenColumn && queenRow < 8) {
        --queenColumn;
        ++queenRow;
        if (m_queens[queenColumn] === queenRow) {
            return false;
        }
    }
    return true;
}

/**
 * Gültige Position einer Dame in der Spalte \c column finden
 * @param column Zu überprüfende Spalte 0...7
 * @returns {Boolean}
 */
function findPosition(column)
{        
    ++m_moveCounter;
    if (column === 8) { // End der Rekursion
        return checkQueen(7);
    }

    while(m_queens[column] < 8) {
        paintArea();
        if (checkQueen(column) && findPosition(column + 1)) {
            return true;
        } else {      
            ++m_moveCounter;
            m_queens[column] = m_queens[column] + 1; // Gehe zum nächsten Feld
        }
    }
    m_queens[column] = 0; // Nicht erfolgreich, Position zurücksetzen
    return false;
}




© 2003-2017 th-thielemann.de