骑士之旅问题 - 存储有效移动然后迭代
Knight's tour Problem - storing the valid moves then iterating
我试图编写骑士的巡回赛问题（8X8 棋盘），但不知何故我无法让它工作。
我没有探索所有可能的骑士动作，而是存储它并一个一个地迭代它但是
程序在打印结果之前终止。
在评论中标记错误代码和（无耻地复制）工作代码。
提前致谢:)
*if the board is traversed, print answer and return
* find all possible moves from given position
* for everyPosition in possiblePosition
* place the knight at everyPosition
* call the same function for the new position
* remove the knight from that position
import java.util.*;
import java.util.Map.Entry;
class Solution {
static int [][] res;
static int N;
static int row[];
static int col[];
public static void init(int n) { //initialize the array
res=new int[n][n];//n or N is the size of board which is 8
N=n;
for(int i=0;i<res.length;i++) {
for(int j=0;j<res[0].length;j++) {
res[i][j]=-1;
}
}
}
public static void print(int[][] res) { //helper function to print the 2d array
for(int i=0;i<res.length;i++) {
for(int j=0;j<res[0].length;j++) {
System.out.print(res[i][j]+" ");
}
System.out.println();
}
System.out.println();
}
static boolean isValid(int r,int c){//check if the knight's move is inside the board then return true(<8 && >0)
return (r>=0 && c>=0 && r<N && c<N && res[r][c] == -1);
}
public static boolean solve(int a,int b,int sizeOfBoard,int count,int row[],int col[]) {
if(count==64)//if the board is traversed
{
System.out.println(":)");
print(res);
return true;
}
//**buggy code start**
ArrayList<ArrayList<Integer>>possibleKnightMoves=possibleKnightMoves(a,b,sizeOfBoard);
for(int i=0;i<possibleKnightMoves.size();i++) {//iterate over every possible knight move and check if the knight can be placed there or not
possibleKnightMoves=possibleKnightMoves(a,b,sizeOfBoard);
int x= possibleKnightMoves.get(i).get(0);
int y= possibleKnightMoves.get(i).get(1);
if(isValid(x,y)) {
res[x][y]=count;
if(solve(x,y,sizeOfBoard,count+1,row,col)) {
return true;
}else
{res[x][y]=-1;
}
}
}
//**buggy code end**
//**perfect working code, uncomment me and comment the buggy code(only for reference)**
// for(int i=0;i<N;i++) {
// int x=a+row[i];
// int y=b+col[i];
// if(isValid(x,y)) {
// res[x][y]=count;
// if(solve(x,y,sizeOfBoard,count+1,row,col))
// return true;//knight can be placed
// else
// res[x][y]=-1;
//
// }
//
// }
//**perfect working code end**
return false;//knight cant be placed at the square
}
public static ArrayList<ArrayList<Integer>> possibleKnightMoves(int a,int b,int sizeOfBoard) {
int x=a;
int y=b;
ArrayList<ArrayList<Integer>> result= new ArrayList<ArrayList<Integer>>();
for(int i=0;i<N;i++) {
x=x+row[i];// x,y represent all the possible knight moves from knight's current position
y=y+col[i];
result.add(new ArrayList<Integer>(Arrays.asList(x,y)));//add the moves to all possible moves list
}
return result;
}
public static void knightTour(int n) {
init(n);
res[0][0]=0;//set starting position
int array[]={2, 1, -1, -2, -2, -1, 1, 2 };//array 1 and array 2 represent the set of knight moves from (x,y) eg: x+2,y+1
row=array;
int array2[]={1, 2, 2, 1, -1, -2, -2, -1 };
col=array2;
solve(0,0,n,1,array,array2);//starting from 0,0 with count =1 as knight is already paced on 0,0
}
public static void main(String args[]) {
N=8;
knightTour(8);
init(8);
res[3][3]=1;
}
}
问题是possibleKnightMoves方法，你写的地方
for(int i=0;i<N;i++) {
x=x+row[i];current position
y=y+col[i];
result.add(new ArrayList<Integer>(Arrays.asList(x,y)));
}
应该是
for(int i=0;i<N;i++) {
x=a+row[i];//Changed here
y=b+col[i];//and here
result.add(new ArrayList<Integer>(Arrays.asList(x,y)));
}
否则，x和y的值相加。
现在是，但是还有一个问题：你的代码运行速度太慢了。
考虑这一行
ArrayList<ArrayList<Integer>>possibleKnightMoves=possibleKnightMoves(a,b,sizeOfBoard);
for 循环中的这一行：
possibleKnightMoves=possibleKnightMoves(a,b,sizeOfBoard);
你多次重复做同样的事情，如果你只是删除 for 循环中的行，结果不会改变但运行速度更快。所以我想这就是你想要的：
import java.util.*;
import java.util.Map.Entry;
public class Main {
static int [][] res;
static int N;
static int row[];
static int col[];
public static void init(int n) { //initialize the array
res=new int[n][n];//n or N is the size of board which is 8
N=n;
for(int i=0;i<res.length;i++) {
for(int j=0;j<res[0].length;j++) {
res[i][j]=-1;
}
}
}
public static void print(int[][] res) { //helper function to print the 2d array
for(int i=0;i<res.length;i++) {
for(int j=0;j<res[0].length;j++) {
if(res[i][j] == -1) {
System.out.print("n ");
}else {
System.out.print(res[i][j]+" ");
}
}
System.out.println();
}
System.out.println();
}
static boolean isValid(int r,int c){//check if the knight's move is inside the board then return true(<8 && >0)
return (r>=0 && c>=0 && r<N && c<N && res[r][c] == -1);
}
public static boolean solve(int a,int b,int sizeOfBoard,int count,int row[],int col[]) {
if(count==64){
System.out.println(":)");
print(res);
return true;
}
ArrayList<ArrayList<Integer>>possibleKnightMoves=possibleKnightMoves(a,b,sizeOfBoard);
for(int i=0;i<possibleKnightMoves.size();i++) {//iterate over every possible knight move and check if the knight can be placed there or not
int x= possibleKnightMoves.get(i).get(0);
int y= possibleKnightMoves.get(i).get(1);
if(isValid(x,y)) {
res[x][y]=count;
if(solve(x,y,sizeOfBoard,count+1,row,col)) {
return true;
}else{
res[x][y]=-1;
}
}
}
return false;//knight cant be placed at the square
}
public static ArrayList<ArrayList<Integer>> possibleKnightMoves(int a,int b,int sizeOfBoard) {
ArrayList<ArrayList<Integer>> result= new ArrayList<ArrayList<Integer>>();
for(int i=0;i<N;i++) {
int x=a+row[i];//Changed here
int y=b+col[i];//and here
result.add(new ArrayList<Integer>(Arrays.asList(x,y)));
}
return result;
}
public static void knightTour(int n) {
init(n);
res[0][0]=0;//set starting position
int array[]={2, 1, -1, -2, -2, -1, 1, 2 };//array 1 and array 2 represent the set of knight moves from (x,y) eg: x+2,y+1
row=array;
int array2[]={1, 2, 2, 1, -1, -2, -2, -1 };
col=array2;
solve(0,0,n,1,array,array2);//starting from 0,0 with count =1 as knight is already paced on 0,0
}
public static void main(String args[]) {
N=8;
knightTour(8);
init(8);
res[3][3]=1;
}
}
我试图编写骑士的巡回赛问题（8X8 棋盘），但不知何故我无法让它工作。
我没有探索所有可能的骑士动作，而是存储它并一个一个地迭代它但是 程序在打印结果之前终止。
在评论中标记错误代码和（无耻地复制）工作代码。
提前致谢:)
*if the board is traversed, print answer and return
* find all possible moves from given position
* for everyPosition in possiblePosition
* place the knight at everyPosition
* call the same function for the new position
* remove the knight from that position
import java.util.*;
import java.util.Map.Entry;
class Solution {
static int [][] res;
static int N;
static int row[];
static int col[];
public static void init(int n) { //initialize the array
res=new int[n][n];//n or N is the size of board which is 8
N=n;
for(int i=0;i<res.length;i++) {
for(int j=0;j<res[0].length;j++) {
res[i][j]=-1;
}
}
}
public static void print(int[][] res) { //helper function to print the 2d array
for(int i=0;i<res.length;i++) {
for(int j=0;j<res[0].length;j++) {
System.out.print(res[i][j]+" ");
}
System.out.println();
}
System.out.println();
}
static boolean isValid(int r,int c){//check if the knight's move is inside the board then return true(<8 && >0)
return (r>=0 && c>=0 && r<N && c<N && res[r][c] == -1);
}
public static boolean solve(int a,int b,int sizeOfBoard,int count,int row[],int col[]) {
if(count==64)//if the board is traversed
{
System.out.println(":)");
print(res);
return true;
}
//**buggy code start**
ArrayList<ArrayList<Integer>>possibleKnightMoves=possibleKnightMoves(a,b,sizeOfBoard);
for(int i=0;i<possibleKnightMoves.size();i++) {//iterate over every possible knight move and check if the knight can be placed there or not
possibleKnightMoves=possibleKnightMoves(a,b,sizeOfBoard);
int x= possibleKnightMoves.get(i).get(0);
int y= possibleKnightMoves.get(i).get(1);
if(isValid(x,y)) {
res[x][y]=count;
if(solve(x,y,sizeOfBoard,count+1,row,col)) {
return true;
}else
{res[x][y]=-1;
}
}
}
//**buggy code end**
//**perfect working code, uncomment me and comment the buggy code(only for reference)**
// for(int i=0;i<N;i++) {
// int x=a+row[i];
// int y=b+col[i];
// if(isValid(x,y)) {
// res[x][y]=count;
// if(solve(x,y,sizeOfBoard,count+1,row,col))
// return true;//knight can be placed
// else
// res[x][y]=-1;
//
// }
//
// }
//**perfect working code end**
return false;//knight cant be placed at the square
}
public static ArrayList<ArrayList<Integer>> possibleKnightMoves(int a,int b,int sizeOfBoard) {
int x=a;
int y=b;
ArrayList<ArrayList<Integer>> result= new ArrayList<ArrayList<Integer>>();
for(int i=0;i<N;i++) {
x=x+row[i];// x,y represent all the possible knight moves from knight's current position
y=y+col[i];
result.add(new ArrayList<Integer>(Arrays.asList(x,y)));//add the moves to all possible moves list
}
return result;
}
public static void knightTour(int n) {
init(n);
res[0][0]=0;//set starting position
int array[]={2, 1, -1, -2, -2, -1, 1, 2 };//array 1 and array 2 represent the set of knight moves from (x,y) eg: x+2,y+1
row=array;
int array2[]={1, 2, 2, 1, -1, -2, -2, -1 };
col=array2;
solve(0,0,n,1,array,array2);//starting from 0,0 with count =1 as knight is already paced on 0,0
}
public static void main(String args[]) {
N=8;
knightTour(8);
init(8);
res[3][3]=1;
}
}
问题是possibleKnightMoves方法，你写的地方
for(int i=0;i<N;i++) {
x=x+row[i];current position
y=y+col[i];
result.add(new ArrayList<Integer>(Arrays.asList(x,y)));
}
应该是
for(int i=0;i<N;i++) {
x=a+row[i];//Changed here
y=b+col[i];//and here
result.add(new ArrayList<Integer>(Arrays.asList(x,y)));
}
否则，x和y的值相加。
现在是，但是还有一个问题：你的代码运行速度太慢了。
考虑这一行
ArrayList<ArrayList<Integer>>possibleKnightMoves=possibleKnightMoves(a,b,sizeOfBoard);
for 循环中的这一行：
possibleKnightMoves=possibleKnightMoves(a,b,sizeOfBoard);
你多次重复做同样的事情，如果你只是删除 for 循环中的行，结果不会改变但运行速度更快。所以我想这就是你想要的：
import java.util.*;
import java.util.Map.Entry;
public class Main {
static int [][] res;
static int N;
static int row[];
static int col[];
public static void init(int n) { //initialize the array
res=new int[n][n];//n or N is the size of board which is 8
N=n;
for(int i=0;i<res.length;i++) {
for(int j=0;j<res[0].length;j++) {
res[i][j]=-1;
}
}
}
public static void print(int[][] res) { //helper function to print the 2d array
for(int i=0;i<res.length;i++) {
for(int j=0;j<res[0].length;j++) {
if(res[i][j] == -1) {
System.out.print("n ");
}else {
System.out.print(res[i][j]+" ");
}
}
System.out.println();
}
System.out.println();
}
static boolean isValid(int r,int c){//check if the knight's move is inside the board then return true(<8 && >0)
return (r>=0 && c>=0 && r<N && c<N && res[r][c] == -1);
}
public static boolean solve(int a,int b,int sizeOfBoard,int count,int row[],int col[]) {
if(count==64){
System.out.println(":)");
print(res);
return true;
}
ArrayList<ArrayList<Integer>>possibleKnightMoves=possibleKnightMoves(a,b,sizeOfBoard);
for(int i=0;i<possibleKnightMoves.size();i++) {//iterate over every possible knight move and check if the knight can be placed there or not
int x= possibleKnightMoves.get(i).get(0);
int y= possibleKnightMoves.get(i).get(1);
if(isValid(x,y)) {
res[x][y]=count;
if(solve(x,y,sizeOfBoard,count+1,row,col)) {
return true;
}else{
res[x][y]=-1;
}
}
}
return false;//knight cant be placed at the square
}
public static ArrayList<ArrayList<Integer>> possibleKnightMoves(int a,int b,int sizeOfBoard) {
ArrayList<ArrayList<Integer>> result= new ArrayList<ArrayList<Integer>>();
for(int i=0;i<N;i++) {
int x=a+row[i];//Changed here
int y=b+col[i];//and here
result.add(new ArrayList<Integer>(Arrays.asList(x,y)));
}
return result;
}
public static void knightTour(int n) {
init(n);
res[0][0]=0;//set starting position
int array[]={2, 1, -1, -2, -2, -1, 1, 2 };//array 1 and array 2 represent the set of knight moves from (x,y) eg: x+2,y+1
row=array;
int array2[]={1, 2, 2, 1, -1, -2, -2, -1 };
col=array2;
solve(0,0,n,1,array,array2);//starting from 0,0 with count =1 as knight is already paced on 0,0
}
public static void main(String args[]) {
N=8;
knightTour(8);
init(8);
res[3][3]=1;
}
}