puzzleのタグがつけられたコード一覧

Prolog マッチ棒を動かして10を3つ作るパズル

一要素置換([Bef|Tail], [Aft|Tail], (Bef, Aft)).
一要素置換([X|BefTail], [X|AftTail], Replace) :-
	一要素置換(BefTail, AftTail, Replace).

% デジタル文字の定義
デジタル文字(X) :- デジタル文字(X, _).
デジタル文字((number, Ptn),   Char) :- デジタル数字((number, Ptn), Char).
デジタル文字((operator, Ptn), Char) :- デジタル演算子((operator, Ptn), Char).

デジタル数字((number, [1, 1, 1, 1, 0, 1, 1]), 0).		% 8 の各所に対応するマッチ棒の有無を表すリスト
デジタル数字((number, [0, 0, 1, 0, 0, 1, 0]), 1).
デジタル数字((number, [0, 1, 1, 1, 1, 0, 1]), 2).
デジタル数字((number, [0, 1, 1, 0, 1, 1, 1]), 3).
デジタル数字((number, [1, 0, 1, 0, 1, 1, 0]), 4).
デジタル数字((number, [1, 1, 0, 0, 1, 1, 1]), 5).
デジタル数字((number, [1, 1, 0, 1, 1, 1, 1]), 6).
デジタル数字((number, [1, 1, 1, 0, 0, 1, 0]), 7).		% “ワ”型
デジタル数字((number, [1, 1, 1, 1, 1, 1, 1]), 8).
デジタル数字((number, [1, 1, 1, 0, 1, 1, 1]), 9).

デジタル演算子((operator, [1, 1, 0, 0]), '+').
デジタル演算子((operator, [0, 1, 0, 0]), '-').
デジタル演算子((operator, [0, 0, 1, 1]), '*').		% ×
%デジタル演算子((operator, [0, 0, 0, 1]), '/').		% /

デジタル文字列([]).
デジタル文字列([Head|Tail]) :- デジタル文字(Head), デジタル文字列(Tail).

デジタル文字列([], []).
デジタル文字列([DH|DigitString], [H|String]) :-
	デジタル文字(DH, H), デジタル文字列(DigitString, String).

棒を1本加える((Type, Ptn), (Type, PtnAfter)) :-	% 入出力がデジタル文字かは無視
	一要素置換(Ptn, PtnAfter, (0, 1)).
棒を1本減らす((Type, Ptn), (Type, PtnAfter)) :-
	一要素置換(Ptn, PtnAfter, (1, 0)).

棒を1本動かす(Chars, CharsAfter) :-
	棒を1本減らす(Chars, CharsTmp1),
	棒を1本加える(CharsTmp1, CharsAfter),
	Chars \== CharsAfter.

棒を1本加える([Char|Tail], [CharAfter|Tail]) :-
	棒を1本加える(Char, CharAfter).
棒を1本加える([X|CharsTail], [X|CharsAfterTail]) :-
	棒を1本加える(CharsTail, CharsAfterTail).

棒を1本減らす([Char|Tail], [CharAfter|Tail]) :-
	棒を1本減らす(Char, CharAfter).
棒を1本減らす([X|CharsTail], [X|CharsAfterTail]) :-
	棒を1本減らす(CharsTail, CharsAfterTail).

% 数式化 (ただし加減乗除 + - * / のみ)
数式化([X, Op1, Y, Op2, Z], Expr) :-
	current_op(Op1Priority, _, Op1),
	current_op(Op2Priority, _, Op2),
	Op1Priority =< Op2Priority
		-> ( Expr1 =.. [Op1, X, Y], Expr =.. [Op2, Expr1, Z] )
		;  ( Expr1 =.. [Op2, Y, Z], Expr =.. [Op1, X, Expr1] ).

%	?- 数式化([1, '+', 2, '+', 3], X).
%	?- 数式化([1, '*', 2, '+', 3], X).
%	?- 数式化([1, '+', 2, '*', 3], X).
%	?- 数式化([1, '*', 2, '*', 3], X).

% 長さからリストを単一化できる述語 (AZ-Prolog の length にはその機能がない故)
mylen([], 0).
mylen([_|Tail], N) :- N > 0, N1 is N - 1, mylen(Tail, N1).

append([], L, L).
append([H|T1], L, [H|T2]) :- append(T1, L, T2).

append_fold([], []).
append_fold([H|Tail], Sum) :- append_fold(Tail, TailSum), append(H, TailSum, Sum).

% 例題
?-	Q = [
		5, '-', 1, '+', 4,
		4, '*', 7, '-', 5,
		6, '-', 4, '+', 8
	],
	% A は、Q のデジタル文字列の棒を3本動かしてできるデジタル文字列で表現できる
	デジタル文字列(Enc0, Q),
	棒を1本動かす(Enc0,  Enc1),
	棒を1本動かす(Enc1, Enc2), Enc0 \== Enc2,
	棒を1本動かす(Enc2, Enc3), Enc0 \== Enc3, Enc1 \== Enc3,
	デジタル文字列(Enc3, A),
%	write(A), nl,

	% 3つの式の答えがすべて10である
	mylen(A1, 5), mylen(A2, 5), mylen(A3, 5),
	append_fold([A1, A2, A3], A),
	数式化(A1, E1), 10 is E1,	% E1 is 10 ではない
	数式化(A2, E2), 10 is E2,
	数式化(A3, E3), 10 is E3.

% 答えはおそらくこの2通り
% A = [7,-,1,+,4,4,*,4,-,6,6,-,4,+,8]
% A = [5,+,1,+,4,1,*,7,+,3,6,-,4,+,8]

TEXT [Prolog]論理パズル/正直者は誰? (失敗例)

% 嘘つき問題
/*
	正直者は誰?
	A1「ここに、嘘つきは1人いる。」
	A2「ここに、嘘つきは2人いる。」
	A3「ここに、嘘つきは3人いる。」
	A4「ここに、嘘つきは4人いる。」
	A5「ここに、嘘つきは5人いる。」

	引用('数学ガール ゲーデルの不完全性定理', page: 3).
*/

% 定義
嘘(A) :- \+(A).

正直者(P) :- 人(P), \+(嘘つき(P)).
嘘つき(P) :- 人(P), 主張(P, A), 嘘(A).

'嘘つきはN人いる'(N) :- setof(P, 嘘つき(P), L), length(L, N).

% 問題
人(a1). 主張(a1, '嘘つきはN人いる'(1)).	% 元々閉世界なので「ここに、」は不要
人(a2). 主張(a2, '嘘つきはN人いる'(2)).
人(a3). 主張(a3, '嘘つきはN人いる'(3)).
人(a4). 主張(a4, '嘘つきはN人いる'(4)).
人(a5). 主張(a5, '嘘つきはN人いる'(5)).

:- trace. % ステップ実行にて無限再帰を確認なされ
?- setof(P, 正直者(P), L).	% 正直者リスト L を求める。
%	L = [a4]

TEXT [Prolog]魔法陣<4×4> (入る値が与えられている場合)

% 4×4 行列分解
groups_4x4(
	[
		[M00, M01, M02, M03],	% 行ベクトルのリスト
		[M10, M11, M12, M13],
		[M20, M21, M22, M23],
		[M30, M31, M32, M33]
	], [
		[M00, M10, M20, M30],	% 列ベクトルのリスト
		[M01, M11, M21, M31],
		[M02, M12, M22, M32],
		[M03, M13, M23, M33]
	],
	[ M00, M11, M22, M33 ],		% 主対角線 (左上→右下)
	[ M30, M12, M21, M03 ],		%  対角線 (左下←右上)
	[ M00, M01, M02, M03,
	  M10, M11, M12, M13,
	  M20, M21, M22, M23,
	  M30, M31, M32, M33 ]	% 全成分のリスト
).

% addelem(S, E, S2): 集合Sに元Eを加えたものが、集合S2に等しいこと (ただし、主に S2 から E を取り除くために使う)
addelem(E, Set, [E|Set]).
addelem(E, [X|Set1], [X|Set2]) :- addelem(E, Set1, Set2).

% 多重集合の部分集合 '⊆'
multi_subset([], Rhs).
multi_subset([E|LhsTail], Rhs) :- addelem(E, Rhs1, Rhs), multi_subset(LhsTail, Rhs1).
multi_set_eq(L, R) :- multi_subset(L, R), multi_subset(R, L).	% 集合 '=' :⇔ '⊆' ∧ '⊇'

% 総和 Σ (sum(L, S): リストLの元の総和が数値Sumに等しい)
sum([Head|Tail], Sum) :- sum_acc(Tail, Sum, Head).
sum_acc([], Sum, Sum).
sum_acc([Head|Tail], Sum, SumAcc) :- SumAcc2 is SumAcc + Head, sum_acc(Tail, Sum, SumAcc2).

% 魔法陣
magic_matrix_4x4(M, A, Src) :-
	sum(Src, SumSrc), Sum is SumSrc / 4,
	M = A,
	M = [Row0, Row1, Row2, Row3],
	groups_4x4( M, [Clm0, Clm1, Clm2, Clm3], DiagL, DiagR, Flat ),
	magic_matrix_4x4_( [
		DiagL, DiagR,
		Row0, Row1, Row2, Row3,
		Clm0, Clm1, Clm2, Clm3 %,
	], Sum, Src ),
	multi_set_eq(Flat, Src).	% 成分列が Src の順列になること

magic_matrix_4x4_( [], _, _ ).
magic_matrix_4x4_( [Head|Tail], Sum, Src ) :-
	multi_subset(Head, Src),
	sum(Head, Sum),
	magic_matrix_4x4_(Tail, Sum, Src).

% 例題
?- magic_matrix_4x4( [
		[_, 18, _, _],
		[7, _, _, 10],
		[_, _, 9, _],
		[_, 5, _, _]
	], A, [2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19] ).

% A = [[6,18,17,2],[7,12,14,10],[11,8,9,15],[19,5,3,16]] (唯一解)

よく投稿されているコード

タグ

最近投稿されたコード