estelendur
d4be579a9f
Initial commit
|
9 éve | |
|---|---|---|
| .. | ||
| ._README.txt | 9 éve | |
| ._data.txt | 9 éve | |
| ._wk3.ss | 9 éve | |
| README.txt | 9 éve | |
| data.txt | 9 éve | |
| wk3.ss | 9 éve | |
| writeup.pdf | 9 éve | |
README.txt
Esty Thomas
Module: Scheme/Lambda Calculus
Week 3
FILES:
wk3.ss - Contains all the code for the project - a backtracking N-Queens solver, a min-conflicts N-Queens solver, and all the necessary and relevant helper/sub-functions.
README - This file.
gotmesomedata(1-5).ss - A bunch of interaction logs showing various results.
data.txt - The easy-to-read compilation of the data in gotmesomedata(1-5)
wk3data.txt - data collected on method of column selection in min-conflicts
tablesncharts.ods - An OpenDocument spreadsheet containing all my data and charts, organized nicely. Includes averages, medians, minimums, and maximums for both sets of min-conflicts data, and charts comparing various pieces of data from various solving methods.
writeup.pdf - A writeup of the project and analysis of the massive amounts of data in the above files.
HOW TO COMPILE:
Not really complicated. It's a single Scheme file. Open it up with DrScheme and interact away.
HOW TO USE:
For simple backtracking with standard initialization (starting state of the form (0 -1 -1 … -1)), use (backtracking (queengen ) 0 0 1). For simple min-conflicts with greedy initialization, use (min-conflicts (initialize-g ) -1 0 ). For simple min-conflicts with random initialization, use (min-conflicts (initialize-r ) -1 0 ). To attempt backtracking with inside to outside column order, use (backtracking (queengen ) 0 0 2). To attempt backtracking with outside to inside column order, use (backtracking (queengen ) 0 0 3).
To try many Ns at once, use the collect-me-some-data functions:
(collect-me-some-data-mg ) (min-conflicts, greedy init)
(collect-me-some-data-mr ) (min-conflicts, random init)
(collect-me-some-data-b ) (backtracking; column order 1 = 0 to N, 2 = inside out, 3 = outside in)
NOTES:
The inside-to-outside column order rarely ever works. Something is messed up in my backtracking algorithm such that it works pretty well going from left to right, and from outside to inside (though somewhat less well) but very badly in the inside-to-outside order. I fixed it so that it stopped continually getting stuck on a single state, but it fails when it should not.
Additionally, the backtracking algorithm can't find any solutions for N = 6.
Module: Scheme/Lambda Calculus
Week 3
FILES:
wk3.ss - Contains all the code for the project - a backtracking N-Queens solver, a min-conflicts N-Queens solver, and all the necessary and relevant helper/sub-functions.
README - This file.
gotmesomedata(1-5).ss - A bunch of interaction logs showing various results.
data.txt - The easy-to-read compilation of the data in gotmesomedata(1-5)
wk3data.txt - data collected on method of column selection in min-conflicts
tablesncharts.ods - An OpenDocument spreadsheet containing all my data and charts, organized nicely. Includes averages, medians, minimums, and maximums for both sets of min-conflicts data, and charts comparing various pieces of data from various solving methods.
writeup.pdf - A writeup of the project and analysis of the massive amounts of data in the above files.
HOW TO COMPILE:
Not really complicated. It's a single Scheme file. Open it up with DrScheme and interact away.
HOW TO USE:
For simple backtracking with standard initialization (starting state of the form (0 -1 -1 … -1)), use (backtracking (queengen ) 0 0 1). For simple min-conflicts with greedy initialization, use (min-conflicts (initialize-g ) -1 0 ). For simple min-conflicts with random initialization, use (min-conflicts (initialize-r ) -1 0 ). To attempt backtracking with inside to outside column order, use (backtracking (queengen ) 0 0 2). To attempt backtracking with outside to inside column order, use (backtracking (queengen ) 0 0 3).
To try many Ns at once, use the collect-me-some-data functions:
(collect-me-some-data-mg ) (min-conflicts, greedy init)
(collect-me-some-data-mr ) (min-conflicts, random init)
(collect-me-some-data-b ) (backtracking; column order 1 = 0 to N, 2 = inside out, 3 = outside in)
NOTES:
The inside-to-outside column order rarely ever works. Something is messed up in my backtracking algorithm such that it works pretty well going from left to right, and from outside to inside (though somewhat less well) but very badly in the inside-to-outside order. I fixed it so that it stopped continually getting stuck on a single state, but it fails when it should not.
Additionally, the backtracking algorithm can't find any solutions for N = 6.