Created
October 29, 2015 06:31
-
-
Save hoenirvili/961fccd36ecd1cedd74e to your computer and use it in GitHub Desktop.
queen nxn
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
package queen | |
import ( | |
"fmt" | |
"time" | |
"github.com/hoenirvili/Main/util" | |
) | |
// BackTrack is the main function that | |
// that will execute recursivly | |
// finding all the possible solutions | |
func BackTrack(row int) bool { | |
if row >= N { | |
return true | |
} | |
for i := 0; i < N; i++ { | |
PrintBoard() | |
fmt.Println() | |
time.Sleep(4 * time.Millisecond) | |
util.ClearScr() | |
if CheckInstance(i, row) == true { | |
Board[i][row] = "Q" | |
PrintBoard() | |
fmt.Println() | |
time.Sleep(70 * time.Millisecond) | |
util.ClearScr() | |
if BackTrack(row + 1) { | |
return true | |
} | |
Board[i][row] = "." | |
} | |
} | |
return false | |
} |
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
package queen | |
import ( | |
"fmt" | |
"log" | |
) | |
const ( | |
queen = "Q" | |
empty = "." | |
) | |
// Board that stores | |
// our empty spaces and Queens on the table | |
var Board [][]string | |
// N contains an integer that | |
// mean a board of N x N | |
var N int | |
//Init just set's the | |
// nXn value | |
func Init(num int) { | |
N = num | |
} | |
// NewBoard an funciont that creates | |
// a new Board type | |
func NewBoard() { | |
if N > 0 { | |
Board = make([][]string, N) | |
for i := 0; i < N; i++ { | |
Board[i] = make([]string, N) | |
} | |
} else { | |
log.Println("Please init N first") | |
} | |
// set all members to be dot. | |
for i := 0; i < N; i++ { | |
for j := 0; j < N; j++ { | |
Board[i][j] = empty | |
} | |
} | |
} | |
// PrintBoard just echo's | |
// our Board | |
func PrintBoard() { | |
var i, j int | |
fmt.Printf("\t\t\tQUEEN %d X %d \t\t\t\n\n\n", N, N) | |
fmt.Println() | |
for i = 0; i < N; i++ { | |
for j = 0; j < N; j++ { | |
fmt.Printf("\t%s", Board[i][j]) | |
} | |
fmt.Printf("\t\n\n") | |
} | |
fmt.Println() | |
} |
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
package queen | |
// CheckInstance verifys if | |
// if we have a quen on a row/col | |
// if we have a quuen on prime diagonal | |
// if we have a queen on the second diagonal | |
func CheckInstance(row, col int) bool { | |
// check col | |
for i, j := 0, 0; i < N && j < N; i, j = i+1, j+1 { | |
if Board[i][col] == queen || Board[row][j] == queen { | |
return false | |
} | |
} | |
//prim diagonal | |
if row > col { | |
startLine := row - col | |
for i, j := startLine, 0; i < N && j < N; i, j = i+1, j+1 { | |
if Board[i][j] == queen { | |
return false | |
} | |
} | |
} else { | |
startCol := col - row | |
for i, j := 0, startCol; i < N && j < N; i, j = i+1, j+1 { | |
if Board[i][j] == queen { | |
return false | |
} | |
} | |
} | |
// second diagonal | |
for i, j := row, col; i < N && j > 0; i, j = i+1, j-1 { | |
if Board[i][j] == queen { | |
return false | |
} | |
} | |
for i, j := row, col; i > 0 && j < N; i, j = i-1, j+1 { | |
if Board[i][j] == queen { | |
return false | |
} | |
} | |
return true | |
} |
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
package util | |
import ( | |
"fmt" | |
"os" | |
"os/exec" | |
"runtime" | |
) | |
// @Global in this pkg | |
// Declare our own holder type | |
// to hold all our func definition handlers | |
// for every clear screen type | |
// [windows,linux] | |
var holder map[string]func() | |
func newMapFunc() { | |
holder = make(map[string]func()) | |
holder["linux"] = func() { | |
// At first almost every component is empty | |
command := exec.Command("clear") | |
// Direct to what screen to point our function | |
command.Stdout = os.Stdout | |
command.Run() | |
} | |
holder["windows"] = func() { | |
// At first almost every component is empty | |
command := exec.Command("cls") | |
// Direct the to the coresponding output | |
command.Stdout = os.Stdout | |
command.Run() | |
} | |
} | |
// ClearScr a funcion that test if | |
// our platform is supported and executes | |
// that specific function | |
func ClearScr() { | |
newMapFunc() | |
var osType = runtime.GOOS | |
run := holder[osType] | |
switch osType { | |
case "darwin": | |
fmt.Println("Mac os not supported") | |
break | |
case "linux": | |
run() | |
case "windows": | |
run() | |
} | |
} |
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
package main | |
import ( | |
"fmt" | |
"os" | |
"strconv" | |
"github.com/hoenirvili/Main/queen" | |
"github.com/hoenirvili/Main/util" | |
) | |
func start() { | |
var arg = os.Args | |
if len(arg) < 2 { | |
panic("Plase enter one argument") | |
} | |
number, err := strconv.Atoi(arg[1]) | |
if err != nil { | |
panic("Wrong data type, please enter a valid number") | |
} | |
queen.Init(number) | |
queen.NewBoard() | |
queen.PrintBoard() | |
} | |
func main() { | |
util.ClearScr() | |
start() | |
if queen.BackTrack(0) == true && queen.N > 3 || queen.N == 1 { | |
queen.PrintBoard() | |
} else { | |
fmt.Println("We don't have any") | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment