Skip to content

Instantly share code, notes, and snippets.

@SoundLogic

SoundLogic/knights-tour.html

Created November 28, 2014 21:26
Show Gist options
  • Save SoundLogic/49e783251567626a9bbd to your computer and use it in GitHub Desktop.
Save SoundLogic/49e783251567626a9bbd to your computer and use it in GitHub Desktop.
Download ZIP
javascript based solution for the Knight's Tour puzzle (http://en.wikipedia.org/wiki/Knight%27s_tour)
Raw
knights-tour.html
<html>
<head>
<style>
a {
color:#000;
display:block;
font-size:60px;
height:80px;
position:relative;
text-decoration:none;
text-shadow:0 1px #fff;
width:80px;
}
#chess_board { border:5px solid #333; }
#chess_board td {
background:#fff;
background:-moz-linear-gradient(top, #fff, #eee);
background:-webkit-gradient(linear,0 0, 0 100%, from(#fff), to(#eee));
box-shadow:inset 0 0 0 1px #fff;
-moz-box-shadow:inset 0 0 0 1px #fff;
-webkit-box-shadow:inset 0 0 0 1px #fff;
height:80px;
text-align:center;
vertical-align:middle;
width:80px;
}
#chess_board tr:nth-child(odd) td:nth-child(even),
#chess_board tr:nth-child(even) td:nth-child(odd) {
background:#ccc;
background:-moz-linear-gradient(top, #ccc, #eee);
background:-webkit-gradient(linear,0 0, 0 100%, from(#ccc), to(#eee));
box-shadow:inset 0 0 10px rgba(0,0,0,.4);
-moz-box-shadow:inset 0 0 10px rgba(0,0,0,.4);
-webkit-box-shadow:inset 0 0 10px rgba(0,0,0,.4);
}
.floatSvgOverHtml{
position:absolute;
top:0px;
left:0px;
}
</style>
</head>
<script src='http://d3js.org/d3.v3.min.js' type='text/javascript'></script>
<body>
<table z-index="10" id="chess_board" class="html" cellpadding="0" cellspacing="0">
<tr>
<td id="A8"></td>
<td id="B8"></td>
<td id="C8"></td>
<td id="D8"></td>
<td id="E8"></td>
<td id="F8"></td>
<td id="G8"></td>
<td id="H8"></td>
</tr>
<tr>
<td id="A7"></td>
<td id="B7"></td>
<td id="C7"></td>
<td id="D7"></td>
<td id="E7"></td>
<td id="F7"></td>
<td id="G7"></td>
<td id="H7"></td>
</tr>
<tr>
<td id="A6"></td>
<td id="B6"></td>
<td id="C6"></td>
<td id="D6"></td>
<td id="E6"></td>
<td id="F6"></td>
<td id="G6"></td>
<td id="H6"></td>
</tr>
<tr>
<td id="A5"></td>
<td id="B5"></td>
<td id="C5"></td>
<td id="D5"></td>
<td id="E5"></td>
<td id="F5"></td>
<td id="G5"></td>
<td id="H5"></td>
</tr>
<tr>
<td id="A4"></td>
<td id="B4"></td>
<td id="C4"></td>
<td id="D4"></td>
<td id="E4"></td>
<td id="F4"></td>
<td id="G4"></td>
<td id="H4"></td>
</tr>
<tr>
<td id="A3"></td>
<td id="B3"></td>
<td id="C3"></td>
<td id="D3"></td>
<td id="E3"></td>
<td id="F3"></td>
<td id="G3"></td>
<td id="H3"></td>
</tr>
<tr>
<td id="A2"></td>
<td id="B2"></td>
<td id="C2"></td>
<td id="D2"></td>
<td id="E2"></td>
<td id="F2"></td>
<td id="G2"></td>
<td id="H2"></td>
</tr>
<tr>
<td id="A1"></td>
<td id="B1"></td>
<td id="C1"></td>
<td id="D1"></td>
<td id="E1"></td>
<td id="F1"></td>
<td id="G1"><a href="#" class="knight white">&#9816;</a></td>
<td id="H1"></td>
</tr>
</table>
<div id="chess_board2" class="svg floatSvgOverHtml" ></div>
<script type="text/javascript">
//chess-board html and css adapted from http://designindevelopment.com/css/css3-chess-board/
var width = 656;
var height = 656;
var gridGraph = d3.select("#chess_board2")
.append("svg:svg")
.attr("width", width) // Set width of the SVG canvas
.attr("height", height); // Set height of the SVG canvas
var yAxisRange = d3.range(8, height, 80);
var xAxisRange = d3.range(8, width, 80);
gridGraph.selectAll("line.vertical")
.data(yAxisRange)
.enter().append("svg:line")
.attr("x1", function(d){return d;})
.attr("y1", 8)
.attr("x2", function(d){return d;})
.attr("y2", height-8)
.style("stroke", "rgb(6,120,155)")
.style("stroke-width", 2);
gridGraph.selectAll("line.horizontal")
.data(xAxisRange)
.enter().append("svg:line")
.attr("x1", 8)
.attr("y1", function(d){return d;})
.attr("x2", width-8)
.attr("y2", function(d){return d;})
.style("stroke", "rgb(6,120,155)")
.style("stroke-width", 2);
var yAxisRange = d3.range(8, height, 8 * 70);
var xAxisRange = d3.range(8, width, 8 * 70);
var yScale = d3.scale.linear()
.domain([0, 7])
.range(yAxisRange)
.nice();
var xScale = d3.scale.linear()
.domain([1, 8])
.range(xAxisRange)
.nice();
var xAxis = d3.svg.axis()
.scale(xScale)
.orient("top")
.tickValues([1,2,3,4,5,6,7,8]);
var yAxis = d3.svg.axis()
.scale(yScale)
.orient("right");
createAxis(gridGraph, "xaxis", xAxis, width, 40, "X", 35, height);
createAxis(gridGraph, "yaxis", yAxis, 20, -20, "Y", 0, 35);
var yLabels = ['A','B','C','D','E','F','G', 'H'];
var yMap = [];
for (var t = 0; t < 8; t++) {
yMap[t] = yLabels[t];
};
var points = {};
var startingXValue = 7;
var startingYValue = 7;
for (var i = 1; i < 9; i++) {
for (var j = 0; j < 8; j++) {
var pointId = yMap[j] + i.toString();
// we'll use 0 for not-visited and 1 for already visited
if(i == startingXValue && j == startingYValue){
points[pointId] = 1;
} else {
points[pointId] = 0;
}
}
}
var interpolationPoints = [];
var possibleMoves = getPossibleMoves({x: startingXValue, y: startingYValue});
var availableMoves = getAvailableMoves(possibleMoves);
var getBestNextMoveResult = getBestNextMove(availableMoves);
var nextMove = getBestNextMoveResult.bestMove;
//interpolationPoints.push(nextMove.interpolationPoint);
interpolationPoints.push(nextMove.resultPoint);
var iterations = 1;
drawMove(nextMove.resultPoint, "blue", iterations);
points[getPointId(nextMove.resultPoint)] = 1;
while(getBestNextMoveResult.bestMove){
iterations += 1;
if(getBestNextMoveResult.nextAvailableMoves.length == 1){
nextMove = getBestNextMoveResult.nextAvailableMoves[0];
drawMove(nextMove.resultPoint, "black", iterations);
points[getPointId(nextMove.resultPoint)] = 1;
//interpolationPoints.push(nextMove.interpolationPoint);
interpolationPoints.push(nextMove.resultPoint);
if(iterations == 63){
//although this should always be 63
break;
}
}
getBestNextMoveResult = getBestNextMove(getBestNextMoveResult.nextAvailableMoves);
nextMove = getBestNextMoveResult.bestMove;
drawMove(nextMove.resultPoint, "red", iterations);
points[getPointId(nextMove.resultPoint)] = 1;
//interpolationPoints.push(nextMove.interpolationPoint);
interpolationPoints.push(nextMove.resultPoint);
};
var line = d3.svg.line()
.x(function(d, i) {
return (xScale(d.x) + 40);
})
.y(function(d) {
return (yScale(d.y) + 40);
})
.interpolate('cardinal');
var path = gridGraph.append("svg:path")
.attr("d", line(interpolationPoints))
.attr("fill", "none")
.attr("stroke", "green")
.attr("stroke-width", 2);
var totalLength = path.node().getTotalLength();
path
.attr("stroke-dasharray", totalLength + " " + totalLength)
.attr("stroke-dashoffset", totalLength)
.transition()
.duration(100000)
.ease("back(20)")
.attr("stroke-dashoffset", 0);
gridGraph.on("click", function(){
path
.transition()
.duration(20000)
.ease("back(100)")
.attr("stroke-dashoffset", totalLength);
});
function createAxis(chart, id, d3Axis, x, y, name, xx, yy) {
chart.append("g")
.attr("id", id)
.attr("class", "axis")
.attr("transform", "translate(" + xx + "," + yy + ")")
.call(d3Axis)
.style("pointer-events", "none")
.append("text")
.attr("class", "label")
.attr("x", x)
.attr("y", y)
.style("text-anchor", "end")
.style("font-weight", "bold")
.text(name);
};
function drawMove(p, color, i){
gridGraph
.append("svg:path")
.attr("class", "point")
.attr("d", d3.svg.symbol().type("triangle-up").size(150)())
.attr("transform","translate(" + (xScale(p.x) + 40) + "," + (yScale(p.y) + 40) + ")")
.attr("fill", "grey")
.attr('stroke', color)
.attr('stroke-width', 2)
gridGraph.append("text")
.attr("transform","translate(" + (xScale(p.x) + 50) + "," + (yScale(p.y) + 65) + ")")
.text(i);
};
function getPossibleMoves(p){
var moves = [];
var x = p.x;
var y = p.y;
var up2y = p.y + 2;
var up1y = p.y + 1;
var down2y = p.y - 2;
var down1y = p.y - 1;
var left2x = p.x - 2;
var left1x = p.x - 1;
var right2x = p.x + 2;
var right1x = p.x + 1;
var interpolationPoint = {x:x, y:up2y};
var resultPoint = {x:right1x, y:up2y};
if(isInBounds(resultPoint)){
moves.push({resultPoint: resultPoint, interpolationPoint: interpolationPoint});
}
interpolationPoint = {x:x, y:up2y};
resultPoint = {x:left1x, y:up2y};
if(isInBounds(resultPoint)){
moves.push({resultPoint: resultPoint, interpolationPoint: interpolationPoint});
}
interpolationPoint = {x:x, y:down2y};
resultPoint = {x:right1x, y:down2y};
if(isInBounds(resultPoint)){
moves.push({resultPoint: resultPoint, interpolationPoint: interpolationPoint});
}
interpolationPoint = {x:x, y:down2y};
resultPoint = {x:left1x, y:down2y};
if(isInBounds(resultPoint)){
moves.push({resultPoint: resultPoint, interpolationPoint: interpolationPoint});
}
interpolationPoint = {x:right2x, y:y};
resultPoint = {x:right2x, y:up1y};
if(isInBounds(resultPoint)){
moves.push({resultPoint: resultPoint, interpolationPoint: interpolationPoint});
}
interpolationPoint = {x:right2x, y:y};
resultPoint = {x:right2x, y:down1y};
if(isInBounds(resultPoint)){
moves.push({resultPoint: resultPoint, interpolationPoint: interpolationPoint});
}
interpolationPoint = {x:left2x, y:y};
resultPoint = {x:left2x, y:up1y};
if(isInBounds(resultPoint)){
moves.push({resultPoint: resultPoint, interpolationPoint: interpolationPoint});
}
interpolationPoint = {x:left2x, y:y};
resultPoint = {x:left2x, y:down1y};
if(isInBounds(resultPoint)){
moves.push({resultPoint: resultPoint, interpolationPoint: interpolationPoint});
}
return moves;
};
function getAvailableMoves(moves){
var availableMoves = [];
moves.forEach(function(m){
var p = m.resultPoint;
var pointId = getPointId(p);
if(points[pointId] == 0){
availableMoves.push(m);
}
});
return availableMoves;
};
function getBestNextMove(moves){
var bestMove;
var nextAvailableMoves;
for (var i = 0; i < moves.length; i++) {
var m = moves[i];
var pMoves = getPossibleMoves(m.resultPoint);
if(pMoves.length == 0){
continue;
};
var aMoves = getAvailableMoves(pMoves);
if(aMoves.length == 0){
continue;
};
if(!bestMove){
bestMove = m;
nextAvailableMoves = aMoves;
} else if( aMoves.length <= nextAvailableMoves.length ){
bestMove = m;
nextAvailableMoves = aMoves;
}
}
return {bestMove: bestMove, nextAvailableMoves: nextAvailableMoves};
};
function getPointId(p){
return yMap[p.y] + p.x;
};
function isInBounds(p){
xMax = 8;
xMin = 1;
yMax = 7;
yMin = 0;
if(p.x >= xMin && p.x <= xMax && p.y >= yMin && p.y <= yMax){
return true;
}
return false;
};
</script>
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment