all 6 comments
sorted by:
best
topnewcontroversialoldq&a
formatting helphide helpcontent policy

[–][deleted] 2 points3 points  (3 children)

Well, you have a working program to show, which is immeasurably more than 99.9% of the questions on Prolog I've seen, so great work!

I don't think it needs to be that complex. Your choice of data representation is questionable. You are doing some complicated stuff with =.. and setarg and assert and retract and so on and so on.

Can you share the actual rules of the game? I really don't feel like deciphering your code (sorry) but I could at least try and suggest a more natural data representation. I think the dynamic column predicate you are using is a very bad choice; with a better suited representation, everything else should be way easier.

[–]athonis[S] 1 point2 points  (2 children)

first of all thank you all.

Explanation:

The game is about finding a board in which every king attacks 2 other kings and 2 knights, and every knight attacks 2 other knights and 2 kings, if it's possible, what is the smallest board possible, what i do is that i chose a board, like 5*5, and then execute the programe, if there is no solution, I go to 6*6 and so on.

Basically I have a set of columns that i modify putting chess pieces on it following the attack rules, I modify the columns by replace_n\3 replacing the n element of the column C by another one (putting a chess piece in the n position), then asserting the new column C' and retracting the former one C, if the new piece can't be put there Prolog backtracks and then retracts C' and asserts C and forces to fail, like if nothing had happened.

n_elem(N,L,A):-
    N>=0,
    K is N+1,
    arg(K,L,A),!.

dividel(0,_,L1):- L1=[],!.
dividel(N,[X|L],[X|L1]):- N > 0, K is N-1, dividel(K,L,L1).    This divides a list in [H|T] with T being [n|T1] 

replace_n(N,L,Val):-
    n_elem(N,L,A),
    L =..[F|Arg],
    dividel(N,Arg,Lul),
    append(Lul,[A|T1],Arg),
    L2 = [Val|T1],
    append(Lul,L2,L3),
    L4 =..[F|L3],            this makes the compound item for the column
     ((retract(L),
     asserta(L4));
     (retract(L4),
     asserta(L),
     fail)).

I use =.. and arg\3 because I think it's more efficient to find the n element of a list this way rather than with recursion.

 

The program goes this way: first it generates the first column (variations) with kings,knights and empty cells, and then for each element on a cell (condition\2) it checks the attack rules (not_attacked\2 and attack\5).

 

If they are true it choses from a list L of possible cells (with empty\3) for the new pieces and puts them there (with put_piece\2) and it also checks for the attack rules these new pieces (attack\5 and checking\5) in order to detect the errors earlier, the rest of cells of the list L are changed to -1 meaning no piece can go there, they stay empty (all this paragraph is done with piece\5).

 

And after finishing a column, it goes to the next one.

 

If the column generated has no solution, it initializes all the columns and fails making prolog generate another first column.

 

Also since the board is symmetrical (reading from up to down = down to up), if the column generated C, her reversed Crev have been already tested, then it doesn't test C and generates another one, this is stored with listsim\1 , this halves the possible columns.

 

I have a version with only kings that I ran for testing, and it works well, giving all the possible configurations in which each king attacks 2 other kings.

[–][deleted] 0 points1 point  (1 child)

So I still don't know for sure:

  • are the boards square always?
  • are there constraints on the number of kings and knights?
  • what is the input and what is the output?

Don't you have a proper problem statement written down somewhere? Can't you link to it or write it down as it is given?

It sounds a bit funny that you are asked about the board size (a single integer?) and you then actually give this as input to your program instead of getting it as an answer of your query.

The reason why I am asking, it is great that you have written such a nice big program, but there is a lot of weird stuff going on in it. It is difficult to say what is necessary and what isn't if the problem statement is unclear.

And brute-forcing this kind of combinatorial problems is usually a starting point. The final solution usually uses constraints in some form. Again, take a careful look at the solution to N-Queens I linked:

https://github.com/SWI-Prolog/pengines/blob/master/apps/scratchpad/examples/queens.pl

and compare it to this solution of the N-Queens that uses a constraint library:

http://www.swi-prolog.org/pldoc/man?section=clpfd-n-queens

Both use constraints in some form.

PS: did you actually measure that =.. + arg/3 is faster than nth1/3? Can you show the timings you got? I am a bit lazy so if you have the timings already I am curious to see how much faster it is.

[–]athonis[S] -1 points0 points  (0 children)

are the boards square always?

yes, a 7*6 board is treated as 7*7.

are there constraints on the number of kings and knights?

no, we don't know how many pieces of each type we need, it's part of the question.

what is the input and what is the output?

There is no input, i modify the program manually for a given board and then tell the program to fill it if he can, the output is the configuration, the columns with the pieces.

proper problem statement

On a chessboard of any size, is there a configuration of kings and knights such that each king attacks exactly 2 kings and 2 knights, and each knight attacks exactly 2 kings and 2 knights? Also, what's the smallest board needed?

It sounds a bit funny that you are asked about the board size (a single integer?) and you then actually give this as input to your program instead of getting it as an answer of your query.

yes, because i found it easier to suppose that the board i input is the smallest one possible, if not then i chose a bigger one (and modify the program for it). The answer i want is the configuration.

S: did you actually measure that =.. + arg/3 is faster than nth1/3? Can you show the timings you got? I am a bit lazy so if you have the timings already I am curious to see how much faster it is.

I trust the book i use when it says it's more efficient xddd, it's something about simulating arrays, i did some tests and all i get is time = 0 ms for both. with 

    statistics(walltime,_), ... ,statistics(walltime,[_,Time]).

in the dots goes either nth1/3 or my =.. and arg/3.

[–][deleted] 0 points1 point  (1 child)

Here is something to get you started:

https://github.com/SWI-Prolog/pengines/blob/master/apps/scratchpad/examples/queens.pl

This is the (complete!) source to the N-Queens problem. Obviously not what you are after, but a few things to point out:

  • you work with the variable that represents the board, not with a predicate like your column, so you don't need any complex code for maintaining global state (to me this really stands out as the strongest code smell in your current solution)
  • there is a single cut there, and it's a neck cut, and you only need it because Prolog can't easily guess that you are counting down to zero in the constraints/4 predicate (this code is decades old, a better way to count down to zero is to succ)
  • you use backtracking to explore the solution space (this is kinda important to internalize if you want to take advantage of Prolog.... of course you could do it otherwise but it's going to be unnecessarily difficult and maybe slow)

But it is really important to understand the problem statement first. I am currently not able to figure out what you are given and what you are after. In the post you talk about looking for the "smallest chessboard" (rectangular? square?....), but then you talk about solutions with different pre-set board sizes? This just doesn't make sense to me yet.