Chapters: Ch 1 · Ch 2 · Ch 3 · Ch 4 · Ch 5
Knight’s Tour
The Knight’s Tour (boraberan.wordpress.com) https://boraberan.wordpress.com/2012/09/28/the-knights-tour/
A blog post walking through the Knight’s Tour problem — finding a sequence of moves that visits every square of a chessboard exactly once — covering both backtracking and Warnsdorff’s heuristic approaches. [→ algorithms-data-structures]
Warnsdorff’s algorithm for Knight’s tour problem — GeeksforGeeks https://www.geeksforgeeks.org/warnsdorffs-algorithm-knights-tour-problem/
GeeksforGeeks article on Warnsdorff’s 1823 heuristic: at each step, move the knight to the square with the fewest onward moves. Runs in near-linear time and produces a valid tour on boards up to ~76x76 reliably. [→ algorithms-data-structures]
Knight’s tour — Wikipedia https://en.wikipedia.org/wiki/Knight's_tour
The Wikipedia reference article on the Knight’s Tour problem, covering history, classifications (open vs closed tours), mathematical properties, and connections to Hamiltonian paths in graph theory. [→ algorithms-data-structures; mathematics-science]
Warnsdorff’s rule PDF https://raw.githubusercontent.com/douglassquirrel/warnsdorff/refs/heads/master/5_Squirrel96.pdf
Squirrel’s 1996 paper formalising and analysing Warnsdorff’s rule, including conditions under which it provably produces a valid tour and discussion of tie-breaking strategies. [→ algorithms-data-structures]
Graph theory origins in Sanskrit poetry and Arabic — highly entertaining YouTube https://youtu.be/DjZB9HvddQk
An entertaining YouTube lecture tracing the origins of graph theory to Sanskrit prosody (Pingala’s enumeration of binary metres) and medieval Arabic combinatorics — predating Euler’s Königsberg bridge problem by centuries. [→ mathematics-science; indian-history-culture]
Scala Knight’s Tour Validation (LeetCode)
Version 1 (774ms, Beats 50%):
object Solution {
case class Rc (row:Int, col:Int)
def checkValidGrid(grid: Array[Array[Int]]): Boolean = {
val n = grid.size
def checkInit():Boolean = (n > 0) && (grid(0)(0) == 0)
val visited = scala.collection.mutable.ArrayBuffer.empty[Rc]
def getNextRc(currRc:Rc):Option[Rc] = {
val nrInc = Array(-2, -2, -1, -1, 1, 1, 2, 2)
val ncInc = Array(-1, 1, -2, 2, 2, -2, 1, -1)
val knightStep = grid(currRc.row)(currRc.col)
visited += currRc
val nextPoss:Array[Rc] = (0 until 8).toArray.flatMap(i => {
val nr = currRc.row + nrInc(i)
val nc = currRc.col + ncInc(i)
val nrc = Rc(nr, nc)
if ((nr >= 0) && (nr < n) && (nc >= 0) && (nc < n) && (visited.find(rc => nrc == rc).isEmpty)) {
Array(nrc)
}
else {
Array[Rc]()
}
})
nextPoss.find(rc => grid(rc.row)(rc.col) == knightStep + 1)
}
def checkTour() : Boolean = {
var currO:Option[Rc] = Some(Rc(0,0))
var nextO = getNextRc(Rc(0,0))
while(nextO.isDefined) {
currO = nextO
nextO = getNextRc(nextO.get)
}
val finalrc = currO.getOrElse(Rc(0,0))
grid(finalrc.row)(finalrc.col) == (n*n)-1
}
checkInit() && checkTour()
}
}
Version 2 (optimized, 710ms Beats 100% — removes O(n) visited scan):
object Solution {
case class Rc (row:Int, col:Int)
def checkValidGrid(grid: Array[Array[Int]]): Boolean = {
val n = grid.size
def checkInit():Boolean = (n > 0) && (grid(0)(0) == 0)
def getNextRc(currRc:Rc):Option[Rc] = {
val nrInc = Array(-2, -2, -1, -1, 1, 1, 2, 2)
val ncInc = Array(-1, 1, -2, 2, 2, -2, 1, -1)
val knightStep = grid(currRc.row)(currRc.col)
val nextPoss:Array[Rc] = (0 until 8).toArray.flatMap(i => {
val nr = currRc.row + nrInc(i)
val nc = currRc.col + ncInc(i)
val nrc = Rc(nr, nc)
if ((nr >= 0) && (nr < n) &&
(nc >= 0) && (nc < n) &&
(grid(nrc.row)(nrc.col) == knightStep + 1)) {
Array(nrc)
}
else {
Array[Rc]()
}
})
nextPoss.find(rc => grid(rc.row)(rc.col) == knightStep + 1)
}
def checkTour() : Boolean = {
var currO:Option[Rc] = Some(Rc(0,0))
var nextO = getNextRc(Rc(0,0))
while(nextO.isDefined) {
currO = nextO
nextO = getNextRc(nextO.get)
}
val finalrc = currO.getOrElse(Rc(0,0))
grid(finalrc.row)(finalrc.col) == (n*n)-1
}
checkInit() && checkTour()
}
}
Submitted as “kodebale” at Sep 25, 2024.
Rust Knight’s Tour Validation
impl Solution {
pub fn check_valid_grid(grid: Vec<Vec<i32>>) -> bool {
#[derive(Copy, Clone)]
struct Move{row: isize, col: isize}
#[derive(Copy, Clone)]
struct Rc{row: usize, col: usize}
fn mv(row: isize, col: isize) -> Move {
Move{row: row, col:col}
}
fn check_init(grid: &Vec<Vec<i32>>) -> bool {
(grid.len() > 0) && (grid[0].len() > 0) && (grid[0][0] == 0)
}
fn get_next(grid: &Vec<Vec<i32>>, curr : Rc, n: isize) -> Option<Rc> {
let moves: Vec<Move> = vec!(mv(-2, -1), mv(-2, 1), mv(-1, -2), mv(-1, 2 ), mv(1, 2), mv(1, -2), mv(2, 1), mv(2, -1));
let knight_step = grid[curr.row][curr.col];
moves.iter().fold(None, |next_pos_o, m| {
let r = m.row + curr.row as isize;
let c = m.col + curr.col as isize;
next_pos_o.or_else(|| {
if (r >= 0) && (r < n) && (c >= 0) && (c < n) &&
(grid[r as usize][c as usize] == knight_step + 1) {
Some(Rc{row:r as usize, col:c as usize})
} else {
None
}
})
})
}
fn check_tour(grid: &Vec<Vec<i32>>) -> bool {
let n = grid.len() as isize;
let mut curr = Rc{row: 0, col: 0};
let mut next_o = get_next(grid, curr, n);
while next_o.is_some() {
curr = next_o.map_or_else(|| curr, |n| n);
next_o = get_next(grid, Rc{row: curr.row, col: curr.col}, n);
}
grid[curr.row][curr.col] == ((n*n - 1) as i32)
}
check_init(&grid) && check_tour(&grid)
}
}
Runtime 3ms, Beats 25.00%, Memory 2.05MB Beats 66.67%