Bert Bosパズルのテストソリューション

Question

Bert Bos Puzzleで作業します。ここでは、シーケンスのすべての可能な順列（クリックまたはクリックなし）を印刷して、赤色の全体が赤くなるようにする必要があります。これは、一連のクリックの中で一番上の行をクリックしてクリックすることによって行われます。その後、次の行に移動し、そこに四角形をクリックすると、最初の行がすべて赤になります。あなたはこのようなパズルを進んで、正方形全体を赤に変えるまで進めます。

4x4四角形の可能な解決策は、最初の行で[クリック、クリック、クリックしない、クリックしない]です。下の行のいずれかのパターンに従わなくても、次の行のすべてのブロックが赤色になり、すべての四角が赤色になるまで反転し続けるだけです。

サイズNの正方形の最初の行に対して、「クリック」と「クリックしない」のすべての可能な順列をテストする述語を書こうとしています。今すぐ、色のトラックを維持して一番上の行をクリックした後、それを使用して2番目の行のどの四角形をクリックして一番上の行をすべて赤色にするかを指定します。

問題は、最初の行からのクリックによって変更された2番目の行の色を追跡する方法を理解してから、2番目の行のクリックを追跡する方法と、残りの行どんな助けでも大歓迎です。あなたは（述語の引数を使用して）に沿って行列を運ぶことができ、かつ常に現在の状態を検査するためにこれを使用します。ここでは

は@CapelliCがすでに一つの可能​​なアプローチを示唆している

state(no_click). 
state(click). 

flip(blue, red). 
flip(red, blue). 

board_permutations(0,[]):- !. 
board_permutations(N, [H|T]) :- 
    state(H), 
    N1 is N - 1, 
    board_permutations(N1, T). 

first_row_solutions([], []). 
first_row_solutions([H1, H2|T], [FirstRow|SecondRow]):- 
    H1 = click, 
    flip(H1,C), 
    flip(H2,C), 
    first_row_solutions(H2, FirstRow). 
first_row_solutions([H|T], [FRH1, FRH2, FRH3|FRT], [SR1, SR2, SR3|SRT]) :- 
    H = click, 
    flip(FRH1, C1), 
    flip(FRH2, C2), 
    flip(FRH3, C3), 
    %flip(SR1, S1), I was thinking I could keep track of the second row colors here 
    %flip(SR2, S2), 
    %flip(SR3, S3) 
    %FlipListRow1 = [C1, C2, C3 | T], 
    %FlipListRow2 = [S1, S2, S3|T], 
    first_row_solutions(H, FRH3). 


%Possible predicate to handle row 2, 3, 4 etc --> ClickList is what clicks to do on row 3 to make row 2 red, etc 
%row_n_solutions(FlipListRow2, ClickList) 


generate_board(0, [], _). 
generate_board(N, [H|T], ConstantN) :- 
    generate_row(ConstantN, H), 
    N =< 12, N >= 1, 
    N2 is N-1, 
    generate_board(N2, T, ConstantN). 

generate_row(0, []) :- !. 
generate_row(N, [H | T]) :- 
    N =< 12, N >= 1, 
    N2 is N-1, 
    H = blue, 
    generate_row(N2, T). 

test(X) :- generate_board(5,X,5). 
test1(X) :- solutions([no_click, click, no_click, no_click], X). 

Answer 1

これまでのところ、私が持っているものです任意の周囲細胞のこのアプローチを補完

、私はまた、全体のタスクにアプローチする別の方法を指摘したいと思います：私たちは、有限 フィールドからのベクトル   GF適し線形組み合わせを見つけると、このパズルを考えることができます（2 ）。クリック数は、ベクトルごとにの整数の係数で表すことができます。

ボード位置とベクトル インデックスの間に対応を確立するだけです。次のように我々はこのような関係を定義することができる：

 
n_id_x_y(N, ID, X, Y) :- 
     ID #= Y*N + X, 
     N1 #= N - 1, 
     [X,Y] ins 0..N1. 

例：私は4枚のボードのために働くマッピングを得るため4を指定

 
?- n_id_x_y(4, 6, X, Y). 
X = 2, 
Y = 1. 

注意。

これはCLP（FD）制約を使用しています例えば含め、すべての方向に動作します：

 
?- n_id_x_y(4, ID, 3, 2). 
ID = 11. 

これに基づき、我々はまた、再び彼らのユニークな指標によって示される、その隣に任意のインデックスを関連付けることができます：

 
n_id_neighbour(N, ID, NID) :- 
     n_id_x_y(N, ID, X, Y), 
     ( ( NX #= X - 1, NY #= Y 
      ; NX #= X + 1, NY #= Y 
      ) 
     ; ( NX #= X, NY #= Y - 1 
      ; NX #= X, NY #= Y + 1 
      ) 
     ), 
     n_id_x_y(N, NID, NX, NY). 

がその位置とその定義された隣人の色を反転させ任意のボードの位置をクリックします。我々は、ブールベクターを使用して1このインデックスに対応する位置の色が影響されることを示すようになる：エントリ0-0クリック例えば

 
n_id_vector(N, ID, Vs) :- 
     V #= N*N, 
     V1 #= V - 1, 
     ID in 0..V1, 
     indomain(ID), 
     findall(NID, n_id_neighbour(N, ID, NID), Ns), 
     sort([ID|Ns], IDs), 
     length(Vs, V), 
     phrase(ids_vector(IDs, 0), Vs, Zeroes), 
     maplist(=(0), Zeroes). 

ids_vector([], _) --> []. 
ids_vector([ID|IDs], Pos0) --> 
     { Gap #= ID - Pos0, 
      Pos #= ID + 1, 
      length(Zeroes, Gap), 
      maplist(=(0), Zeroes) }, 
     Zeroes, 
     [1], 
     ids_vector(IDs, Pos). 

は、正確で示される3つの他の細胞に影響を与えます  1：

 
?- n_id_vector(4, 0, Vs). 
Vs = [1, 1, 0, 0, 1, 0, 0, 0, 0|...]. 

我々は今、我々は、溶液から期待するものを説明する準備ができている：ソリューションは、係数のリストで構成され、各ベクトルのための1スカラー積の和（各ベクトルのベクトル時間係数）は、モジュロと等しく、  (1,1,...,1)に等しい。これは、の各色のセルが変更されたことを意味します。

この場合、固有の対称性のために、行列を転置する必要はありません。

我々はオーバーブール代数を推論しているという事実は、すでに細胞がクリックされる順序は、ベクトルのそれぞれが任意の溶液中で、最高1回使用する必要があることも結果に影響し、しないことを伴います。ここで

は4 × 4ボードのためのソリューションです：

 
?- n_solution(4, Cs). 
Cs = [0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1] ; 
Cs = [0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1] ; 
Cs = [0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0] ; 
Cs = [0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0] ; 
etc. 

各ソリューションは、私たちがクリックする必要があり、細胞のどの正確に示します。例えば、第一の溶液：

は、ここでは、この基板サイズのため、最長のソリューションの1つです：

そして、これが最短のいずれかです。

もちろん、この方法を他のボードsizにも適用できますESは、そのような7 × 7として：

または12 × 12：