CPMagical CP Library

Problem solution · Turing

CCC 2010 J5 - Knight Hop

CCC 2010 J5 - Knight Hop: a Turing solution using breadth-first search. Learn the idea, check the complexity, and read the full code, with credit to CCCSolutions.

Technique
Breadth-first search
Source
CCCSolutions
Length
117 lines
Start with the idea.

Try the problem first. If you get stuck, read the approach below, then write your own solution. The full code is at the bottom.

Approach

Breadth-first search

For CCC 2010 J5 - Knight Hop, the implementation explores reachable states in layers, which is the standard shape for unweighted shortest paths and minimum-step transitions.

  1. Model each valid configuration as a state and each legal move as an edge.
  2. Seed the queue with the starting state and mark it immediately.
  3. Expand each state once, recording distance or reachability for unseen neighbours.

Code notes

  • 117 lines of Turing from the credited upstream file ccc10j5.t.
  • The implementation keeps its working state in language-native values and containers.
  • No explicit loop blocks detected.

Complexity

Verify that each state and transition is processed only a bounded number of times; that determines the traversal cost.

Check the problem constraints before deciding whether this complexity will pass.

Source

Code and credit

This code comes from CCCSolutions by CCCSolutions contributors · Milliken Mills High School and is used under the MIT licence.

Open problem ↗Original source ↗
Full codeCCC 2010 J5 - Knight Hop · TuringTuring
Use this to learn the idea, then write your own version.
% J5 2010; Knight Hop%% 2D array for the board% 1D array of points to do the BFS% class Point    export var x, var y, setValue    var x, y : int     procedure setValue (a, b : int)	x := a	y := b    end setValueend Point  var board : array 1 .. 8, 1 .. 8 of int var p : array 1 .. 64 of ^Pointvar q : array 1 .. 64 of ^Pointvar psize, qsize : int var x, y : intvar sx, sy : intvar a, b, step : int % get inputget x, y, sx, sy %initialize array of points (tracks latest moves)new p (1)p (1) -> setValue (x, y)psize := 1 % initialize the board (99999 = haven't got there yet)for i : 1 .. 8    for j : 1 .. 8	board (i, j) := 99999    end forend forboard (x, y) := 0 %move EVERYWHERE possiblestep := 1loop    exit when psize = 0     % move to the next spots and remember where you moved to in q    qsize := 0    for i : 1 .. psize	a := p (i) -> x	b := p (i) -> y 	% try all 8 possible moves	if a + 1 <= 8 and b + 2 <= 8 and step < board (a + 1, b + 2) then	    board (a + 1, b + 2) := step	    qsize := qsize + 1	    new q (qsize)	    q (qsize) -> setValue (a + 1, b + 2)	end if	if a + 2 <= 8 and b + 1 <= 8 and step < board (a + 2, b + 1) then	    board (a + 2, b + 1) := step	    qsize := qsize + 1	    new q (qsize)	    q (qsize) -> setValue (a + 2, b + 1)	end if	if a + 2 <= 8 and b - 1 >= 1 and step < board (a + 2, b - 1) then	    board (a + 2, b - 1) := step	    qsize := qsize + 1	    new q (qsize)	    q (qsize) -> setValue (a + 2, b - 1)	end if	if a + 1 <= 8 and b - 2 >= 1 and step < board (a + 1, b - 2) then	    board (a + 1, b - 2) := step	    qsize := qsize + 1	    new q (qsize)	    q (qsize) -> setValue (a + 1, b - 2)	end if	if a - 1 >= 1 and b - 2 >= 1 and step < board (a - 1, b - 2) then	    board (a - 1, b - 2) := step	    qsize := qsize + 1	    new q (qsize)	    q (qsize) -> setValue (a - 1, b - 2)	end if	if a - 2 >= 1 and b - 1 >= 1 and step < board (a - 2, b - 1) then	    board (a - 2, b - 1) := step	    qsize := qsize + 1	    new q (qsize)	    q (qsize) -> setValue (a - 2, b - 1)	end if	if a - 2 >= 1 and b + 1 <= 8 and step < board (a - 2, b + 1) then	    board (a - 2, b + 1) := step	    qsize := qsize + 1	    new q (qsize)	    q (qsize) -> setValue (a - 2, b + 1)	end if	if a - 1 >= 1 and b + 2 <= 8 and step < board (a - 1, b + 2) then	    board (a - 1, b + 2) := step	    qsize := qsize + 1	    new q (qsize)	    q (qsize) -> setValue (a - 1, b + 2)	end if    end for     % get set for the next round of moving    % (its one more step and set p = q)    step := step + 1    psize := qsize    for i : 1 .. psize	p (i) := q (i)    end forend loop % answer in on the boardput board (sx, sy)

Keep practising

Did this explanation save you time? I'm a Grade 11 student building this free library to make difficult algorithms easier to understand.

Buy me a coffee ↗