The Eight Queens Problem refers to a puzzle where you place eight chess queens on an 8×8 chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal. This solver uses a recursive function, solveQueens, to attempt to place queens in every single combination until a solution is found. The solveQueens function adds queens one row at a time, but a separate isSolution function checks every queen’s diagonals to see whether any of them threaten each other. Finally, for dramatic effect, each frame of the computation is stored in an arraylist that is displayed one frame at a time for the user to see. By the time the animation starts loading, the problem has already been solved fully, and the sketch simply plays back the solution!
Code for the animation follows。 You can edit and run this code on the KTBYTE Coder
|
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 |
int boardRectSize = 50; boolean[][] board = new boolean[8][8]; PImage queen; ArrayList<boolean[][]> tries = new ArrayList<boolean[][]>(); void setup() { //size(8*boardRectSize, 8*boardRectSize); size(400, 400); boardRectSize = width / board.length; queen = loadImage("https://i.imgur.com/SDiocmg.png"); queen.resize(boardRectSize, boardRectSize); frameRate(99999); solveQueens(board, 0); } void draw() { int index = frameCount; if (index < tries.size()) { drawBoard(tries.get(index)); } else { noLoop(); //end program } } boolean hasQueen(boolean[][] board, int x, int y) { if (x >= 0 && x < board.length && y >= 0 && y < board[x].length && board[x][y] == true) return true; return false; } boolean isSolution(boolean[][] board) { //save copy for drawing: boolean[][] cp = new boolean[board.length][board[0].length]; for (int i=0; i<board.length; i++) { for (int j=0; j<board[0].length; j++) { cp[i][j] = board[i][j]; } } tries.add(cp); for (int i=0; i<board.length; i++) { int queenLoc = -1; //find the queen in this column for (int j=0; j<board[i].length; j++) { if (board[i][j]) { if (queenLoc != -1) return false; queenLoc = j; } } if (queenLoc == -1) continue; for (int k=1; k<8; k++) { //check diagonals if (hasQueen(board, i+k, queenLoc+k)) return false; if (hasQueen(board, i-k, queenLoc+k)) return false; if (hasQueen(board, i+k, queenLoc-k)) return false; if (hasQueen(board, i-k, queenLoc-k)) return false; //check rows if (hasQueen(board, i+k, queenLoc)) return false; if (hasQueen(board, i-k, queenLoc)) return false; if (hasQueen(board, i, queenLoc+k)) return false; if (hasQueen(board, i, queenLoc-k)) return false; } } return true; } boolean solveQueens(boolean[][] board, int curRow) { if (curRow >= board.length) return isSolution(board); if (!isSolution(board)) return false; //exit if board not valid already for (int i=0; i<board[curRow].length; i++) { //try each position board[curRow][i] = true; if (solveQueens(board, curRow+1)) { return true; } board[curRow][i] = false; } return false; } void drawBoard(boolean[][] board) { background(0); rectMode(CORNER); //draw rectangles using topleft corner as coordinate ellipseMode(CORNER); for (int i=0; i<board.length; i++) { for (int j=0; j<board[i].length; j++) { fill(255); rect(i*boardRectSize, j*boardRectSize, boardRectSize, boardRectSize); if ((i+j) % 2 == 1) { fill(0); rect(i*boardRectSize, j*boardRectSize, boardRectSize, boardRectSize); } if (board[i][j]) { //fill(100, 100, 255); //ellipse(i*boardRectSize, j*boardRectSize, boardRectSize, boardRectSize); image(queen, i*boardRectSize, j*boardRectSize, boardRectSize, boardRectSize); } } } } |