Skip to content

Instantly share code, notes, and snippets.

@kamiyaowl

kamiyaowl/EightQueen.scala

Created February 20, 2014 03:04
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save kamiyaowl/9106393 to your computer and use it in GitHub Desktop.
Save kamiyaowl/9106393 to your computer and use it in GitHub Desktop.
Download ZIP
8 Queen Problem with Scala
Raw
EightQueen.scala
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)
}
}
Raw
log
========================
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