radiance · Radiance self-hosting compiler

lib/std/arch/rv64/tests/prog.nqueens.rad 3.4 KiB raw

//! N-Queens solver.
//! Solve the N-Queens problem using backtracking. Count all valid placements
//! for boards of size 1 through 8 and verify against known solution counts.

const MAX_N: u32 = 8;

record Board {
    queens: *mut [i32],
    solutionCount: u32,
    boardSize: u32,
}

fn isSafe(b: *Board, row: u32, col: u32) -> bool {
    let mut i: u32 = 0;
    while i < row {
        let qcol: i32 = b.queens[i];
        if qcol == col as i32 {
            return false;
        }
        let rowDiff: i32 = row as i32 - i as i32;
        let colDiff: i32 = col as i32 - qcol;
        if colDiff == rowDiff or colDiff == 0 - rowDiff {
            return false;
        }
        i += 1;
    }
    return true;
}

fn solve(b: *mut Board, row: u32) {
    if row == b.boardSize {
        b.solutionCount += 1;
        return;
    }
    let mut col: u32 = 0;
    while col < b.boardSize {
        if isSafe(b, row, col) {
            b.queens[row] = col as i32;
            solve(b, row + 1);
            b.queens[row] = -1;
        }
        col += 1;
    }
}

fn resetBoard(b: *mut Board) {
    let mut i: u32 = 0;
    while i < MAX_N {
        b.queens[i] = -1;
        i += 1;
    }
    b.solutionCount = 0;
}

fn solveNQueens(b: *mut Board, n: u32) -> u32 {
    resetBoard(b);
    b.boardSize = n;
    solve(b, 0);
    return b.solutionCount;
}

fn testAllSizes(b: *mut Board) -> i32 {
    let expected: [u32; 9] = [0, 1, 0, 0, 2, 10, 4, 40, 92];
    let mut n: u32 = 1;
    while n <= 8 {
        let count: u32 = solveNQueens(b, n);
        if count != expected[n] {
            return n as i32;
        }
        n += 1;
    }
    return 0;
}

fn testKnownSolution() -> i32 {
    let solution: [i32; 8] = [0, 4, 7, 5, 2, 6, 1, 3];

    let mut i: u32 = 0;
    while i < 8 {
        let mut j: u32 = i + 1;
        while j < 8 {
            assert solution[i] != solution[j];
            let rowDiff: i32 = j as i32 - i as i32;
            let colDiff: i32 = solution[j] - solution[i];
            assert colDiff != rowDiff and colDiff != 0 - rowDiff;
            j += 1;
        }
        i += 1;
    }

    let mut used: [bool; 8] = [false; 8];
    let mut k: u32 = 0;
    while k < 8 {
        let col: u32 = solution[k] as u32;
        if used[col] {
            return 3;
        }
        used[col] = true;
        k += 1;
    }

    return 0;
}

fn testDeterminism(b: *mut Board) -> i32 {
    let count1: u32 = solveNQueens(b, 8);
    let count2: u32 = solveNQueens(b, 8);
    let count3: u32 = solveNQueens(b, 8);

    assert count1 == 92;
    assert count2 == 92;
    assert count3 == 92;
    return 0;
}

fn testProperties() -> i32 {
    let expected: [u32; 9] = [0, 1, 0, 0, 2, 10, 4, 40, 92];

    let mut n: u32 = 4;
    while n <= 8 {
        assert expected[n] != 0;
        n += 1;
    }

    assert expected[2] == 0;
    assert expected[3] == 0;
    assert expected[7] > expected[6];
    assert expected[8] > expected[7];

    return 0;
}

@default fn main() -> i32 {
    let mut queens: [i32; 8] = [-1; 8];
    let mut b: Board = Board {
        queens: &mut queens[..],
        solutionCount: 0,
        boardSize: 0,
    };

    let r1: i32 = testAllSizes(&mut b);
    if r1 != 0 { return 10 + r1; }

    let r2: i32 = testKnownSolution();
    if r2 != 0 { return 20 + r2; }

    let r3: i32 = testDeterminism(&mut b);
    if r3 != 0 { return 30 + r3; }

    let r4: i32 = testProperties();
    if r4 != 0 { return 40 + r4; }

    return 0;
}

1	//! N-Queens solver.
2	//! Solve the N-Queens problem using backtracking. Count all valid placements
3	//! for boards of size 1 through 8 and verify against known solution counts.
4
5	const MAX_N: u32 = 8;
6
7	record Board {
8	queens: *mut [i32],
9	solutionCount: u32,
10	boardSize: u32,
11	}
12
13	fn isSafe(b: *Board, row: u32, col: u32) -> bool {
14	let mut i: u32 = 0;
15	while i < row {
16	let qcol: i32 = b.queens[i];
17	if qcol == col as i32 {
18	return false;
19	}
20	let rowDiff: i32 = row as i32 - i as i32;
21	let colDiff: i32 = col as i32 - qcol;
22	if colDiff == rowDiff or colDiff == 0 - rowDiff {
23	return false;
24	}
25	i += 1;
26	}
27	return true;
28	}
29
30	fn solve(b: *mut Board, row: u32) {
31	if row == b.boardSize {
32	b.solutionCount += 1;
33	return;
34	}
35	let mut col: u32 = 0;
36	while col < b.boardSize {
37	if isSafe(b, row, col) {
38	b.queens[row] = col as i32;
39	solve(b, row + 1);
40	b.queens[row] = -1;
41	}
42	col += 1;
43	}
44	}
45
46	fn resetBoard(b: *mut Board) {
47	let mut i: u32 = 0;
48	while i < MAX_N {
49	b.queens[i] = -1;
50	i += 1;
51	}
52	b.solutionCount = 0;
53	}
54
55	fn solveNQueens(b: *mut Board, n: u32) -> u32 {
56	resetBoard(b);
57	b.boardSize = n;
58	solve(b, 0);
59	return b.solutionCount;
60	}
61
62	fn testAllSizes(b: *mut Board) -> i32 {
63	let expected: [u32; 9] = [0, 1, 0, 0, 2, 10, 4, 40, 92];
64	let mut n: u32 = 1;
65	while n <= 8 {
66	let count: u32 = solveNQueens(b, n);
67	if count != expected[n] {
68	return n as i32;
69	}
70	n += 1;
71	}
72	return 0;
73	}
74
75	fn testKnownSolution() -> i32 {
76	let solution: [i32; 8] = [0, 4, 7, 5, 2, 6, 1, 3];
77
78	let mut i: u32 = 0;
79	while i < 8 {
80	let mut j: u32 = i + 1;
81	while j < 8 {
82	assert solution[i] != solution[j];
83	let rowDiff: i32 = j as i32 - i as i32;
84	let colDiff: i32 = solution[j] - solution[i];
85	assert colDiff != rowDiff and colDiff != 0 - rowDiff;
86	j += 1;
87	}
88	i += 1;
89	}
90
91	let mut used: [bool; 8] = [false; 8];
92	let mut k: u32 = 0;
93	while k < 8 {
94	let col: u32 = solution[k] as u32;
95	if used[col] {
96	return 3;
97	}
98	used[col] = true;
99	k += 1;
100	}
101
102	return 0;
103	}
104
105	fn testDeterminism(b: *mut Board) -> i32 {
106	let count1: u32 = solveNQueens(b, 8);
107	let count2: u32 = solveNQueens(b, 8);
108	let count3: u32 = solveNQueens(b, 8);
109
110	assert count1 == 92;
111	assert count2 == 92;
112	assert count3 == 92;
113	return 0;
114	}
115
116	fn testProperties() -> i32 {
117	let expected: [u32; 9] = [0, 1, 0, 0, 2, 10, 4, 40, 92];
118
119	let mut n: u32 = 4;
120	while n <= 8 {
121	assert expected[n] != 0;
122	n += 1;
123	}
124
125	assert expected[2] == 0;
126	assert expected[3] == 0;
127	assert expected[7] > expected[6];
128	assert expected[8] > expected[7];
129
130	return 0;
131	}
132
133	@default fn main() -> i32 {
134	let mut queens: [i32; 8] = [-1; 8];
135	let mut b: Board = Board {
136	queens: &mut queens[..],
137	solutionCount: 0,
138	boardSize: 0,
139	};
140
141	let r1: i32 = testAllSizes(&mut b);
142	if r1 != 0 { return 10 + r1; }
143
144	let r2: i32 = testKnownSolution();
145	if r2 != 0 { return 20 + r2; }
146
147	let r3: i32 = testDeterminism(&mut b);
148	if r3 != 0 { return 30 + r3; }
149
150	let r4: i32 = testProperties();
151	if r4 != 0 { return 40 + r4; }
152
153	return 0;
154	}