Aknakereső (Alice) ================== A feladvány Adott egy n*m mezőből álló, téglalap alakú tábla, amelynek egyes mezőin 0 és 8 közötti számok szerepelnek. A feladat az, hogy aknákat helyezzünk el a táblára, az alábbi feltételek teljesítésével: - Pontosan i darab aknát használunk fel. - A számozott mezők nyolc él- és sarokszomszédja közül pontosan annyi mezőn kell aknának lennie, amekkora szám szerepel az adott mezőn. - Számmal jelzett mezőn nem lehet akna. - Egy mezőn legfeljebb 1 akna lehet. Egy feladványnak több megoldása is lehet. Az első ábra egy feladványt ábrázol, a második ábra ennek (egyetlen) megoldását mutatja. (A megoldásban * jelöli az aknákat.) +---+---+---+---+---+ | | | 0 | | | +---+---+---+---+---+ | | | | | 1 | +---+---+---+---+---+ | 3 | | 1 | | | +---+---+---+---+---+ | | | | | 1 | +---+---+---+---+---+ | | 1 | | | | +---+---+---+---+---+ +---+---+---+---+---+ | | | 0 | | | +---+---+---+---+---+ | * | | | | 1 | +---+---+---+---+---+ | 3 | * | 1 | | * | +---+---+---+---+---+ | * | | | | 1 | +---+---+---+---+---+ | | 1 | | | | +---+---+---+---+---+ (n=5, m=5, i=4) A megoldandó feladat Írjon akna néven olyan SML-függvényt, amely egy feladvány összes megoldását előállítja! Az SML-függvény paramétere egy ((S,O), N, RefPL) hármas, jelentésük a következő: - S és O a tábla mérete, azaz sorainak és oszlopainak a száma (a tábla bal felső mezője az első sor első oszlopában van); - N az aknák száma; - RefPL egy lexikografikusan rendezett lista, amelynek elemei (Sor,Oszlop,Érték) alakú hármasok. Az első ábrán bemutatott feladvány esetén például az SML-függvény paramétere: ((5,5), 4, [(1,3,0),(2,5,1),(3,1,3),(3,3,1),(4,5,1),(5,2,1)]) Az SML-függvény eredménye egy olyan lista, amely a feladvány összes megoldását tartalmazza, mégpedig minden megoldást pontosan egyszer. Ha a feladatnak nincs megoldása, az eredmény az üres lista. Egy megoldást a koordinátapárok listájaként kell megadni. Az aknák felsorolásának sorrendje tetszőleges. A második ábrán látható megoldást írja le például az alábbi (egyelemű) megoldás-lista: [[(2,1),(3,2),(3,5),(4,1)]]