生成7位数字

Question

给定如下所示的电话键盘：

1 2 3
4 5 6
7 8 9
  0

到目前为止我有这个..。我已经计算了从开始位置开始的所有可能的移动，并填充了一个名为MoveArray的数组，以帮助记忆我正在存储的调用(即printoutArr)。

我试图递归地构建7个字母的字符串，但我没有得到anywhere.This是我被卡住的地方。这个请求有什么帮助吗？！？！

Answer 1

我在这个答案中使用了Java 8。如果您希望我转换为不使用streams，请告诉我。

我建议将问题分成两部分。第一个是定义每个棋子的潜在动作的算法，第二个是获得所有组合的递归。

对于第一个问题，从接口开始：

public interface MoveGenerator {
    IntStream nextPositions(Integer position);
}

您可以只使用Function<Integer,IntStream>，但是定义您自己的接口会让事情变得更加明显。

然后，您可以为每个部分定义此接口的实现。一旦你定义了一系列合法的动作，这就相当微不足道了。请参阅下面的附录，以获得不需要数组的更优雅的解决方案。

int[][] legalBishopMoves = {{7, 9}, {5, 9}, {4, 6}, {5, 7}...};
MoveGenerator bishopMoves = pos -> Arrays.stream(legalBishopMoves[pos]);

第二个问题实际上相对简单。它接受一个起始位置和一个MoveGenerator，并使用递归生成所有字符串：

void getCombinations(String combination, int position, MoveGenerator generator) {
    if (combination.length() == 7) {
        System.out.println(combination);
    } else {
        generator.nextPositions(position)
            .forEach(pos -> getCombinations(combination + pos, pos, generator);
    }
}

你可以这样叫它：getCombinations("", 4, bishopMoves)

附录

我不喜欢在我的代码中使用静态数组来表示规则，所以我创建了一个替代方案，可以从每个块的基本规则生成移动：

int col(int pos) {
    return pos == 0 ? 1 : (pos - 1) % 3;
}

int row(int pos) {
    return pos == 0 ? 2 : (pos - 1) / 3;
}

int rows(int from, int to) {
    return Math.abs(row(from) - row(to));
}

int cols(int from, int to) {
    return Math.abs(col(from) - col(to));
}

interface MoveTest {
    boolean isLegal(int rows, int cols);
}

MoveGenerator fromTest(MoveTest test) {
    return from -> IntStream.range(0, 10)
        .filter(to -> from != to)
        .filter(to -> test.isLegal(rows(from, to), cols(from, to)));
}

MoveGenerator bishopMoves = fromTest((r, c) -> r == c);
MoveGenerator knightMoves = fromTest((r, c) -> r + c == 3);
MoveGenerator rookMoves = fromTest((r, c) -> r == 0 || c == 0);
MoveGenerator queenMoves = fromTest((r, c) -> r == 0 || c == 0 || r == c); 
MoveGenerator kingMoves = fromTest((r, c) -> r <= 1 && c <= 1);

这很有效，尽管我建议你不要尝试任何皇后动作，因为你最终会有很多弦！

我没有添加棋子移动，因为它不会产生任何东西。

Answer 2

我喜欢@sprinter的方式，因为它更简洁，并利用了Java 8的优势。但这里有一个更详细的方法来解决这个问题：

首先定义一个描述棋子运动的通用接口

interface Movement {
    int x();
    int y();
}

然后，我们将使用枚举来实现其中一个块的移动

enum BishopMovement implements Movement {
    //the names for the enum constants
    //indicate the direction of the movement and how far it goes
    UpLeft1( -1, -1 ),
    UpLeft2( -2, -2 ),
    UpRight1( 1, -1 ),
    UpRight2( 2, -2 ),
    DownRight1( 1, 1 ),
    DownRight2( 2, 2 ),
    DownLeft1( -1, 1 ),
    DownLeft2( -2, 2 );

    final int x, y;

    BishopMovement( int xOffset, int yOffset ){
        x = xOffset;
        y = yOffset;
    }

    @Override
    public int x() {
        return x;
    }

    @Override
    public int y() {
        return y;
    }    
}

这是另一个关于骑士的例子

enum KnightMovement implements Movement {
    //again, the names say which movement they represent
    UpLeft( -1, -2 ),
    UpRight( 1, -2 ),
    RightUp( 2, -1 ),
    RightDown( 2, 1 ),
    DownRight( 1, 2 ),
    DownLeft( -1, 2 ),
    LeftDown( -2, 1 ),
    LeftUp( -2, -1 );

    final int x, y;

    KnightMovement( int xOffset, int yOffset ){
        x = xOffset;
        y = yOffset;
    }

    @Override
    public int x() {
        return x;
    }

    @Override
    public int y() {
        return y;
    }
}

像这样定义每个片段有点乏味，但实际上我喜欢将动作组织在枚举中。我想是个人喜好吧。

我还将在枚举中定义键盘中的键

enum Key {
    //note that the order is important here
    //because we'll be using ordinal() to easily
    //convert between an int and a Key
    Zero( 1, 3 ),
    One( 0, 0 ),
    Two( 1, 0 ),
    Three( 2, 0 ),
    Four( 0, 1 ),
    Five( 1, 1 ),
    Six( 2, 1 ),
    Seven( 0, 2 ),
    Eight( 1, 2 ),
    Nine( 2, 2 ),
    None( -1, -1 ); //default constant

    final int x, y;

    Key( int xOffset, int yOffset ){
        x = xOffset;
        y = yOffset;
    }

    //overriding toString because it'll be easier
    //to record the moves
    @Override
    public String toString() {
        String s = "";
        if( !this.equals( None ) )
            s += this.ordinal();
        return s;
    }
}

最后，给出解决方案

public class Solution {    
    static Key[][] keypad;
    static final int x1 = 2, y1 = 3; //Key One will be at x=2, y=3

    static {
        keypad = new Key[7][10]; //extra padding
        for( int x = 0; x < 7; x++ ){
            for( int y = 0; y < 10; y++ ) {
                keypad[x][y] = Key.None; //set all the elements to the default
            }
        }
        for( Key k : Key.values() ) {
            keypad[x1+k.x][y1+k.y] = k; //set all the keys
        }
    }

    public static void main( String[] args ) {
        int key = 1;
        int totalMoves = 7;
        String initialMovement = "-";
        String allPossibleMoves = recursiveSolve( key, totalMoves, initialMovement, BishopMovement.values() );
        //all the possible moves will be separated by spaces with a trailing space at the end
        System.out.print( allPossibleMoves );
    }


    static String recursiveSolve( int key, int movesLeft, String moves, Movement[] possibleMoves ) {
        String results="";
        if( movesLeft > 0 ){
            Key k = Key.values()[key], nextKey;
            for( Movement m : possibleMoves ){
                nextKey = keypad[x1+k.x+m.x()][y1+k.y+m.y()];
                if( !nextKey.equals( Key.None ) ) {
                    results += recursiveSolve( nextKey.ordinal(), movesLeft - 1, moves + nextKey, possibleMoves );
                }
            }
        }
        else {
            results = moves+" ";
        }
        return results;
    }
}