andron81понял. переделаю
Вроде немного очухался за выходной. Если будете делать перебор в нескольких потоках, то придется либо лочить общий ресурс, либо делать его volatile, что для больших объектов плохо.
Для отдельных локов на чрение и запись, можете использовать подобный код:
(Предупреждаю что сам по себе код бессмысленный, просто пример с расшареным ресурсом):
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.
133.
134.
135.
136.
137.
138.
139.
140.
141.
142.
143.
144.
145.
146.
147.
148.
149.
150.
151.
152.
153.
154.
155.
156.
157.
158.
159.
160.
161.
162.
163.
164.
165.
166.
167.
168.
169.
170.
171.
172.
173.
174.
175.
176.
177.
178.
179.
180.
181.
182.
183.
184.
185.
186.
187.
188.
189.
190.
191.
import java.util.concurrent.locks.ReentrantReadWriteLock;
public class Horse implements Runnable {
static final int[][] HORSE_MOVES = {{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1},{-2,1},{-1,2}};
static final int HOURSE_COUNT = 65;
static final int BOARD_DIMENSION =6;/*длина доски*/
static int[][] USED_BOARD_CELLS = new int[BOARD_DIMENSION +1][BOARD_DIMENSION +1];
static ReentrantReadWriteLock rwLock = new ReentrantReadWriteLock();
ReentrantReadWriteLock.ReadLock readLock = rwLock.readLock();
ReentrantReadWriteLock.WriteLock writeLock = rwLock.writeLock();
final int[] xPositions = new int[HOURSE_COUNT];
final int[] yPositions = new int[HOURSE_COUNT];
long depth = 0;
int threadId;
int startXPos;
int startYPos;
public Horse(int threadId, int startXPos, int startYPos )
{
this.threadId =threadId;
writeLock.lock();
try {
//Double check after obtaining write lock that cell is available
if(USED_BOARD_CELLS[startXPos][startYPos] != 0) {
//Cell is used by another Horse
throw new RuntimeException("Board cell "+startXPos + "x"+startYPos+" is already used!");
}
USED_BOARD_CELLS[startXPos][startYPos] = 1;
} finally {
//release write lock
writeLock.unlock();
}
this.startYPos =startYPos ;
this.startXPos =startXPos;
xPositions[1] = startXPos;
yPositions[1] = startYPos;
}
public static void main (String[] args) {
Thread t1 = new Thread(new Horse(1,1,2));
/*
Thread t1 = new Thread(new Horse(1,5,5));
Thread t2 = new Thread(new Horse(2,4,2));
Thread t4 = new Thread(new Horse(4,3,2));
Thread t5 = new Thread(new Horse(5,6,4));
Thread t6 = new Thread(new Horse(6,1,3));
Thread t7 = new Thread(new Horse(7,2,1));
Thread t8 = new Thread(new Horse(8,3,4));
*/
t1.start();
/* t2.start();
t3.start();
t4.start();
t5.start();
t6.start();
t7.start();
t8.start();
*/
}
public boolean tryHorse(int horseIndex) {
boolean success = true;
int xPos;
int yPos;
depth++;
//System.out.println("tryHorse("+horseIndex+")");
printState();
//logger.debug("Глубина = {}", depth);
if (horseIndex == 2) {
xPos = this.startXPos;
yPos = this.startYPos;
xPositions[horseIndex] = xPos;
yPositions[horseIndex] = yPos;
printState();
}
int i;
int j;
int nextX;
int nextY;
for(int stepIndex = 0; stepIndex < HORSE_MOVES.length; stepIndex++){
i = xPositions[horseIndex - 1];
j = yPositions[horseIndex - 1];
readLock.lock();
try {
if (i + HORSE_MOVES[stepIndex][0] >= 1 && i + HORSE_MOVES[stepIndex][0] <= BOARD_DIMENSION &&
j + HORSE_MOVES[stepIndex][1] >= 1 && j + HORSE_MOVES[stepIndex][1] <= BOARD_DIMENSION
&& USED_BOARD_CELLS[(i + HORSE_MOVES[stepIndex][0])][(j + HORSE_MOVES[stepIndex][1])] == 0) {
nextX = i + HORSE_MOVES[stepIndex][0];
nextY = j + HORSE_MOVES[stepIndex][1];
//если можно поставить коня
xPos = nextX;
yPos = nextY;
} else {
// Continue next
continue;
}
} finally {
readLock.unlock();
}
writeLock.lock();
try {
if(USED_BOARD_CELLS[startXPos][startYPos] == 1) {
//Cell is used by another Horse, skip and continue
continue;
}
USED_BOARD_CELLS[xPos][yPos] = horseIndex;/*ставим*/
} finally {
writeLock.unlock();
}
xPositions[horseIndex] = xPos;
yPositions[horseIndex] = yPos;
//System.out.println("Можно ! Передвигаем коня на "+ x1+" "+y1 +" ход "+ horseIndex);
//printState();
if (horseIndex <= BOARD_DIMENSION * BOARD_DIMENSION +1) {
if (!tryHorse(horseIndex + 1)) {
// logger.debug("Плохо ! Вынуждены убрать коня с USED_BOARD_CELLS={} y={} ", xPositions[horseIndex], yPositions[horseIndex]);
printState();
writeLock.lock();
try {
USED_BOARD_CELLS[xPositions[horseIndex]][yPositions[horseIndex]] = 0;
} finally {
writeLock.unlock();
}
//System.out.println("Плохо ! Вынуждены убрать коня "+ xPositions[horseIndex]+" "+yPositions[horseIndex] +" ход ");
xPositions[horseIndex] = 0;
yPositions[horseIndex] = 0;
}
}
}
depth--;
return success;
}
public void printState() {
System.out.println("Поток # "+ threadId);
for (int x = 1; x <= BOARD_DIMENSION; x++) {
for (int y = 1; y <= BOARD_DIMENSION; y++) {
if (this.USED_BOARD_CELLS[x][y] > 0) {
System.out.print(this.USED_BOARD_CELLS[x][y]+" ");
} else if (this.USED_BOARD_CELLS[x][y] < 0) {
System.out.print("B ");
} else if (this.USED_BOARD_CELLS[x][y] == 0) {
System.out.print("0 ");
}
}
System.out.println();
}
System.out.println();
}
public void run() {
// try{
tryHorse(2);
// }catch(Exception e) {}
}
Без обид но код я не понял, те если за 5 минут код непонятен то нет желания долго с ним копаться.
На просторах интернета нашел пример который делает перебор возможных позиций на доске для коня с заданной глубиной ходов. Код примитивный и понятный, немного его подправил (но не все). Сразу учитесь на хороших примерах и делайте тесты. Этот код написан понятно, изучите и делайте похожий на него код.На досуге можете сравнение в тестах улучшить (не печатать в строку) и попробовать деление на потоки с расшаренным ресурсом (сет с позициями и текущими ходами).
Основной класс.
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
package knight;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;
public class Knight {
public static int boardSize = 8;
static final int [] X_STEPS = {1, 2, 2, 1, -1, -2, -2, -1};
static final int [] Y_STEPS = {2, 1, -1, -2, -2, -1, 1, 2};
public Set<Position> getReachableSet(Position pos, int numberofMoves) {
return getReachableSet(pos, numberofMoves, null);
}
protected Set<Position> getReachableSet(Position pos, int numberofMoves, Set<Position> reachableSet) {
if(reachableSet == null) {
reachableSet = new HashSet<>();
}
if (!reachableSet.contains(pos)) reachableSet.add(pos);
if (numberofMoves == 0) return reachableSet;
ArrayList<Position> moves = new ArrayList<>();
for (int i = 0; i < 8; i++) {
Position candidate = new Position (pos.x + X_STEPS[i], pos.y + Y_STEPS[i]);
if (!moveIsPossible(candidate)) continue;
if (!reachableSet.contains(candidate)) {
moves.add(candidate);
}
}
for (int j = 0; j < moves.size(); j++) {
reachableSet = getReachableSet(moves.get(j), numberofMoves-1, reachableSet);
}
return reachableSet;
}
private static boolean moveIsPossible (Position pos) {
return (pos.x >= 0 && pos.x <= 7) && (pos.y >= 0 && pos.y <= 7);
}
}
Позиция, можно использовать что то готовое из awt пакета, там вроде был подобный класс. Для учебного процесса лучше свое написать
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
package knight;
public class Position implements Comparable<Position> {
/**
* The row on the chess board
*/
public int x;
/**
* The column on the chess board
*/
public int y;
/**
* Create a new position object
* @param x the row on the chess board
* @param y the column on the chess board
*/
public Position(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public int compareTo(Position o) {
if(x == o.x) {
return Integer.compare(y, o.y);
} else {
return Integer.compare(x, o.x);
}
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Position position = (Position) o;
if (x != position.x) return false;
return y == position.y;
}
@Override
public int hashCode() {
int result = x;
result = 31 * result + y;
return result;
}
@Override
public String toString() {
return "{" + x + ", " + y + "}";
}
}
На десерт, тест класс. Нужно его доработать, убрать сортировку и сделать сравнение коллекций покультурнее, без печати в строку
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
package knight;
import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;
import java.util.Set;
public class KnightTests {
Knight knight;
@Before
public void setup() {
knight = new Knight();
}
private String printSet(Collection<Position> positions)
{
StringBuffer s = new StringBuffer("\n ");
for (int x=0; x<Knight.boardSize; x++) {
s.append(x);
}
s.append("\n ");
for (int x=0; x<Knight.boardSize; x++) {
s.append("-");
}
s.append("\n");
for (int y=0; y<Knight.boardSize; y++) {
s.append(y).append("|");
for (int x=0; x<Knight.boardSize; x++) {
if (positions.contains(new Position(x, y))) {
s.append("X");
} else {
s.append(" ");
}
}
s.append("\n");
}
return s.toString();
}
private void compare(Set<Position> result, int[]... expected) {
List<Position> orderedPositions = new ArrayList<>(result);
Collections.sort(orderedPositions);
ArrayList<Position> expectedList = new ArrayList<>(expected.length);
for (int[] pos : expected) {
expectedList.add(new Position(pos[0], pos[1]));
}
Collections.sort(expectedList);
Assert.assertEquals(printSet(orderedPositions), expectedList.toString(), orderedPositions.toString());
}
@Test
public void noHop() {
Set<Position> result = knight.getReachableSet(new Position(4, 4), 0);
int expected[][] = { { 4, 4 } };
compare(result, expected);
}
@Test
public void oneHop() {
Set<Position> result = knight.getReachableSet(new Position(4, 4), 1);
int expected[][] = { {2, 3}, {2, 5}, {3, 2}, {3, 6}, {4, 4}, {5, 2}, {5, 6}, {6, 3}, {6, 5} };
compare(result, expected);
}
@Test
public void oneHopCorner() {
Set<Position> result = knight.getReachableSet(new Position(0, 0), 1);
int expected[][] = { { 0, 0 }, { 1, 2 }, { 2, 1 } };
compare(result, expected);
}
@Test
public void twoHopsCorner() {
Set<Position> result = knight.getReachableSet(new Position(0, 0), 2);
int expected[][] = { { 0, 0 }, { 0, 2 }, { 0, 4 }, { 1, 2 }, { 1, 3 },
{ 2, 0 }, { 2, 1 }, { 2, 4 }, { 3, 1 }, { 3, 3 }, { 4, 0 },
{ 4, 2 } };
compare(result, expected);
}
@Test
public void threeHops() {
Set<Position> result = knight.getReachableSet(new Position(4, 4), 3);
int expected[][] = {
{0, 1}, {0, 2}, {0, 3}, {0, 4}, {0, 5}, {0, 6}, {0, 7},
{4, 5}, {4, 4}, {4, 7}, {4, 6}, {5, 0}, {5, 1}, {5, 2}, {5, 3}, {5, 4},
{1, 0}, {1, 3}, {1, 4}, {1, 1}, {1, 2}, {1, 7}, {1, 5}, {1, 6}, {5, 7},
{5, 6}, {5, 5}, {6, 0}, {6, 1}, {6, 4}, {6, 5}, {6, 3}, {2, 1}, {2, 0},
{2, 7}, {2, 3}, {2, 4}, {2, 5}, {6, 7}, {7, 3}, {7, 4}, {7, 5}, {7, 6},
{7, 0}, {7, 1}, {7, 2}, {3, 0}, {3, 2}, {3, 1}, {3, 7}, {3, 5}, {3, 6},
{3, 3}, {3, 4}, {7, 7}, {4, 3}, {4, 2}, {4, 1}, {4, 0}
};
compare(result, expected);
}
@Test
public void fourHops() {
Set<Position> result = knight.getReachableSet(new Position(4, 4), 4);
int expected[][] = { {0, 0}, {0, 1}, {0, 2}, {0, 4}, {0, 6}, {1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6},
{1, 7}, {2, 0}, {2, 2}, {2, 3}, {2, 4}, {2, 5}, {2, 6}, {2, 7}, {3, 1}, {3, 2}, {3, 3}, {3, 5}, {3, 6},
{3, 7}, {4, 0}, {4, 1}, {4, 2}, {4, 3}, {4, 4}, {4, 5}, {4, 6}, {4, 7}, {5, 1}, {5, 2}, {5, 3}, {5, 4},
{5, 5}, {5, 6}, {5, 7}, {6, 0}, {6, 2}, {6, 3}, {6, 4}, {6, 5}, {6, 6}, {6, 7}, {7, 1}, {7, 2}, {7, 3},
{7, 5}, {7, 6}, {7, 7}
};
compare(result, expected);
}
}
|
