Tag Archives: bactracking

The Knight’s tour problem

The Knight’s tour problem

Algorithm:
  1. If move == board.size then
    1. return true
  2. Iterate all possible 8 positions where Knight can go from current position
    1. If next position is valid and not visited earlier then
    2. Set board location = move
    3. Recursively call with move + 1 and with new position
    4. If last recursive call was success then
      1. return true
    5. else reset location
  3. return false

Latest Source Code:
Github: TheKnightTourProblem.java


Output:

 Path Found!! 
 0	 9	22	63	 6	 3	12	17	
23	62	 7	 2	11	16	 5	14	
 8	 1	10	21	 4	13	18	31	
61	24	39	42	19	30	15	50	
38	43	20	57	40	49	32	29	
25	60	41	46	35	28	51	54	
44	37	58	27	56	53	48	33	
59	26	45	36	47	34	55	52	

Video
Wiki