SCIP in C++11 ― 2.2.3節 その6

エイトクイーンパズル：問題2.42

問題2.43は特にC++コードを書くわけでないのでパス。

1つのクイーンの位置・クイーン位置のリストとしての盤面・盤面のリストとしての解と、

問題の階層がわかれている。Schemeだとその階層が見づらいが、

C++ではtypedefに分類のメモの役割をもたせられるので、わかりやすくはある。

いつもは型が七面倒臭いし、それが致命的なこともあるだろうが、

問題によってはいいこともあるかｗ

一つのクイーンの位置と盤面の表現はいろいろ考えられるが、

ここでは単純にx座標（列）とy座標（行）の組にした。

第k列のクイーンが他と当たりになっていないかは、

横に並んでいるか斜めに並んでいるかのor演算だから、filterに渡すために、

2つの述語関数からその論理和の述語関数を返すlogicalOr

（ついでにlogicalAndとlogicalNot）も実装。

この辺は第1章で学んだ発想が少し生きてきたか。

board-size=7&8も計算したが、出力が長たらしいので略。

同じ配置を回転しただけのものを省く、とかするべきなのかもだが、

そこまではしないでおくｗ

表示系get1BoardStringとprintBoardsでは、

accumulate,filter,mapを使った長い連鎖に挑戦。

書いたら一発でコンパイル・実行とも正常！

超気持ちいい～感激～！！

まあ可読性に難ありだけどｗ

----

// AND operation of predicate

template<typename Argument>

const function<bool(Argument)>

logicalAnd(const function<bool(Argument)>& predicate1,

           const function<bool(Argument)>& predicate2)

{

    const function<bool(Argument)>

        andPredicate=[predicate1,predicate2](const Argument& arg)

        {return(predicate1(arg) && predicate2(arg));};

    return(andPredicate);

}

// OR operation of predicate

template<typename Argument>

const function<bool(Argument)>

logicalOr(const function<bool(Argument)>& predicate1,

          const function<bool(Argument)>& predicate2)

{

    const function<bool(Argument)>

        orPredicate=[predicate1,predicate2](const Argument& arg)

        {return(predicate1(arg) || predicate2(arg));};

    return(orPredicate);

}

// NOT operation of predicate

template<typename Argument>

const function<bool(Argument)>

logicalNot(const function<bool(Argument)>& predicate)

{

    const function<bool(Argument)>

        notPredicate=[predicate](const Argument arg)

        {return(!predicate(arg));};

    return(notPredicate);

}

typedef List Queen;

typedef List QueenSet;

typedef List QueenBoards;

typedef List Queen;

typedef List QueenSet;

typedef List QueenBoards;

const int xCoordinate(const Queen& q){

    return(value<int>(car(q)));

}

const int yCoordinate(const Queen& q){

    return(value<int>(cadr(q)));

}

const function<bool(int,QueenSet)>

isSafe=[](const int kColumn, const QueenSet& queenSet)

{

    const int xNewQueen(kColumn);

    const int yNewQueen(yCoordinate(car(queenSet)));

   

    const function<bool(Queen)> isSameRow=

    [yNewQueen](const Queen queenPosition)

    {return(yCoordinate(queenPosition)==yNewQueen);};

   

    const function<bool(Queen)> isDiagonal=

    [xNewQueen,yNewQueen]

    (const Queen queenPosition)

    {return(abs(yNewQueen-yCoordinate(queenPosition))

            ==abs(xNewQueen-xCoordinate(queenPosition)));};

    

    return(0==length(filter(logicalOr(isSameRow,isDiagonal),cdr(queenSet))));

};

const function<QueenSet(int,int,QueenSet)>

adjoinPosition

=[](const int newRow, const int kColumn, const QueenSet& restOfQueens)

{

    return(cons(cons(kColumn,newRow),restOfQueens));

};

const QueenBoards emptyBoard(void)

{return(QueenBoards(makeList(makeList())));}

const QueenBoards queens(const int boardSize)

{

    function<QueenBoards(int)> queenColumns;

    queenColumns=[boardSize,&queenColumns]

        (const int kColumn){

        if(0==kColumn){return(emptyBoard());}

       

        const function<bool(QueenSet)> isSafeQueen

        =[kColumn](const QueenSet& queenSet)

        {

            return(isSafe(kColumn,queenSet));

        };

       

        const function<QueenBoards(QueenSet)>

        appendPositions=[boardSize,kColumn]

        (const QueenSet& restOfQueens)

        {

            const function<QueenSet(int)>

            trialRow2Position=

            [restOfQueens,kColumn](const int newRow)

            {

                return(adjoinPosition(newRow,kColumn,restOfQueens));

            };

            return(mapping

                   (trialRow2Position,

                    enumerateInterval(1,boardSize)));

        };

        return(filter

               (isSafeQueen,

                flatMap(appendPositions,queenColumns(kColumn-1))));

    };

   

    return(queenColumns(boardSize));

}

const function<string(string,string)>

jointString=[](const string inString1, const string inString2)

{return(inString1+inString2);};

const function<string(string)> addEndOfLine

=[](const string inString){return(inString+"\n");};

void get1BoardString(const QueenSet& board,const int boardSize)

{

    const auto coordinateList(enumerateInterval(1,boardSize));

    const string nullString("");

    function<string(int)> makeRowLine

        =[&nullString,&coordinateList,board](const int y){

        function<bool(Queen)> isSameY=[y](const Queen aQueen){

            return(yCoordinate(aQueen)==y);

        };

        const int xOfYQueen(xCoordinate(car(filter(isSameY,board))));

        function<string(int)> makeMark=[y,xOfYQueen](const int x){

            if(xOfYQueen==x){return("o");}

            return("x");

        };

        return(accumulate

               (jointString,nullString,

                mapping(makeMark,coordinateList)));

    };

    cout<<accumulate

           (jointString,nullString,

            mapping(addEndOfLine,

                mapping(makeRowLine,coordinateList)));

}

void printBoards(const QueenBoards& boards,const int boardSize)

{

    function<void(QueenBoards)> print1Board

        =[boardSize](const QueenSet board){

        get1BoardString(board,boardSize);

        cout<<endl;

    };

    forEach(print1Board,boards);

}

int main(int argc, char** argv)

{

    int boardSize(4);

    cout<<"board-size = "<<boardSize<<":"<<endl;

    printBoards(queens(boardSize),boardSize);

    boardSize=5;

    cout<<"board-size = "<<boardSize<<":"<<endl;

    printBoards(queens(boardSize),boardSize);

    boardSize=6;

    cout<<"board-size = "<<boardSize<<":"<<endl;

    printBoards(queens(boardSize),boardSize);

    boardSize=7;

    cout<<"board-size = "<<boardSize<<":"<<endl;

    printBoards(queens(boardSize),boardSize);

    boardSize=8;

    cout<<"board-size = "<<boardSize<<":"<<endl;

    printBoards(queens(boardSize),boardSize);

    return(0);

}

----

出力

----

board-size = 4:

xoxx

xxxo

oxxx

xxox

xxox

oxxx

xxxo

xoxx

board-size = 5:

oxxxx

xxoxx

xxxxo

xoxxx

xxxox

oxxxx

xxxox

xoxxx

xxxxo

xxoxx

xoxxx

xxxox

oxxxx

xxoxx

xxxxo

xoxxx

xxxxo

xxoxx

oxxxx

xxxox

xxoxx

oxxxx

xxxox

xoxxx

xxxxo

xxoxx

xxxxo

xoxxx

xxxox

oxxxx

xxxox

oxxxx

xxoxx

xxxxo

xoxxx

xxxox

xoxxx

xxxxo

xxoxx

oxxxx

xxxxo

xoxxx

xxxox

oxxxx

xxoxx

xxxxo

xxoxx

oxxxx

xxxox

xoxxx

board-size = 6:

xoxxxx

xxxoxx

xxxxxo

oxxxxx

xxoxxx

xxxxox

xxoxxx

xxxxxo

xoxxxx

xxxxox

oxxxxx

xxxoxx

xxxoxx

oxxxxx

xxxxox

xoxxxx

xxxxxo

xxoxxx

xxxxox

xxoxxx

oxxxxx

xxxxxo

xxxoxx

xoxxxx