N-Queens in 110 languages

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
Michael Sherwin
Posts: 3046
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

N-Queens in 110 languages

Post by Michael Sherwin » Thu Nov 21, 2019 2:15 am

Also has more than one algorithm for some. Python for example has six.
https://rosettacode.org/wiki/N-queens_problem
I hate if statements. Pawns demand if statements. Therefore I hate pawns.

jdart
Posts: 3835
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: N-Queens in 110 languages

Post by jdart » Thu Nov 21, 2019 2:59 am

Only one for Perl (well, two if you count Perl6)? Isn't the Perl motto "There Is More Than One Way To Do It ?"

--Jon

Michael Sherwin
Posts: 3046
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: N-Queens in 110 languages

Post by Michael Sherwin » Thu Nov 21, 2019 5:19 am

jdart wrote:
Thu Nov 21, 2019 2:59 am
Only one for Perl (well, two if you count Perl6)? Isn't the Perl motto "There Is More Than One Way To Do It ?"

--Jon
Forget that, I have just found my dream compiler, QB64, from looking at the list! It is backwards compatible with QBasic 4.5 and yet is a 2019 compiler. It even has 64 bit integers, double buffering, up to 8k graphics, and a full screen borderless display. It is as easy as:

_SCREEN 1920, 1080
_FULL_SCREEN

Then there are all the primitive drawing functions as well as sprites and alpha blending and vsync, event handlers and apparently much more including OpenGL. I had a full screen up and drawing circles in about ten minutes. Never have I seen something so easy to allow me to do full screen graphics so quickly. And it compiles to C++ code that it automatically then compiles to native machine code without any additional setup at all. I think I read that it uses the mingwin(?) c++ compiler and the SDL graphics toolkit. I'm not sure I remember correctly. I'll have to take another look tomorrow. I wish someone would do something this simple and powerful for C!!
I hate if statements. Pawns demand if statements. Therefore I hate pawns.

mar
Posts: 2007
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: N-Queens in 110 languages

Post by mar » Thu Nov 21, 2019 9:17 am

QB64 is a pile of junk, sorry. Simply look at what it transpiles to C for this simple proc:

Code: Select all

SUB mysub
       DIM a
       a = 10
END SUB

Code: Select all

void SUB_MYSUB(){
qbs *tqbs;
ptrszint tmp_long;
int32 tmp_fileno;
uint32 qbs_tmp_base=qbs_tmp_list_nexti;
uint8 *tmp_mem_static_pointer=mem_static_pointer;
uint32 tmp_cmem_sp=cmem_sp;
#include "data1.txt"
mem_lock *sf_mem_lock;
new_mem_lock();
sf_mem_lock=mem_lock_tmp;
sf_mem_lock->type=3;
if (new_error) goto exit_subfunc;
do{
if(!qbevent)break;evnt(2);}while(r);
do{
*_SUB_MYSUB_SINGLE_A= 10 ;
if(!qbevent)break;evnt(3);}while(r);
exit_subfunc:;
free_mem_lock(sf_mem_lock);
#include "free1.txt"
if ((tmp_mem_static_pointer>=mem_static)&&(tmp_mem_static_pointer<=mem_static_limit)) mem_static_pointer=tmp_mem_static_pointer; else mem_static_pointer=mem_static;
cmem_sp=tmp_cmem_sp;
}
of course, SUB_MYSUB_SINGLE_A is a lazy-initialized global:

Code: Select all

float *_SUB_MYSUB_SINGLE_A=NULL;
if(_SUB_MYSUB_SINGLE_A==NULL){
_SUB_MYSUB_SINGLE_A=(float*)mem_static_malloc(4);
*_SUB_MYSUB_SINGLE_A=0;
}
With other words, it doesn't have true stack-allocated locals, so:
- no recursion for you
- no multithreading for you

That is unless I don't know how to declare a local variable in basic or unless basic itself doesn't support local variables at all (both are possible) :)
Martin Sedlak

Michael Sherwin
Posts: 3046
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: N-Queens in 110 languages

Post by Michael Sherwin » Thu Nov 21, 2019 12:02 pm

mar wrote:
Thu Nov 21, 2019 9:17 am
QB64 is a pile of junk, sorry. Simply look at what it transpiles to C for this simple proc:

Code: Select all

SUB mysub
       DIM a
       a = 10
END SUB

Code: Select all

void SUB_MYSUB(){
qbs *tqbs;
ptrszint tmp_long;
int32 tmp_fileno;
uint32 qbs_tmp_base=qbs_tmp_list_nexti;
uint8 *tmp_mem_static_pointer=mem_static_pointer;
uint32 tmp_cmem_sp=cmem_sp;
#include "data1.txt"
mem_lock *sf_mem_lock;
new_mem_lock();
sf_mem_lock=mem_lock_tmp;
sf_mem_lock->type=3;
if (new_error) goto exit_subfunc;
do{
if(!qbevent)break;evnt(2);}while(r);
do{
*_SUB_MYSUB_SINGLE_A= 10 ;
if(!qbevent)break;evnt(3);}while(r);
exit_subfunc:;
free_mem_lock(sf_mem_lock);
#include "free1.txt"
if ((tmp_mem_static_pointer>=mem_static)&&(tmp_mem_static_pointer<=mem_static_limit)) mem_static_pointer=tmp_mem_static_pointer; else mem_static_pointer=mem_static;
cmem_sp=tmp_cmem_sp;
}
of course, SUB_MYSUB_SINGLE_A is a lazy-initialized global:

Code: Select all

float *_SUB_MYSUB_SINGLE_A=NULL;
if(_SUB_MYSUB_SINGLE_A==NULL){
_SUB_MYSUB_SINGLE_A=(float*)mem_static_malloc(4);
*_SUB_MYSUB_SINGLE_A=0;
}
With other words, it doesn't have true stack-allocated locals, so:
- no recursion for you
- no multithreading for you

That is unless I don't know how to declare a local variable in basic or unless basic itself doesn't support local variables at all (both are possible) :)
idk, only had a brief look at it, but shouldn't it be:

Code: Select all

SUB mysub
       DIM a AS INTEGER
       a = 10
END SUB
Does that make a difference? Anyway, I was speaking from an idealistic point of view. Why couldn't MSVS have DirectX macros built right into the languages? It could be as easy as _SCREEN() to set up a DirectX surface the size and color depth of the system. Then I could write.

Code: Select all

_SCREEN_CREATE();
_SCREEN_SHOW();

int sw = _SCREEN_WIDTH();
int sh = _SCREEN_HEIGHT();
int sd = _SCREEN_DEPTH();

while(1) {
  Do_Something();
  _SCREEN_VSYNC();
  _SCREEN_FLIP();}
}

_SCREEN_HIDE();
_SCREEN_DESTROY();
ETC.
I hate if statements. Pawns demand if statements. Therefore I hate pawns.

Michael Sherwin
Posts: 3046
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: N-Queens in 110 languages

Post by Michael Sherwin » Thu Nov 21, 2019 12:21 pm

Basic Subroutines and Functions

Subroutines are useful little critters, and are used for two basic reasons.
One is when you have a given set of instructions which you use at several
points in a program. You can write the instructions one time in a subroutine
and call that subroutine whenever you want to execute those instructions.
The other reason is to logically structure your program such that related
code is placed together. This permits good, logically structured, top-down
design, and also facilitates creating libraries of pre-coded subroutines
which you can drop into a program whenever needed.

Subroutines are simple to create and use. I will use QBasic/QuickBasic as an
example, but other languages are fairly similar For simplicity I will just
use BASIC to refer to QBasic/QuickBasic. In BASIC you can have 'informal' or
'formal' subroutines. Informal subroutines are just blocks of code which are
invoked with the GOSUB command and that are terminated by a RETURN statement.
Like this:

GOSUB MySub
...

MySub:
<subroutine code>
RETURN

These informal subroutines are part of the main module code, and share all
variables with the main module.

You create a 'formal' subroutine by setting off a block of code like this:

SUB MySub
<subroutine code goes here>
END SUB

When you want to execute MySub, code this:

CALL MySub

And the subroutine will be executed. In languages like QBasic/QuickBasic
which have 'variable scoping', subroutines, by default, have their own
'local' variables. This is good, because it lets you code the subroutine
without being concerned about trashing a variable of the same name used
outside the subroutine. There are two mechanisms for the subroutine to
communicate with the rest of the program. One is by passing 'parameters' to
the subroutine when you call it. These parameters are defined in the
subroutine definition like this:

SUB MySub(P1,P2)
<subroutine code goes here>
END SUB

Defined in this way, P1 and P2 are called 'formal parameters'. When you want
to execute MySub, code this:

CALL MySub(A1,A2)

A1 and A2 are called 'arguments', and are matched 1 to 1 with the 'formal
parameters' defined in the subroutine heading. For the compiler to do this
matching efficiently, and to validate that your arguments match the formal
parameters in order, number and type, it needs to know what the formal
parameters are before it encounters the subroutine CALL. This is done by
placing a 'subroutine declaration' at the front of your main module, like
this:

DECLARE SUB MySub(P1 AS INTEGER, P2 AS DOUBLE)

This subroutine declaration is a template, telling the compiler the name of
the subroutine and the number and type of arguments which must be passed when
it is called. It is the order, type and number of the formal parameters
which is important, not the names of the parameters.

The other method to permit the subroutine to communicate to the outside
program is to explicitly declare the scope of variables to 'cross' the
subroutine boundary. From the outside program you can define a variable as
'SHARED', which means it can be seen from inside the subroutines. In the
main module do this:

DIM SHARED X AS DOUBLE

X can then be 'seen' and used inside subroutines. This can be overridden on
an individual subroutine basis by explicitly declaring variables as STATIC
inside the subroutine:

SUB MySub(P1,P2)
STATIC X AS DOUBLE
<subroutine code goes here>
END SUB

Outside this subroutine, X is 'global', but X is also a separate 'local'
variable inside this subroutine.

You also can also do it the other way around. You can declare a variable
as 'SHARED' from within a subroutine:

SUB MySub(P1,P2)
SHARED X AS DOUBLE
<subroutine code goes here>
END SUB

In this case, X is shared between this subroutine and the main module. If X
is to be shared with another subroutine, the other subroutine must also
declare X as SHARED.

Now let's look at another useful construct, the 'function'. Functions are
similar to subroutines, but have one specific difference: functions return
a value.
I hate if statements. Pawns demand if statements. Therefore I hate pawns.

tmokonen
Posts: 1037
Joined: Sun Mar 12, 2006 5:46 pm
Location: Vancouver

Re: N-Queens in 110 languages

Post by tmokonen » Thu Nov 21, 2019 10:54 pm

No COBOL or RPG versions? For shame.

AlvaroBegue
Posts: 922
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)

Re: N-Queens in 110 languages

Post by AlvaroBegue » Fri Nov 22, 2019 6:52 am

Here's a very short one in C++, without much obfuscation:

Code: Select all

#include <iostream>
#include <algorithm>
#include <vector>

const int n = 8;

bool check_permutation(std::vector<int> const &v) {
  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      if (std::abs(v[i]-v[j]) == std::abs(i-j))
	return false;
    }
  }
  return true;
}

int main() {
  std::vector<int> v(n);
  for (int i = 0; i < n; ++i)
    v[i] = i;
  
  while (std::next_permutation(v.begin(), v.end())) {
    if (check_permutation(v)) {
      for (int x : v) {
	for (int i = 0; i < n; ++i)
	  std::cout << ((i==x) ? 'X' : '_') << ' ';
	std::cout << '\n';
      }
      std::cout << '\n';
    }
  }
}

Post Reply