Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package ch.rfin.ai.search.problems;
- import ch.rfin.ai.search.AbstractSearchProblem;
- import java.util.*;
- public class EightQueens extends AbstractSearchProblem<EightQueens.State, EightQueens.Action> {
- private static final int SIZE = 8;
- public EightQueens() {
- super(new State(0), new State(SIZE));
- }
- private State result(State state, Action move){
- int[] board = state.board;
- for(int x = 0; x < SIZE; x++){
- if(board[x + move.y * SIZE] == 1){
- return null;
- }
- }
- for(int y = 0; y < SIZE; y++){
- if(board[move.x + y * SIZE] == 1){
- return null;
- }
- }
- for(int y = 0; y < SIZE; y++){
- for(int x = 0; x < SIZE; x++){
- if(board[x + y * SIZE] == 1){
- int deltaRow = Math.abs(x - move.x);
- int deltaCol = Math.abs(y - move.y);
- if(deltaCol == deltaRow){
- return null;
- }
- }
- }
- }
- return new State(state, move);
- }
- @Override
- public Collection<Action> possibleActionsIn(State state) {
- List<Action> actions = new ArrayList<>();
- for(int y = 0; y < SIZE; y++){
- for(int x = 0; x < SIZE; x++){
- Action action = new Action(x, y);
- State after = result(state, action);
- if(after != null){
- actions.add(action);
- }
- }
- }
- return actions;
- }
- @Override
- public State transition(State state, Action action) {
- State result = result(state, action);
- if(result == null){
- throw new IllegalArgumentException("No transition for " + action + " in " + state + ".");
- }
- return result;
- }
- public static class State{
- public int queens = 0;
- public int board[] = {0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0,
- };
- public State(int queens){
- this.queens = queens;
- };
- public State(State oldState, Action action){
- board = oldState.board.clone();
- this.board[action.x + action.y * SIZE] = 1;
- this.queens = oldState.queens + 1;
- }
- @Override
- public boolean equals(Object obj) {
- return queens == ((State) obj).queens;
- }
- @Override
- public String toString() {
- String string = "State: \n queens: " + queens + "\n board: \n";
- for(int y = 0; y < SIZE; y++){
- for(int x = 0; x < SIZE; x++){
- string += board[x + y * SIZE] + " ";
- }
- string += "\n";
- }
- return string;
- }
- }
- public static class Action{
- public int x;
- public int y;
- public Action(int x, int y){
- this.x = x;
- this.y = y;
- }
- @Override
- public String toString() {
- return "Action{" +
- "x=" + x +
- ", y=" + y +
- '}';
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement