Created
November 28, 2014 21:26
-
-
Save SoundLogic/49e783251567626a9bbd to your computer and use it in GitHub Desktop.
javascript based solution for the Knight's Tour puzzle (http://en.wikipedia.org/wiki/Knight%27s_tour)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <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">♘</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