Created
February 20, 2014 03:04
-
-
Save kamiyaowl/9106393 to your computer and use it in GitHub Desktop.
8 Queen Problem with Scala
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
| import scala.collection.immutable.IndexedSeq | |
| object EightQueen { | |
| def main(args:Array[String]):Unit = { | |
| val DISABLE = "X" | |
| //Queen pattern | |
| val Identifier = "Q" | |
| def upToDown(x:Int, y:Int) = (for(i <- 0 - {if(x < y) x else y} to 7 - {if(x > y) x else y}) yield (x + i,y + i)) | |
| def downToUp(x:Int, y:Int) = (for(i <- 0 - {if(x < 7 - y) x else 7 - y} to 7 - {if(x > 7 - y) x else 7 - y}) yield (x + i,y - i)) | |
| def horizontal(x:Int,y:Int) = (for(i <- 0 to 7) yield (i, y)) | |
| def vertical(x:Int,y:Int) = (for(i <- 0 to 7) yield (x, i)) | |
| def disableArea(x:Int, y:Int) = { | |
| upToDown(x,y) ++ downToUp(x,y) ++ horizontal(x,y) ++ vertical(x,y) | |
| } | |
| def disableMap(x:Int, y:Int) = { | |
| ((for(p <- disableArea(x,y)) yield { p -> DISABLE }).toMap) | |
| } | |
| def printBoard(b:Map[(Int,Int),String]) = { | |
| println("========================") | |
| for(j <- 0 to 7 ; i <- 0 to 7) | |
| { | |
| if(i == 0) println("") | |
| if(b.contains((i,j))) print(" " + b((i,j)) + " ") | |
| else print(" ") | |
| } | |
| println("") | |
| } | |
| def putPiece(b:Map[(Int,Int),String], x:Int, y:Int): Map[(Int,Int),String] = { | |
| b ++ disableMap(x,y) ++ Map((x,y) -> Identifier) | |
| } | |
| val allTarget = for(i <- 0 to 7 ; j <- 0 to 7) yield (i,j) | |
| def searchEmpty(targets:IndexedSeq[(Int,Int)],b: Map[(Int,Int),String] = Map(),depth:Int = 0) : Map[(Int,Int),String] = { | |
| var result:Map[(Int,Int),String] = Map() | |
| if(depth == 7) b | |
| else if(targets.isEmpty) Map() | |
| else { | |
| if(!b.contains(targets.head)){ | |
| result = searchEmpty(allTarget,putPiece(b,targets.head._1,targets.head._2),depth + 1) | |
| } | |
| if(!result.isEmpty) result | |
| else searchEmpty(targets.tail,b,depth) | |
| } | |
| } | |
| /* search all point */ | |
| var t = allTarget | |
| do { | |
| val result = searchEmpty(t) | |
| if(!result.isEmpty) printBoard(result) | |
| t = t.tail | |
| } while(!t.isEmpty) | |
| } | |
| } |
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
| ======================== | |
| Q X X X X X X X | |
| X X X Q X X X X | |
| X Q X X X X X X | |
| X X X X X X Q X | |
| X X Q X X X X X | |
| X X X X X X X X | |
| X X X X X X X Q | |
| X X X X Q X X X | |
| ======================== | |
| X X Q X X X X X | |
| Q X X X X X X X | |
| X X X X X Q X X | |
| X Q X X X X X X | |
| X X X X Q X X X | |
| X X X X X X Q X | |
| X X X Q X X X X | |
| X X X X X X X X | |
| ======================== | |
| X Q X X X X X X | |
| X X X X X Q X X | |
| Q X X X X X X X | |
| X X Q X X X X X | |
| X X X X Q X X X | |
| X X X X X X X Q | |
| X X X Q X X X X | |
| X X X X X X X X | |
| ======================== | |
| X Q X X X X X X | |
| X X X X X Q X X | |
| X X Q X X X X X | |
| Q X X X X X X X | |
| X X X Q X X X X | |
| X X X X X X X Q | |
| X X X X Q X X X | |
| X X X X X X X X | |
| ======================== | |
| X Q X X X X X X | |
| X X X X X X Q X | |
| X X X X Q X X X | |
| X X Q X X X X X | |
| Q X X X X X X X | |
| X X X Q X X X X | |
| X X X X X X X X | |
| X X X X X X X Q | |
| ======================== | |
| X Q X X X X X X | |
| X X X X X Q X X | |
| X X Q X X X X X | |
| X X X X X X Q X | |
| X X X Q X X X X | |
| Q X X X X X X X | |
| X X X X Q X X X | |
| X X X X X X X X | |
| ======================== | |
| X Q X X X X X X | |
| X X X X Q X X X | |
| X X Q X X X X X | |
| X X X X X X X Q | |
| X X X Q X X X X | |
| X X X X X X X X | |
| Q X X X X X X X | |
| X X X X X Q X X | |
| ======================== | |
| X Q X X X X X X | |
| X X X X Q X X X | |
| X X Q X X X X X | |
| X X X X X X X X | |
| X X X X X X Q X | |
| X X X Q X X X X | |
| X X X X X Q X X | |
| Q X X X X X X X | |
| ======================== | |
| X Q X X X X X X | |
| X X X X X Q X X | |
| Q X X X X X X X | |
| X X Q X X X X X | |
| X X X X Q X X X | |
| X X X X X X X Q | |
| X X X Q X X X X | |
| X X X X X X X X | |
| ======================== | |
| X X X X Q X X X | |
| X Q X X X X X X | |
| X X X Q X X X X | |
| Q X X X X X X X | |
| X X Q X X X X X | |
| X X X X X X X Q | |
| X X X X X Q X X | |
| X X X X X X X X | |
| ======================== | |
| Q X X X X X X X | |
| X X X Q X X X X | |
| X Q X X X X X X | |
| X X X X X X Q X | |
| X X Q X X X X X | |
| X X X X X X X X | |
| X X X X X X X Q | |
| X X X X Q X X X | |
| ======================== | |
| Q X X X X X X X | |
| X X Q X X X X X | |
| X X X X X X Q X | |
| X Q X X X X X X | |
| X X X Q X X X X | |
| X X X X X X X Q | |
| X X X X X X X X | |
| X X X X Q X X X | |
| ======================== | |
| Q X X X X X X X | |
| X X Q X X X X X | |
| X X X X Q X X X | |
| X X X X X X Q X | |
| X Q X X X X X X | |
| X X X Q X X X X | |
| X X X X X Q X X | |
| X X X X X X X X | |
| ======================== | |
| Q X X X X X X X | |
| X X Q X X X X X | |
| X X X X X X X Q | |
| X X X X X Q X X | |
| X X X Q X X X X | |
| X Q X X X X X X | |
| X X X X Q X X X | |
| X X X X X X X X | |
| ======================== | |
| Q X X X X X X X | |
| X X Q X X X X X | |
| X X X X Q X X X | |
| X X X X X X X Q | |
| X X X X X X X X | |
| X X X Q X X X X | |
| X Q X X X X X X | |
| X X X X X X Q X | |
| ======================== | |
| Q X X X X X X X | |
| X X Q X X X X X | |
| X X X X X X X X | |
| X X X X X X Q X | |
| X X X Q X X X X | |
| X X X X X X X Q | |
| X X X X Q X X X | |
| X Q X X X X X X | |
| ======================== | |
| X X Q X X X X X | |
| Q X X X X X X X | |
| X X X X X Q X X | |
| X Q X X X X X X | |
| X X X X Q X X X | |
| X X X X X X Q X | |
| X X X Q X X X X | |
| X X X X X X X X | |
| ======================== | |
| Q X X X X X X X | |
| X X Q X X X X X | |
| X X X X X X Q X | |
| X Q X X X X X X | |
| X X X Q X X X X | |
| X X X X X X X Q | |
| X X X X X X X X | |
| X X X X Q X X X | |
| ======================== | |
| X X X Q X X X X | |
| Q X X X X X X X | |
| X X Q X X X X X | |
| X X X X X Q X X | |
| X Q X X X X X X | |
| X X X X X X Q X | |
| X X X X Q X X X | |
| X X X X X X X X | |
| ======================== | |
| Q X X X X X X X | |
| X X X Q X X X X | |
| X X X X X X Q X | |
| X X Q X X X X X | |
| X X X X X Q X X | |
| X Q X X X X X X | |
| X X X X Q X X X | |
| X X X X X X X X | |
| ======================== | |
| Q X X X X X X X | |
| X X X Q X X X X | |
| X Q X X X X X X | |
| X X X X X X Q X | |
| X X Q X X X X X | |
| X X X X X X X X | |
| X X X X X X X Q | |
| X X X X Q X X X | |
| ======================== | |
| Q X X X X X X X | |
| X X X Q X X X X | |
| X Q X X X X X X | |
| X X X X X X Q X | |
| X X X X X X X X | |
| X X Q X X X X X | |
| X X X X X X X Q | |
| X X X X X Q X X | |
| ======================== | |
| Q X X X X X X X | |
| X X X Q X X X X | |
| X Q X X X X X X | |
| X X X X Q X X X | |
| X X X X X X X Q | |
| X X X X X X X X | |
| X X Q X X X X X | |
| X X X X X Q X X | |
| ======================== | |
| Q X X X X X X X | |
| X X X X Q X X X | |
| X Q X X X X X X | |
| X X X X X X X X | |
| X X X X X X Q X | |
| X X X Q X X X X | |
| X X X X X X X Q | |
| X X Q X X X X X | |
| ======================== | |
| X X X Q X X X X | |
| Q X X X X X X X | |
| X X X X Q X X X | |
| X Q X X X X X X | |
| X X X X X Q X X | |
| X X Q X X X X X | |
| X X X X X X Q X | |
| X X X X X X X X | |
| ======================== | |
| Q X X X X X X X | |
| X X X Q X X X X | |
| X Q X X X X X X | |
| X X X X X X Q X | |
| X X Q X X X X X | |
| X X X X X X X X | |
| X X X X X X X Q | |
| X X X X Q X X X | |
| ======================== | |
| Q X X X X X X X | |
| X X X X X Q X X | |
| X X X Q X X X X | |
| X Q X X X X X X | |
| X X X X X X X Q | |
| X X Q X X X X X | |
| X X X X X X X X | |
| X X X X X X Q X | |
| ======================== | |
| X X Q X X X X X | |
| Q X X X X X X X | |
| X X X X X Q X X | |
| X X X Q X X X X | |
| X Q X X X X X X | |
| X X X X X X Q X | |
| X X X X Q X X X | |
| X X X X X X X X | |
| ======================== | |
| Q X X X X X X X | |
| X X Q X X X X X | |
| X X X X X X Q X | |
| X Q X X X X X X | |
| X X X Q X X X X | |
| X X X X X X X Q | |
| X X X X X X X X | |
| X X X X Q X X X | |
| ======================== | |
| Q X X X X X X X | |
| X X X X Q X X X | |
| X Q X X X X X X | |
| X X X X X X X X | |
| X X X X X X Q X | |
| X X X Q X X X X | |
| X X X X X X X Q | |
| X X Q X X X X X | |
| ======================== | |
| Q X X X X X X X | |
| X X X X Q X X X | |
| X Q X X X X X X | |
| X X X X X Q X X | |
| X X Q X X X X X | |
| X X X X X X Q X | |
| X X X Q X X X X | |
| X X X X X X X X | |
| ======================== | |
| Q X X X X X X X | |
| X X X X Q X X X | |
| X Q X X X X X X | |
| X X X X X Q X X | |
| X X Q X X X X X | |
| X X X X X X Q X | |
| X X X X X X X X | |
| X X X Q X X X X | |
| ======================== | |
| X X X X Q X X X | |
| Q X X X X X X X | |
| X X X X X Q X X | |
| X X X Q X X X X | |
| X Q X X X X X X | |
| X X X X X X Q X | |
| X X Q X X X X X | |
| X X X X X X X X | |
| ======================== | |
| Q X X X X X X X | |
| X X X X Q X X X | |
| X Q X X X X X X | |
| X X X X X Q X X | |
| X X Q X X X X X | |
| X X X X X X Q X | |
| X X X Q X X X X | |
| X X X X X X X X | |
| ======================== | |
| Q X X X X X X X | |
| X X Q X X X X X | |
| X X X X Q X X X | |
| X Q X X X X X X | |
| X X X X X X X Q | |
| X X X X X X X X | |
| X X X Q X X X X | |
| X X X X X X Q X | |
| ======================== | |
| Q X X X X X X X | |
| X X X Q X X X X | |
| X Q X X X X X X | |
| X X X X Q X X X | |
| X X X X X X X Q | |
| X X X X X X X X | |
| X X Q X X X X X | |
| X X X X X Q X X | |
| ======================== | |
| X X Q X X X X X | |
| Q X X X X X X X | |
| X X X X X Q X X | |
| X Q X X X X X X | |
| X X X X Q X X X | |
| X X X X X X Q X | |
| X X X Q X X X X | |
| X X X X X X X X | |
| ======================== | |
| Q X X X X X X X | |
| X X Q X X X X X | |
| X X X X X X Q X | |
| X Q X X X X X X | |
| X X X X X X X Q | |
| X X X X Q X X X | |
| X X X X X X X X | |
| X X X Q X X X X | |
| ======================== | |
| Q X X X X X X X | |
| X X X X X X Q X | |
| X Q X X X X X X | |
| X X X X X Q X X | |
| X X X X X X X Q | |
| X X X X X X X X | |
| X X X X Q X X X | |
| X X Q X X X X X | |
| ======================== | |
| Q X X X X X X X | |
| X X X Q X X X X | |
| X Q X X X X X X | |
| X X X X X X Q X | |
| X X Q X X X X X | |
| X X X X X X X X | |
| X X X X X X X Q | |
| X X X X Q X X X | |
| ======================== | |
| X X X X X Q X X | |
| Q X X X X X X X | |
| X X X X Q X X X | |
| X Q X X X X X X | |
| X X X X X X X | |
| X X Q X X X X X | |
| X X X X X X Q X | |
| X X X Q X X X X | |
| ======================== | |
| Q X X X X X X X | |
| X X X X X Q X X | |
| X Q X X X X X X | |
| X X X X X X Q X | |
| X X X X X X X X | |
| X X Q X X X X X | |
| X X X X X X X Q | |
| X X X Q X X X X | |
| ======================== | |
| Q X X X X X X X | |
| X X Q X X X X X | |
| X X X X X Q X X | |
| X Q X X X X X X | |
| X X X X X X X X | |
| X X X X X X X Q | |
| X X X Q X X X X | |
| X X X X X X Q X | |
| ======================== | |
| Q X X X X X X X | |
| X X X X Q X X X | |
| X Q X X X X X X | |
| X X X X X Q X X | |
| X X Q X X X X X | |
| X X X X X X Q X | |
| X X X Q X X X X | |
| X X X X X X X X | |
| ======================== | |
| Q X X X X X X X | |
| X X X Q X X X X | |
| X Q X X X X X X | |
| X X X X X X X Q | |
| X X X X X Q X X | |
| X X X X X X X X | |
| X X Q X X X X X | |
| X X X X Q X X X | |
| ======================== | |
| X X Q X X X X X | |
| Q X X X X X X X | |
| X X X X X X Q X | |
| X Q X X X X X X | |
| X X X X X X X Q | |
| X X X X X Q X X | |
| X X X Q X X X X | |
| X X X X X X X X | |
| ======================== | |
| Q X X X X X X X | |
| X X Q X X X X X | |
| X X X X X X Q X | |
| X Q X X X X X X | |
| X X X X X X X X | |
| X X X X X X X Q | |
| X X X X X Q X X | |
| X X X Q X X X X | |
| ======================== | |
| Q X X X X X X X | |
| X X X Q X X X X | |
| X Q X X X X X X | |
| X X X X X X Q X | |
| X X X X X X X X | |
| X X Q X X X X X | |
| X X X X X X X Q | |
| X X X X X Q X X | |
| ======================== | |
| X X X X X X Q X | |
| Q X X X X X X X | |
| X X X X X X X Q | |
| X Q X X X X X X | |
| X X X X Q X X X | |
| X X Q X X X X X | |
| X X X X X X X X | |
| X X X Q X X X X | |
| ======================== | |
| Q X X X X X X X | |
| X X X X X X Q X | |
| X Q X X X X X X | |
| X X X X X Q X X | |
| X X Q X X X X X | |
| X X X X X X X X | |
| X X X X X X X Q | |
| X X X Q X X X X | |
| ======================== | |
| Q X X X X X X X | |
| X X Q X X X X X | |
| X X X X X X Q X | |
| X Q X X X X X X | |
| X X X Q X X X X | |
| X X X X X X X Q | |
| X X X X X X X X | |
| X X X X Q X X X | |
| ======================== | |
| Q X X X X X X X | |
| X X X Q X X X X | |
| X Q X X X X X X | |
| X X X X X X Q X | |
| X X Q X X X X X | |
| X X X X X X X X | |
| X X X X X X X Q | |
| X X X X Q X X X | |
| ======================== | |
| Q X X X X X X X | |
| X X X X Q X X X | |
| X Q X X X X X X | |
| X X X X X X X X | |
| X X X X X X Q X | |
| X X Q X X X X X | |
| X X X X X X X Q | |
| X X X X X Q X X | |
| ======================== | |
| Q X X X X X X X | |
| X X X X Q X X X | |
| X Q X X X X X X | |
| X X X X X Q X X | |
| X X Q X X X X X | |
| X X X X X X Q X | |
| X X X Q X X X X | |
| X X X X X X X X | |
| ======================== | |
| X X X Q X X X X | |
| Q X X X X X X X | |
| X X X X Q X X X | |
| X Q X X X X X X | |
| X X X X X Q X X | |
| X X Q X X X X X | |
| X X X X X X Q X | |
| X X X X X X X X | |
| ======================== | |
| Q X X X X X X X | |
| X X Q X X X X X | |
| X X X X Q X X X | |
| X Q X X X X X X | |
| X X X X X X X Q | |
| X X X X X X X X | |
| X X X Q X X X X | |
| X X X X X X Q X | |
| ======================== | |
| X X X X X X X Q | |
| Q X X X X X X X | |
| X X X Q X X X X | |
| X Q X X X X X X | |
| X X X X X X X X | |
| X X X X X Q X X | |
| X X Q X X X X X | |
| X X X X Q X X X | |
| ======================== | |
| Q X X X X X X X | |
| X X X X X X X Q | |
| X Q X X X X X X | |
| X X X X Q X X X | |
| X X X X X X Q X | |
| X X X X X X X X | |
| X X X Q X X X X | |
| X X X X X Q X X | |
| ======================== | |
| Q X X X X X X X | |
| X X X X Q X X X | |
| X X X X X X X Q | |
| X Q X X X X X X | |
| X X X X X X X X | |
| X X Q X X X X X | |
| X X X X X Q X X | |
| X X X Q X X X X | |
| ======================== | |
| Q X X X X X X X | |
| X X X X Q X X X | |
| X Q X X X X X X | |
| X X X X X X X Q | |
| X X Q X X X X X | |
| X X X X X X Q X | |
| X X X Q X X X X | |
| X X X X X X X X | |
| ======================== | |
| Q X X X X X X X | |
| X X X Q X X X X | |
| X Q X X X X X X | |
| X X X X Q X X X | |
| X X X X X X X Q | |
| X X X X X X X X | |
| X X Q X X X X X | |
| X X X X X Q X X | |
| ======================== | |
| Q X X X X X X X | |
| X X X X X Q X X | |
| X Q X X X X X X | |
| X X X X X X Q X | |
| X X X X X X X X | |
| X X X X X X X Q | |
| X X Q X X X X X | |
| X X X X Q X X X | |
| ======================== | |
| Q X X X X X X X | |
| X X X Q X X X X | |
| X Q X X X X X X | |
| X X X X X X Q X | |
| X X Q X X X X X | |
| X X X X X X X X | |
| X X X X X X X Q | |
| X X X X Q X X X | |
| ======================== | |
| X X Q X X X X X | |
| Q X X X X X X X | |
| X X X X X Q X X | |
| X Q X X X X X X | |
| X X X X X X X X | |
| X X X X X X Q X | |
| X X X Q X X X X | |
| X X X X X X X Q |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment