DEFCON CTF 2013のゲリラプログラミングのスライドパズル同様、過去に自分で作って晒したコードをダウンロードして流用パターンです。
出題サーバにtelnetでアクセスするとこんな問題が表示されます。
'suDOKU(su-poison)' challenge for SECCON 2013. by KeigoYAMAZAKI, 2013.11.22- * Stage 1 1 2 3 4 5 6 7 8 9 $-+-+-$-+-+-$-+-+-$ A |8|.|.|.|.|.|.|.|.| B |.|.|3|6|.|.|.|.|.| C |.|7|.|.|9|.|X|.|.| $-+-+-$-+-+-$-+-+-$ D |.|5|.|.|.|7|.|.|.| E |.|.|.|.|4|5|7|.|.| F |.|.|.|1|.|.|.|3|.| $-+-+-$-+-+-$-+-+-$ G |.|.|1|.|.|.|.|6|8| H |.|.|8|5|.|.|.|1|.| I |.|9|.|.|.|.|4|.|.| $-+-+-$-+-+-$-+-+-$ if 'X' is 2, how many solutions does this sudoku have? => answer:
注：証拠のデータ残していなかったので、問題は別のやつ貼り付けてます。
数独の問題なんですが中にXってのがあって、Xが２の時解はいくつあるか？って聞いてきます。 １盤面あたり複数この質問が来て、クリアすると次の盤面っていう繰り返しです。
以前、自分で作ったPrologのコードはこんなカンジです。
https://github.com/minetosh/sudoku/tree/master/prolog
sudoku(Rows) :-
maplist(seigen, Rows), cols(Rows), blks(Rows),
maplist(fd_labeling, Rows).
cols([[]|L]).
cols(L) :-
maplist(nth(1), L, X), seigen(X), maplist(delete, L, X, NL), cols(NL).
blks([]).
blks([X, Y, Z|L]) :- blks2(X, Y, Z), blks(L).
blks2([],_,_).
blks2([X1, X2, X3|XL], [Y1, Y2, Y3|YL], [Z1, Z2, Z3|ZL]) :-
seigen([X1, X2, X3, Y1, Y2, Y3, Z1, Z2, Z3]), blks2(XL, YL, ZL).
seigen(X) :- fd_domain(X, 1, 9), fd_all_different(X).
gprolog --consult-file sudoku.pl で起動した後、問題入力はこうやります。
Row1 = [8, _, _, _, _, _, _, _, _], Row2 = [_, _, 3, 6, _, _, _, _, _], Row3 = [_, 7, _, _, 9, _, 2, _, _], Row4 = [_, 5, _, _, _, 7, _, _, _], Row5 = [_, _, _, _, 4, 5, 7, _, _], Row6 = [_, _, _, 1, _, _, _, 3, _], Row7 = [_, _, 1, _, _, _, _, 6, 8], Row8 = [_, _, 8, 5, _, _, _, 1, _], Row9 = [_, 9, _, _, _, _, 4, _, _], sudoku([Row1, Row2, Row3, Row4, Row5, Row6, Row7, Row8, Row9]).
解は次のように表示されます。
Row1 = [8,1,2,7,5,3,6,4,9] Row2 = [9,4,3,6,8,2,1,7,5] Row3 = [6,7,5,4,9,1,2,8,3] Row4 = [1,5,4,2,3,7,8,9,6] Row5 = [3,6,9,8,4,5,7,2,1] Row6 = [2,8,7,1,6,9,5,3,4] Row7 = [5,2,1,9,7,4,3,6,8] Row8 = [4,3,8,5,2,6,9,1,7] Row9 = [7,9,6,3,1,8,4,5,2] ?
検索してこのプログラムにたどり着いても複数解表示させる方法がわからなければ意味ないんですが、Prologで次の解を表示させるには、解を表示した後の?プロンプトに対して;(セミコロン)を入力します。解がある間これを繰り返します。
１問あたり制限時間は３分なので、この間に全解を手動で表示できる程度であれば、問題をこのプログラムの入力形式に変換してコピペ、セミコロンを入力し続けて解の数を数えればおｋとなります。
解の数が2桁程度までなら上記方法でも十分間に合いますが3桁以上になったらきついと思うので、その時はjavaでI/O制御するプログラム作るつもりでいました。
とりあえず問題変換＆コピペの手法を試すのに、以下のプログラムを作りました。
import java.io.*;
public class P200 {
public static void main(String args[]) {
try {
InputStreamReader isr = null;
try {
isr = new InputStreamReader(System.in, "UTF-8");
BufferedReader br = null;
try {
br = new BufferedReader(isr);
String line = null;
char c;
while (true) {
line = br.readLine();
if (line.charAt(0) != ' ') {
System.out.print("Row");
System.out.print(line.charAt(0) - 'A' + 1);
System.out.print("=[");
System.out.print(a(line.charAt(3))); System.out.print(",");
System.out.print(a(line.charAt(5))); System.out.print(",");
System.out.print(a(line.charAt(7))); System.out.print(",");
System.out.print(a(line.charAt(9))); System.out.print(",");
System.out.print(a(line.charAt(11))); System.out.print(",");
System.out.print(a(line.charAt(13))); System.out.print(",");
System.out.print(a(line.charAt(15))); System.out.print(",");
System.out.print(a(line.charAt(17))); System.out.print(",");
System.out.print(a(line.charAt(19))); System.out.println("],");
if (line.charAt(0) == 'I') {
System.out.println(
"sudoku([Row1, Row2, Row3, Row4, Row5, Row6, Row7, Row8, Row9])."
);
}
}
}
} finally {
if (br != null) br.close();
}
} finally {
if (isr != null) isr.close();
}
} catch (Exception ex) {
ex.printStackTrace();
}
}
public static char a(char c) {
if (c == '.')
return '_';
else
return c;
}
}
このプログラムで、
1 2 3 4 5 6 7 8 9 $-+-+-$-+-+-$-+-+-$ A |8|.|.|.|.|.|.|.|.| B |.|.|3|6|.|.|.|.|.| C |.|7|.|.|9|.|X|.|.| $-+-+-$-+-+-$-+-+-$ D |.|5|.|.|.|7|.|.|.| E |.|.|.|.|4|5|7|.|.| F |.|.|.|1|.|.|.|3|.| $-+-+-$-+-+-$-+-+-$ G |.|.|1|.|.|.|.|6|8| H |.|.|8|5|.|.|.|1|.| I |.|9|.|.|.|.|4|.|.| $-+-+-$-+-+-$-+-+-$
が、
Row1 = [8, _, _, _, _, _, _, _, _], Row2 = [_, _, 3, 6, _, _, _, _, _], Row3 = [_, 7, _, _, 9, _, X, _, _], Row4 = [_, 5, _, _, _, 7, _, _, _], Row5 = [_, _, _, _, 4, 5, 7, _, _], Row6 = [_, _, _, 1, _, _, _, 3, _], Row7 = [_, _, 1, _, _, _, _, 6, 8], Row8 = [_, _, 8, 5, _, _, _, 1, _], Row9 = [_, 9, _, _, _, _, 4, _, _], sudoku([Row1, Row2, Row3, Row4, Row5, Row6, Row7, Row8, Row9]).
になるので、X手前までPrologへコピペ、Xのところに示された数字入力、Xより後ろコピペ、セミコロン入力しながら数えて、の繰り返しでクリア出来ました。
結局私がやったときは解の数は0,1,2しかなく結構あっさり終わってしまいました。他の方のWriteupを見ると19っていうのもあったようです。
スコア画面に「あなたが一番最初にこの問題をときました」みたいに表示されていたので、多分そうゆうことなんだと思います。
0 件のコメント:
コメントを投稿