Created
December 4, 2017 15:32
-
-
Save salememd/14768d529c910cffe8862b85a835b5f1 to your computer and use it in GitHub Desktop.
8 queens puzzle
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* | |
| * To change this license header, choose License Headers in Project Properties. | |
| * To change this template file, choose Tools | Templates | |
| * and open the template in the editor. | |
| */ | |
| package eigthq; | |
| import java.util.ArrayList; | |
| import java.util.LinkedList; | |
| /** | |
| * | |
| * @author Salem F. Elmrayed | |
| */ | |
| public class EigthQ { | |
| static LinkedList<int[][]> stack = new LinkedList(); | |
| static int type = 8; | |
| static int[][] bord = new int[type][type]; | |
| static int numOfQ = 0; | |
| static int[][] getCopy(int[][] a) { | |
| int[][] bordt = new int[type][type]; | |
| for (int ik = 0; ik < type; ik++) { | |
| for (int jk = 0; jk < type; jk++) { | |
| bordt[ik][jk] = a[ik][jk]; | |
| } | |
| } | |
| return bordt; | |
| } | |
| static boolean chickwin(int[][] a) { | |
| int q = 0; | |
| for (int ik = 0; ik < type; ik++) { | |
| for (int jk = 0; jk < type; jk++) { | |
| if (a[ik][jk] == 1) { | |
| q++; | |
| } | |
| } | |
| } | |
| if (q == type) { | |
| return true; | |
| } | |
| return false; | |
| } | |
| static int level(int[][] a) { | |
| int q = 0; | |
| for (int ik = 0; ik < type; ik++) { | |
| for (int jk = 0; jk < type; jk++) { | |
| if (a[ik][jk] == 2) { | |
| return ik; | |
| } | |
| } | |
| } | |
| return 3; | |
| } | |
| static int[][] play(int[][] bord) { | |
| try{ | |
| /* if(stack.size() ==0 && numOfQ !=0 ){ | |
| System.out.println(numOfQ); | |
| return bord; | |
| }*/ | |
| if (chickwin(bord)) { | |
| numOfQ++; | |
| for (int i = 0; i < type; i++) { | |
| for (int j = 0; j < type; j++) { | |
| System.out.print(bord[i][j]); | |
| } | |
| System.out.println(); | |
| } | |
| System.out.println(); | |
| System.out.println(); | |
| } | |
| int i = level(bord); | |
| for (int jk = 0; jk < type; jk++) { | |
| int[][] copy = getCopy(bord); | |
| if (setQ(copy, i, jk)) { | |
| stack.push(copy); | |
| } | |
| } | |
| return play(stack.pop()); | |
| }catch(Exception ex){ | |
| System.out.println(numOfQ); | |
| return bord; | |
| } | |
| } | |
| static boolean setQ(int[][] bord, int x, int y) { | |
| if (bord[x][y] == 2) { | |
| bord[x][y] = 1; | |
| for (int i = 0; i < type; i++) { | |
| if (i != y) { | |
| bord[x][i] = 0; | |
| } | |
| } | |
| for (int i = 0; i < type; i++) { | |
| if (i != x) { | |
| bord[i][y] = 0; | |
| } | |
| } | |
| int ii = x + 1; | |
| int jj = y + 1; | |
| /* | |
| 0 0 0 0 | |
| 0 0 1 0 | |
| 0 0 0 0 | |
| 0 0 0 0 | |
| */ | |
| while (ii <= type-1 && jj <= type-1) { | |
| bord[ii++][jj++] = 0; | |
| } | |
| ii = x - 1; | |
| jj = y - 1; | |
| while (ii >= 0 && jj >= 0) { | |
| bord[ii--][jj--] = 0; | |
| } | |
| /* | |
| 0 0 0 0 | |
| 0 1 0 0 | |
| 0 0 0 0 | |
| 0 0 0 0 | |
| */ | |
| ii = x - 1; | |
| jj = y + 1; | |
| while (ii >= 0 && jj <= type-1) { | |
| bord[ii--][jj++] = 0; | |
| } | |
| ii = x + 1; | |
| jj = y - 1; | |
| while (jj >= 0 && ii <= type-1) { | |
| bord[ii++][jj--] = 0; | |
| } | |
| return true; | |
| } | |
| return false; | |
| } | |
| public static void main(String[] args) { | |
| for (int i = 0; i < type; i++) { | |
| for (int j = 0; j < type; j++) { | |
| bord[i][j] = 2; | |
| } | |
| } | |
| bord = play(bord); | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment