Stack Overflow
Stack Overflow

Questions tagged [knights-tour]

A knight's tour is a sequence of moves of a knight on a chessboard.

223 questions
23
votes
8 answers

Simulating the Knight Sequence Tour

I am currently trying to write a simple multi-threading program using Python. However I have run on to a bug I think I am missing. I am trying to simply write a program that uses a brute force approach the problem below: As can be seen from the…
JohnRoach
  • 747
  • 4
  • 11
  • 26
22
votes
7 answers

Riddle: The Square Puzzle

Last couple of days, I have refrained myself from master's studies and have been focusing on this (seemingly simple) puzzle: There is this 10*10 grid which constitutes a square of 100 available places to go. The aim is to start from a corner and…
rpr
  • 3,768
  • 2
  • 22
  • 20
21
votes
4 answers

How to optimize Knight's tour algorithm?

I code the Knight's tour algorithm in c++ using Backtracking method. But it seems too slow or stuck in infinite loop for n > 7 (bigger than 7 by 7 chessboard). The question is: What is the Time complexity for this algorithm and how can I optimize…
Kasra
  • 891
  • 1
  • 10
  • 17
7
votes
4 answers

How to improve Knight's tour with Warnsdorff's rule?

I know there are several similar threads, but I didn't find a solution even outside of SO. Here's my problem: I implemented Warnsdorff's algorithm for the Knight's Tour problem http://en.wikipedia.org/wiki/Knight%27s_tour , but it doesn't give a…
Mate E.
  • 396
  • 2
  • 10
6
votes
1 answer

Knight's tour algorithm with adjacency-lists

I'm trying to solve the Knight's tour problem in Java. My goal is to calculate all possible tours of a horse on a chessboard with any dimension. What I have tried to use is an adjadency-lists data structure. The problem now, is that I know which…
ShinyForce
  • 61
  • 2
5
votes
2 answers

Level solving and pathfinding

I have played a little flash game recently called Just A Trim Please and really liked the whole concept. The basic objective of the game is to mow the whole lawn by going over each square once. Your lawn mower starts on a tile and from there you can…
pbondoer
  • 538
  • 7
  • 15
5
votes
1 answer

Correct declaration of variables in recursive knights tour (Java homework)

I am having trouble finding the bug in my code for my last project of the school year (my first year as a CS student). I'm stuck on the recursion in my implementation of the knights tour problem. Here is the file in question:…
Shea Gunther
  • 51
  • 3
4
votes
2 answers

Knight tours algorithm C implementation performance

I was playing with Knight Tour algorithm implementation in Java. All that time I was completely sure that implementation on C must be faster. So after reading GNU C Reference the code be done and logic was implemented the same way is on Java. Can…
oreh
  • 1,129
  • 1
  • 9
  • 16
4
votes
3 answers

All possible knight positions in n moves - infinite loop in prolog

I have a problem with backtracking in Prolog when calculation solution for all possible knight positions in n moves with knowing the exact path. My solution print some of the first results and then never terminate while looking for impossible…
Szymon Modelewski
  • 51
  • 3
4
votes
4 answers

Knight's tour / recursion

I'm trying to learn a little bit more about recursion but somehow I can't solve the knight's tour and I'm hoping someone can point out my logic error. class main { static int fsize = 5; // board size (5*5) static int board[][] = new…
user238801
4
votes
2 answers

What am I missing in DFS in knight tour?

I am trying to solve the knight tour problem using DFS. I generated my graph (in this example I have 5x5 matrix): { 0: set([11, 7]), 1: set([8, 10, 12]), 2: set([9, 11, 5, 13]), 3: set([12, 14, 6]), 4: set([13, 7]), 5: set([16, 2, 12]),…
Salvador Dali
  • 214,103
  • 147
  • 703
  • 753
4
votes
2 answers

knight's tour efficient solution

I have build a code in prolog to find a series of legal moves in which the knight lands on each square of the chessboard(8x8) exactly once. I have used a logic like below: There 8 types of knight moves: right 1 down 2 left 1 down 2 right 2 down 1…
user3080000
3
votes
1 answer

How to solve partial Knight's Tour with special constraints

Knight's tour problem described in the image here, with diagram. A knight was initially located in a square labeled 1. It then proceeded to make a series of moves, never re-visiting a square, and labeled the visited squares in order. When the…
impossible_756
  • 31
  • 1
3
votes
1 answer

Solving Knight's Tour with Backtracking (javascript)

I am trying to write an algorithm in javascript to solve the Knight's Tour problem using Backtracking, but it doesn't work. Basically, the function is supposed to output an array called visited, which contains the locations of each moves. However,…
ratsimihah
  • 1,010
  • 1
  • 11
  • 22
3
votes
1 answer

Knight's Tour recursive method in Java, code execution is stuck on the 5th move (on a 25 square board)?

Since the board is 5x5 there should be 25 moves. I used a print statement to verify that the recursive method only runs 5 times successfully. When it gets to the fifth move in the last row it doesn't keep going, even though there are 4 valid moves…
J__
  • 61
  • 4
1
2 3
…
14 15