N Queen

n_queen.cpp

#include <iostream>
#include <vector>
#include <list>
#include <stack>
 
using namespace std;
 
int BOARD_SIZE = 8;
 
bool update_board(vector<vector<int>>& board,int i, int j){
    int up = j-1;
    int down = j+1;
    if(board[j][i] == 1) return false;
    for(int y=0; y<board.size() ;++y){
        board[y][i] = 1;
    }
    for(int x=i+1; x<BOARD_SIZE; ++x){
        board[j][x] = 1;
        if(up >= 0) board[up--][x] = 1;
        if(down < board.size()) board[down++][x] = 1;
    }
    return true;
}
 
list<int> get_next_list(list<int> l){
    vector<vector<int>> board(BOARD_SIZE,vector<int>(BOARD_SIZE,0));
    int x=0;
    for(auto y : l){
        update_board(board,x++,y);
    }
    list<int> ret;
    for(int y=0 ; y<board.size() ; ++y){
        if(board[y][l.size()] == 0) ret.push_back(y);
    }
    return ret;
}
 
int main(int argc, char *argv[]){
    if(argc > 1) BOARD_SIZE = stoi(argv[1]);
    stack<list<int>> s;
    int cnt=0;
    for(int i=0; i<BOARD_SIZE ; ++i) s.push(list<int>(1,i));
    while(!s.empty()){
        list<int> l = s.top();
        s.pop();
        list<int> next_list = get_next_list(l);
        for(auto i : next_list){
            list<int> temp(l.begin(),l.end());
            temp.push_back(i);
            if(temp.size() == BOARD_SIZE) cnt++;
            else s.push(temp);
        }
    }
    cout << cnt << endl;
}

n_queen.go

package main

import "fmt"
import "container/list"
import "os"
import "strconv"

var BOARD_SIZE = 8

func update_board(board [][]int, i int, j int) bool{
    up := j-1
    down := j+1
    if board[j][i] == 1 {
        return false
    } else {
        for y:=0; y<len(board); y++ {
            board[y][i] = 1
        }
        for x:=i+1; x<BOARD_SIZE ; x++ {
            board[j][x] = 1
            if up >= 0 {
                board[up][x] = 1
                up--
            } 
            if down < len(board) {
                board[down][x] = 1
                down++
            }
        }
        return true
    }
}

func get_next_list(l *list.List) *list.List{
    board := make([][]int,BOARD_SIZE)
    for i := 0; i<len(board); i++ {
        board[i] = make([]int,BOARD_SIZE)
    }
    x := 0
    for y := l.Front(); y != nil; y = y.Next() {
        update_board(board,x,y.Value.(int))
        x++
    }
    ret := list.New()
    for y:=0; y<len(board); y++ {
        if board[y][l.Len()] == 0 {
            ret.PushBack(y)
        }
    }
    return ret
}

func main(){
    if len(os.Args) > 1 {
        BOARD_SIZE,_ = strconv.Atoi(os.Args[1])
    }
    s := list.New()
    cnt := 0
    for i:=0; i<BOARD_SIZE; i++ {
        temp := list.New()
        temp.PushBack(i)
        s.PushFront(temp)
    }
    for s.Len() != 0 {
        l := s.Front().Value.(*list.List)
        s.Remove(s.Front())
        var next_list list.List = *get_next_list(l)
        for i:=next_list.Front(); i != nil; i = i.Next() {
            temp := list.New()
            temp.PushBackList(l)
            temp.PushBack(i.Value.(int))
            if temp.Len() == BOARD_SIZE {
                cnt++
            }else {
                s.PushFront(temp)
            }
        }
    }
    fmt.Println(cnt)
}

n_queen.java

import java.util.*;
public class n_queen{
    public static int BOARD_SIZE = 8;
    public static boolean update_board(int[][] board,int i,int j ){
        int up = j-1;
        int down = j+1;
        if(board[j][i] == 1) return false;
        else{
            for(int y =0; y<board.length ; ++y){
                board[y][i] = 1;
            }
            for(int x=i+1; x<BOARD_SIZE; ++x){
                board[j][x] = 1;
                if(up >= 0) board[up--][x] = 1;
                if(down < board.length) board[down++][x] = 1;
            }
            return true;
        }
    }

    public static List<Integer> get_next_list(List<Integer> l){
        int[][] board = new int[BOARD_SIZE][BOARD_SIZE];
        int x = 0;
        for(Integer y : l){
            update_board(board,x++,y);
        }
        List<Integer> ret = new LinkedList<Integer>();
        for(int y=0; y<board.length; ++y){
            if(board[y][l.size()] == 0) ret.add(y);
        }
        return ret;
    }
    public static void main(String[] args) {
        if(args.length > 0) BOARD_SIZE = Integer.parseInt(args[0]);
        Deque<LinkedList<Integer>> s = new ArrayDeque<LinkedList<Integer>>();
        int cnt = 0;
        for(int i=0; i<BOARD_SIZE; ++i){ 
            LinkedList<Integer> l = new LinkedList<Integer>();
            l.add(i);
            s.push(l);
        }
        while(s.peek() != null){
            List<Integer> l = s.peek();
            s.remove();
            List<Integer> next_list = get_next_list(l);
            for(Integer i : next_list){
                LinkedList<Integer> temp = new LinkedList<Integer>(l);
                temp.add(i);
                if(temp.size() == BOARD_SIZE) cnt++;
                else s.push(temp);
            }
        }
        System.out.println(cnt);
    }
}

n_queen.rb

$board_size = 8

def update_board(board,i,j)
    up = j-1
    down = j+1
    if board[j][i] == 1 then return false
    else
        for y in 0...board.length do
            board[y][i] = 1
        end
        for x in (i+1)...$board_size do
            board[j][x] =  1
            if up >= 0
                board[up][x] = 1
                up -= 1
            end
            if down < board.length
                board[down][x] = 1
                down += 1
            end
        end
        return true
    end
end

def get_next_list(l)
    board = Array.new($board_size){Array.new($board_size,0)}
    x = 0
    for y in l do
        update_board(board,x,y)
        x += 1
    end
    ret = Array.new()
    for y in 0...board.length do
        if board[y][l.length] == 0
            ret.push(y)
        end
    end
    return ret;
end

if __FILE__ == $0
    if ARGV.length > 0
        $board_size = ARGV[0].to_i
    end
    s = Array.new
    cnt = 0
    for i in 0...$board_size do
        s.push(Array.new(1,i))
    end
    while !s.empty? do
        l = s.last
        s.pop
        next_list = get_next_list(l)
        for i in next_list do
            temp = l.clone
            temp.push(i)
            if temp.length == $board_size
                cnt += 1
            else
                s.push(temp)
            end
        end
    end
    puts cnt
end

n_queen.scala

object NQueen {
  var BOARD_SIZE : Int = 8;
  def update_board(board : Array[Array[Int]], i : Int, j : Int) : Boolean = {
    var up = j-1
    var down = j+1
    if(board(j)(i) == 1) return false
    else{
      board.foreach(a => a(i) = 1)
      for(x <- i+1 until BOARD_SIZE){
        board(j)(x) = 1
        if(up >= 0){ board(up)(x) = 1; up -= 1;}
        if(down < board.length){ board(down)(x) = 1; down += 1;}
      }
      return true
    }
  }

  def get_next_list(l : List[Int]) : List[Int] = {
    val board : Array[Array[Int]] = Array.ofDim(BOARD_SIZE,BOARD_SIZE)
    var x = 0
    for(y <- l){
      update_board(board,x,y)
      x += 1
    }
    var ret = List.empty[Int]
    for(y <- 0 until board.length) if(board(y)(l.length) == 0) ret +:= y
    return ret.reverse
  }

  def main(args: Array[String]) {
    if(args.length > 0) BOARD_SIZE = args(0).toInt
    val s = scala.collection.mutable.Stack.empty[List[Int]]
    var cnt = 0
    for(i <- 0 until BOARD_SIZE) s.push(List(i))
    while(s.nonEmpty){
      var l = s.pop
      val next_list = get_next_list(l);
      for(i <- next_list){
        var temp = l
        temp :+= i
        if(temp.length == BOARD_SIZE) cnt += 1
        else s.push(temp)
      }
    }
    println(cnt)
  }
}

n_queen_py2.py

# -*- coding: utf-8 -*-

import sys

BOARD_SIZE = 8

def update_board(board,i,j):
    up = j-1
    down = j+1
    if board[j][i] == 1:
        return False
    else:
        for y in xrange(len(board)):
            board[y][i] = 1
        for x in xrange(i+1,BOARD_SIZE):
            board[j][x] = 1
            if up >= 0:
                board[up][x] = 1
                up -= 1
            if down < len(board):
                board[down][x] = 1
                down += 1
        return True

def get_next_list(l):
    board = [[0 for i in xrange(BOARD_SIZE)] for row in xrange(BOARD_SIZE)]
    x = 0
    for y in l:
        update_board(board,x,y)
        x += 1
    ret = []
    for y in xrange(len(board)):
        if board[y][len(l)] == 0:
            ret.append(y)
    return ret

if __name__ == '__main__':
    if len(sys.argv) > 1:
        BOARD_SIZE = int(sys.argv[1])
    s = []
    cnt = 0
    for i in xrange(BOARD_SIZE):
        s.append([i])
    while s:
        l = s.pop()
        next_list = get_next_list(l)
        for i in next_list:
            temp = list(l)
            temp.append(i)
            if len(temp) == BOARD_SIZE:
                cnt += 1
            else:
                s.append(temp)
    print(cnt)

n_queen_py3.py

# -*- coding: utf-8 -*-

import sys

BOARD_SIZE = 8

def update_board(board,i,j):
    up = j-1
    down = j+1
    if board[j][i] == 1:
        return False
    else:
        for y in range(len(board)):
            board[y][i] = 1
        for x in range(i+1,BOARD_SIZE):
            board[j][x] = 1
            if up >= 0:
                board[up][x] = 1
                up -= 1
            if down < len(board):
                board[down][x] = 1
                down += 1
        return True

def get_next_list(l):
    board = [[0 for i in range(BOARD_SIZE)] for row in range(BOARD_SIZE)]
    x = 0
    for y in l:
        update_board(board,x,y)
        x += 1
    ret = []
    for y in range(len(board)):
        if board[y][len(l)] == 0:
            ret.append(y)
    return ret

if __name__ == '__main__':
    if len(sys.argv) > 1:
        BOARD_SIZE = int(sys.argv[1])
    s = []
    cnt = 0
    for i in range(BOARD_SIZE):
        s.append([i])
    while s:
        l = s.pop()
        next_list = get_next_list(l)
        for i in next_list:
            temp = list(l)
            temp.append(i)
            if len(temp) == BOARD_SIZE:
                cnt += 1
            else:
                s.append(temp)
    print(cnt)