This PR adds solutions to the following exercises from SICP JS using Source 3 Non-Det, as part of our reach goals.
Exercise 4.31: Faster solution to multiple dwelling puzzle
Exercise 4.33: Liars puzzle
Exercise 4.35: eight-queens
Two solutions have been added. Each of them makes use of the generate-and-test paradigm.
The first (queens_slow) uses non-determinism for generating both the row and column for each position. It does so in an optimized manner, testing the corresponding condition as soon as the choice is generated, thereby reducing the search space. However, this is not enough to yield a quick solution when N = 8. This solution also gives repeated solutions (i.e different permutations that have all the same positions) upon backtracking.
The second (queens_fast) uses non-determinism in picking only the row and not the column of each position, with the columns being fixed. This further reduces the search space, yielding a quick solution when N = 8.
Example Usage:
const result = queens_fast(8, 8); pretty_print(result, 8);
This PR adds solutions to the following exercises from SICP JS using Source 3 Non-Det, as part of our reach goals.
Exercise 4.31: Faster solution to multiple dwelling puzzle
Exercise 4.33: Liars puzzle
Exercise 4.35: eight-queens Two solutions have been added. Each of them makes use of the generate-and-test paradigm.
The first (
queens_slow) uses non-determinism for generating both the row and column for each position. It does so in an optimized manner, testing the corresponding condition as soon as the choice is generated, thereby reducing the search space. However, this is not enough to yield a quick solution when N = 8. This solution also gives repeated solutions (i.e different permutations that have all the same positions) upon backtracking.The second (
queens_fast) uses non-determinism in picking only the row and not the column of each position, with the columns being fixed. This further reduces the search space, yielding a quick solution when N = 8.Example Usage:
Depends on #34