/*
Tic Tac Toe avoidance in Picat.
From Richard Wiseman
http://richardwiseman.wordpress.com/2013/11/15/its-the-friday-puzzle-233/
"""
Can you place six X’s on this noughts and crosses board without making three-in-a-row in any direction?
"""
This model assumes that it's not a trick question (which it very well might be)
Yes, there are two different ways:
0 1 1
1 0 1
1 1 0
----------
1 1 0
1 0 1
0 1 1
Hmm, I assume that this mean that just the 'X's (1's) should don't have three-in-a-row.
Both these solutions give one three-in-a-row for the 'O's (0's).
For the general problem, for a NxN matrix, placing NxN-N 'X's without any
row, column, or diagonal with N 'X', here are the number of solutions for each N.
[N,#solutions]
[1,1]
[2,0]
[3,2]
[4,10]
[5,48]
[6,270]
[7,2004]
[8,15406]
[counts=[1,0,2,10,48,270,2004,15406]]
This sequence is not in OEIS:
http://oeis.org/search?q=1%2C0%2C2%2C10%2C48%2C270%2C2004%2C15406&sort=&language=english&go=Search
With the symmetry breaking that X[1,1] = 0
[1,1]
[2,0]
[3,1]
[4,3]
[5,13]
[6,67]
[7,411]
[8,2921]
[9,23633]
If we also require that the 0's should not give three-in-a-row, then we
have a slightly different result
[1,0]
[2,0]
[3,0]
[4,10]
[5,46]
[6,270]
[7,2002]
[counts=[0,0,0,10,46,270,2002]]
This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
See also my Picat page: http://www.hakank.org/picat/
*/
% import util.
import cp.
main => go.
%
% Standard problem, one solution
%
go =>
ttt(3,X),
println(X),
nl.
%
% Standard problem, using findall
%
go2 =>
Counts = [],
foreach(N in 1..7)
time2(All = findall(X, ttt(N,X))),
Len = All.length,
println([N,Len]),
Counts := Counts ++ [Len]
end,
println([counts=Counts]),
nl.
%
% Standard problem, using using solve_all
%
go3 =>
Counts = [],
foreach(N in 1..8)
(
ttt2(N,All) ->
Len := All.length
;
Len := 0
),
println([N,Len]),
Counts := Counts ++ [Len]
end,
println([counts=Counts]),
nl.
% Both Xs and Os should not be three-in-a-row
% findall N=1..7
go4 =>
Counts = [],
foreach(N in 1..7)
time2(All = findall(X, ttt3(N,X))),
Len = All.length,
println([N,Len]),
Counts := Counts ++ [Len]
end,
println([counts=Counts]),
nl.
%
% Standard problem with symmetry breaking X[1,1] = 0
%
go5 =>
Counts = [],
foreach(N in 1..9)
time2(All = findall(X, ttt4(N,X))),
Len = All.length,
println([N,Len]),
Counts := Counts ++ [Len]
end,
println([counts=Counts]),
nl.
%
% Standard problem:
% 'X's should not give three-in-a-row (no symmetry breaking)
%
ttt(N, X) =>
M = N*N-N,
P = N-1,
X = new_array(N,N),
X :: 0..1,
sum([X[I,J] : I in 1..N, J in 1..N]) #= M,
foreach(I in 1..N)
sum([X[I,J] : J in 1..N]) #<= P,
sum([X[J,I] : J in 1..N]) #<= P
end,
% Diagonals
sum([X[I,I] : I in 1..N]) #<= P,
sum([X[I,N-I+1] : I in 1..N]) #<= P,
solve([],X).
% using solve_all
ttt2(N, Sols) =>
M = N*N-N,
P = N-1,
X = new_array(N,N),
X :: 0..1,
sum([X[I,J] : I in 1..N, J in 1..N]) #= M,
foreach(I in 1..N)
sum([X[I,J] : J in 1..N]) #<= P,
sum([X[J,I] : J in 1..N]) #<= P
end,
% Diagonals
sum([X[I,I] : I in 1..N]) #<= P,
sum([X[I,N-I+1] : I in 1..N]) #<= P,
Sols=solve_all([],X).
% If we also require that both Xs and Ys should not give
% three-in-a-row
ttt3(N, X) =>
M = N*N-N,
P = N-1,
X = new_array(N,N),
X :: 0..1,
Y = new_array(N,N),
Y :: 0..1,
% Y is the complementary matrix
foreach(I in 1..N, J in 1..N) X[I,J] + Y[I,J] #= 1 end,
sum([X[I,J] : I in 1..N, J in 1..N]) #= M,
foreach(I in 1..N)
sum([X[I,J] : J in 1..N]) #<= P,
sum([X[J,I] : J in 1..N]) #<= P
end,
% Diagonals
sum([X[I,I] : I in 1..N]) #<= P,
sum([X[I,N-I+1] : I in 1..N]) #<= P,
foreach(I in 1..N)
sum([Y[I,J] : J in 1..N]) #<= P,
sum([Y[J,I] : J in 1..N]) #<= P
end,
% Diagonals
sum([Y[I,I] : I in 1..N]) #<= P,
sum([Y[I,N-I+1] : I in 1..N]) #<= P,
solve([],X).
% Symmetry breaking: X[1,1] = 0
ttt4(N, X) =>
M = N*N-N,
P = N-1,
X = new_array(N,N),
X :: 0..1,
sum([X[I,J] : I in 1..N, J in 1..N]) #= M,
foreach(I in 1..N)
sum([X[I,J] : J in 1..N]) #<= P,
sum([X[J,I] : J in 1..N]) #<= P
end,
% Diagonals
sum([X[I,I] : I in 1..N]) #<= P,
sum([X[I,N-I+1] : I in 1..N]) #<= P,
% symmery breaking
X[1,1] #= 0,
solve([],X).