たとえば90分で数独解くプログラム作れる？

1 ：以下、＼(^o^)／でVIPがお送りします：2016/12/03(土) 21:29:03.346 ID:5/x8kPnUd.net

俺は無理

2 ：以下、＼(^o^)／でVIPがお送りします：2016/12/03(土) 21:29:18.905 ID:i299/iJn0.net

俺は有理

3 ：以下、＼(^o^)／でVIPがお送りします：2016/12/03(土) 21:29:41.635 ID:kfalo7//0.net

無理数

4 ：以下、＼(^o^)／でVIPがお送りします：2016/12/03(土) 21:30:02.218 ID:rFJ3P8Y20.net

俺は循環

5 ：以下、＼(^o^)／でVIPがお送りします：2016/12/03(土) 21:31:07.809 ID:o7sKq+k10.net

俺は定理

6 ：以下、＼(^o^)／でVIPがお送りします：2016/12/03(土) 21:31:11.189 ID:j6rImq3Y0.net

いけるんじゃ無い？
次の手を木構造にして、ダメだった枝は除外してくの。

7 ：以下、＼(^o^)／でVIPがお送りします：2016/12/03(土) 21:34:43.135 ID:Pg6j70li0.net

90分もいらない

8 ：以下、＼(^o^)／でVIPがお送りします：2016/12/03(土) 21:35:02.175 ID:oJ7Vy54n0.net

問題作るほうならできる

9 ：以下、＼(^o^)／でVIPがお送りします：2016/12/03(土) 21:35:11.816 ID:Z91bZxgy0.net

マス目が少ないならゴリ押し法で書けばええやん

10 ：以下、＼(^o^)／でVIPがお送りします：2016/12/03(土) 21:35:48.588 ID:E4RK9on/0.net

>>8これ

11 ：以下、＼(^o^)／でVIPがお送りします：2016/12/03(土) 21:36:02.038 ID:PfQPagsS0.net

簡単でしょ

解き始める前のタイム測って
問題を解く関数に入れて
（解く関数自体の実時間は１秒もかからないと思う）
あまった時間は空でループして
９０分後に解けた！と表示して終わり

12 ：以下、＼(^o^)／でVIPがお送りします：2016/12/03(土) 21:37:30.785 ID:j6rImq3Y0.net

・全体の縦横に同じ数字が無い
・3x3枠に同じ数字がない

これが枝が生き残る条件。
これを満たさなくなった枝から切っていく。

13 ：以下、＼(^o^)／でVIPがお送りします：2016/12/03(土) 21:38:54.715 ID:UZksCzFY0.net

「90分で」は「解く」にかかるのか「プログラム作る」にかかるのか

14 ：以下、＼(^o^)／でVIPがお送りします：2016/12/03(土) 21:39:45.645 ID:Jeff+a7gd.net

>>11
おもしろくないよ

15 ：以下、＼(^o^)／でVIPがお送りします：2016/12/03(土) 21:41:47.570 ID:j6rImq3Y0.net

だから要点は、
・配列の管理
・木構造の走査（再帰関数で表現するのが良さそう）

16 ：以下、＼(^o^)／でVIPがお送りします：2016/12/03(土) 21:42:46.396 ID:xrFbOo8q0.net

出来るだろ

17 ：以下、＼(^o^)／でVIPがお送りします：2016/12/03(土) 21:45:44.606 ID:E4RK9on/0.net

なんかネットにソースあってそれ使えば数分で出来ちゃいそうな予感

18 ：以下、＼(^o^)／でVIPがお送りします：2016/12/03(土) 21:53:25.022 ID:PTJ1+HhB0.net

余裕でいける

問題作るプログラムも解くプログラムも

90分もあるなら
ヘタしたらそれをiOSアプリにするくらいまでいける

19 ：以下、＼(^o^)／でVIPがお送りします：2016/12/03(土) 21:55:11.022 ID:Ubce4pIu0.net

俺は多分7時間ぐらいかかる

20 ：以下、＼(^o^)／でVIPがお送りします：2016/12/03(土) 21:59:13.293 ID:j6rImq3Y0.net

csvで問題作ったので解いてみてちょ
,,3,,2,,,,
8,,,,,4,7,,
9,7,5,,,,2,,
3,5,,2,1,,6,8,9
7,9,1,3,8,,,,2
,,6,,4,,1,,
5,,8,,,2,4,9,6
4,,9,6,3,5,,7,1
1,6,7,4,,8,3,,5

21 ：以下、＼(^o^)／でVIPがお送りします：2016/12/03(土) 22:00:48.326 ID:Fbky+KC00.net

じゃあ試しにこれ解いてみろよ
sssp://o.8ch.net/jssn.png

22 ：以下、＼(^o^)／でVIPがお送りします：2016/12/03(土) 22:07:19.637 ID:j6rImq3Y0.net

>>18
俺も作ってるけど、そっちのが早そうなので頼んだぞ

23 ：以下、＼(^o^)／でVIPがお送りします：2016/12/03(土) 22:31:28.705 ID:j6rImq3Y0.net

返事が無いから心配になってきた、作ってる？

24 ：以下、＼(^o^)／でVIPがお送りします：2016/12/03(土) 22:33:26.443 ID:j6rImq3Y0.net

pythonの途中経過な

import numpy as np
import csv
import sys

sudoku_path = "sudoku.csv”

def read_csv(path):
with open(path, "r") as f:
reader = csv.reader(f)
return [row for row in reader]

def scan_hor(sudoku_np, pos, val):
i, j = pos[0], pos[1]

def scan_ver(sudoku_np, pos, val):
i, j = pos[0], pos[1]

def scan_local(sudoku_np, pos, val):
i, j = pos[0], pos[1]

def scan(sudoku_np, pos, val):
is_hor = scan_hor(sudoku_np, pos, val)
is_ver = scan_ver(sudoku_np, pos, val)
is_local = scan_local(sudoku_np, pos, val)
return is_hor and is_ver and is_local

def ketaage(pos):
i, j = pos[0], pos[1]
i += 1
if(i>8):
i = 0
j += 1
if(j>8):
return None
return (i, j)

def scan_re(sudoku_np, pos):
npos = ketaage(pos)
if(npos is None):
print(sudoku_np)
sys.exit()

if(sudoku_np[pos[0], pos[1]] is None):
for val in range(1, 9) if scan(sudoku_np, pos, val):
sudoku_np[pos[0], pos[1]] = val
scan_re(sudoku_np, npos)
else:
scan_re(sudoku_np, npos)

sudoku_list = read_csv(sudoku_path)
sudoku_np = np.asarray(sudoku_list)
scan_re(sudoku_np, (0, 0))

25 ：以下、＼(^o^)／でVIPがお送りします：2016/12/03(土) 22:35:40.031 ID:j6rImq3Y0.net

インデントが死ぬので2chはpythonに向いてない

26 ：以下、＼(^o^)／でVIPがお送りします：2016/12/03(土) 22:36:20.328 ID:lIEDR9ld0.net

ソース拾ってくればいいだけ

27 ：以下、＼(^o^)／でVIPがお送りします：2016/12/03(土) 23:25:49.976 ID:j6rImq3Y0.net

問題間違えたかな、解けん
[['' '' '3' '' '2' '' '' '' '']
['8' '' '' '' '' '4' '7' '' '']
['9' '7' '5' '' '' '' '2' '' '']
['3' '5' '' '2' '1' '' '6' '8' '9']
['7' '9' '1' '3' '8' '' '' '' '2']
['' '' '6' '' '4' '' '1' '' '']
['5' '' '8' '' '' '2' '4' '9' '6']
['4' '' '9' '6' '3' '5' '' '7' '1']
['1' '6' '7' '4' '' '8' '3' '' '5']]

↓

[['6' '4' '3' '' '2' '' '' '' '']
['8' '2' '' '' '' '4' '7' '' '']
['9' '7' '5' '' '' '' '2' '' '']
['3' '5' '' '2' '1' '' '6' '8' '9']
['7' '9' '1' '3' '8' '' '' '' '2']
['2' '8' '6' '' '4' '' '1' '' '']
['5' '3' '8' '' '' '2' '4' '9' '6']
['4' '' '9' '6' '3' '5' '' '7' '1']
['1' '6' '7' '4' '' '8' '3' '' '5']]

28 ：以下、＼(^o^)／でVIPがお送りします：2016/12/03(土) 23:31:35.145 ID:j6rImq3Y0.net

時間が過ぎてしまった。俺には90分で解くのは無理だったらしい。

数独ってのは
・縦横に同じ数字が無い
・3x3に同じ数字が無い
が条件なんだよな？

29 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 00:03:08.591 ID:Sk9zl0Dr0.net

誰もいないだろうが、悔しいのでバグの原因を解明中

30 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 00:06:38.174 ID:Sk9zl0Dr0.net

アホやったわ。range(1,10)がrange(1,9)になってた。

31 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 00:10:03.153 ID:Sk9zl0Dr0.net

2時間かかったができたよ
[['' '' '3' '' '2' '' '' '' '']
['8' '' '' '' '' '4' '7' '' '']
['9' '7' '5' '' '' '' '2' '' '']
['3' '5' '' '2' '1' '' '6' '8' '9']
['7' '9' '1' '3' '8' '' '' '' '2']
['' '' '6' '' '4' '' '1' '' '']
['5' '' '8' '' '' '2' '4' '9' '6']
['4' '' '9' '6' '3' '5' '' '7' '1']
['1' '6' '7' '4' '' '8' '3' '' '5']]

↓

[['6' '4' '3' '7' '2' '1' '9' '5' '8']
['8' '1' '2' '9' '5' '4' '7' '6' '3']
['9' '7' '5' '8' '6' '3' '2' '1' '4']
['3' '5' '4' '2' '1' '7' '6' '8' '9']
['7' '9' '1' '3' '8' '6' '5' '4' '2']
['2' '8' '6' '5' '4' '9' '1' '3' '7']
['5' '3' '8' '1' '7' '2' '4' '9' '6']
['4' '2' '9' '6' '3' '5' '8' '7' '1']
['1' '6' '7' '4' '9' '8' '3' '2' '5']]

アホなミスをしなけりゃ、
微妙なプログラマでも90分で余裕にソースをかけるってこった。

32 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 00:11:54.238 ID:EoCPJhaU0.net

乙

33 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 00:16:30.033 ID:Sk9zl0Dr0.net

>>32
おお、誰か居たか、誰も何も言ってくれなかったらどうしようかと思ったよ。ありがとう。
ソース全文を共有するよ。ひどいソースだがなにか指摘があったら頼む。
forが内包表記じゃないとかは理解してるのでスルーしてくれ。

http://climbi.com/b/8623/0

34 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 00:29:52.184 ID:Sk9zl0Dr0.net

誰か一緒にやって欲しかったな、
早いやつは実際どれくらいの早さで書き上げるのか知りたかったのに。

35 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 00:30:47.437 ID:xR6ODjNh0.net

今からやるという主旨のスレだとは思わなかったので

36 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 00:33:27.386 ID:Sk9zl0Dr0.net

>>35
そんな趣旨のスレじゃなかったからなw
実際やってみたほうが面白いと思って勝手にやっただけだ。気にしないでくれ。

37 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 00:37:50.272 ID:eb3i2/nX0.net

import sudokulib.h
main(){
Game game=new Game();
Result kekka=game.Start();
print(kekka);
}
出来たぞ

38 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 00:38:56.112 ID:Sk9zl0Dr0.net

>>37
なるほど（なるほど）

39 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 00:39:33.901 ID:+tB9G2uma.net

PHP読んだことないからよくわからんけど左上から解析してるんだよな？
その時点で解なしだった場合値入らなくね？

40 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 00:42:39.545 ID:dEZSuwAL0.net

プログラムを書く方の時間が90分でプログラムを動かす方の制限時間がないなら普通に総当りすればよくね
10分あれば書けるだろ

41 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 00:44:53.754 ID:Sk9zl0Dr0.net

>>39
Pythonだぞ
ちょっとよくわからん。解ナシだったらそもそも解けんのでは？

たぶん再帰関数で走査してるのが伝わってないんだと思う。
順に木構造を作っていくイメージで考えてくれ。

42 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 00:44:58.595 ID:mzwFMjMf0.net

板間違えたかと思ったぞ

43 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 00:46:58.991 ID:Al1X94uE0.net

VBで作ったな

44 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 00:48:13.922 ID:+tB9G2uma.net

ソース化はしてないけど
1. 横に走査して入りうる候補をlist
2. 縦に走査
3. 内部に走査
4. 1〜3までで被ってる値を抽出してlist
5. 4の結果が1個ならぶちこむ、そうじゃなかったら候補listだけ残しとく
6. 全マスにたいして1〜5実行
7. 埋まってないとこ（候補listが残ってるとこ）の候補で縦横内部走査して1個に絞る
8. 7を全マスが埋まるまで繰り返す

こんな感じでどうだろ

45 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 00:49:36.428 ID:Sk9zl0Dr0.net

>>40
10分はすごいと思うが、脳みその回転次第では書けるのかもな。

46 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 00:50:55.238 ID:+tB9G2uma.net

>>41
左上が空でその瞬間に値が未定（複数候補がある）の場合67行目のifが最小値しかならなくない？

47 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 00:52:01.156 ID:eb3i2/nX0.net

数独はラインラインとかトリプルアタックとかクロスファイアとか様々なテクニックがあるから
プログラミングにするのはなかなか大変だと思う

48 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 00:52:21.869 ID:+tB9G2uma.net

んああこれnp.copyてもしかして別物つくってんのか？

49 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 00:54:03.408 ID:+tB9G2uma.net

分かった理解した、それぞれの値が入ったオブジェクト生成されてちゃんと再帰になってんのな
すまんこ

50 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 00:55:10.987 ID:Sk9zl0Dr0.net

>>46
左上に複数候補{1,2}があったとするなら、

まず1を代入して再帰的に走査を始める。
最後までたどり着けたなら左上は1で正解だ。

最後までたどり着けなかった場合は、
左上に2を代入するところまで自動的に戻ってくるんだ。

その仕組みは関数の再帰的な呼び出しによって実現されている。

51 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 00:56:45.485 ID:Sk9zl0Dr0.net

>>48-49
なるほど。もっと上手い方法があったのかな。
その方法も教えてくれると助かる。

52 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 00:58:53.168 ID:+tB9G2uma.net

copyのところ何故か実態に直接ぶち込んでんのかと勘違いしてたわ

53 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 00:59:22.407 ID:Sk9zl0Dr0.net

>>52
なるへそ

54 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 01:00:45.422 ID:+tB9G2uma.net

俺が思い付いたの>>44だけど決め打ちしなきゃいけないケース考えたらやっぱ再帰しかないんじゃねーのかなあと

55 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 01:07:13.752 ID:Qg8hzU5H0.net

美人揃いで話題沸騰だったダイハツコンパニオン
http://www.uiyuio.jkub.com/14.html

56 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 01:07:19.068 ID:Sk9zl0Dr0.net

>>54
確かに>>44の方が速そうだな。最後らへんの処理に自信がないけど。

57 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 01:09:16.947 ID:+tB9G2uma.net

アルゴリズムマスターきてくれーっ！

58 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 01:17:39.404 ID:Sk9zl0Dr0.net

>>57
>>44って人間が数独を解くアルゴリズムっぽいので、いけるんじゃない？（的どう）
数独をやったことが無い自分は、実際の状況が頭に浮かんでこないけど。

59 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 01:18:00.925 ID:Sk9zl0Dr0.net

的どう→適当

60 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 01:35:43.318 ID:o7P8EDHd0.net

90分で書ける（計算には1世紀かかる）

61 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 01:42:03.436 ID:dEZSuwAL0.net

何も数字が入ってない場合で9!^9=1.1*10^50通りくらい？

62 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 01:49:44.605 ID:o7P8EDHd0.net

>>61
毎秒 10^9 通り計算しても 10^41 秒
1世紀が約 3×10^9 秒だから全列挙は闇

63 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 01:53:10.656 ID:Sk9zl0Dr0.net

>>62
全列挙は闇かもしれんが、1つの答えを出すだけならpythonで1秒掛かってないゾ
[['' '' '' '' '' '' '' '' '']
['' '' '' '' '' '' '' '' '']
['' '' '' '' '' '' '' '' '']
['' '' '' '' '' '' '' '' '']
['' '' '' '' '' '' '' '' '']
['' '' '' '' '' '' '' '' '']
['' '' '' '' '' '' '' '' '']
['' '' '' '' '' '' '' '' '']
['' '' '' '' '' '' '' '' '']]

↓

[['1' '4' '7' '2' '3' '8' '5' '6' '9']
['2' '5' '8' '1' '6' '9' '3' '4' '7']
['3' '6' '9' '4' '5' '7' '1' '2' '8']
['4' '7' '1' '3' '8' '2' '6' '9' '5']
['5' '8' '2' '6' '9' '1' '4' '7' '3']
['6' '9' '3' '5' '7' '4' '2' '8' '1']
['7' '1' '4' '8' '2' '3' '9' '5' '6']
['8' '2' '5' '9' '1' '6' '7' '3' '4']
['9' '3' '6' '7' '4' '5' '8' '1' '2']]


右下の値が入ってなかったのを修正
http://climbi.com/b/8623/1

64 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 01:57:17.353 ID:o7P8EDHd0.net

Nクイーンのアルゴリズムと上手く融合できないかな

65 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 02:01:15.969 ID:PrL2sfMj0.net

この手の学生の課題とかコンテストの問題みたいなプログラムが実務の場で役に立った試しがない

66 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 02:03:51.389 ID:Sk9zl0Dr0.net

>>65
再帰関数の練習になる。配列の処理の練習になる。
再帰を実務で使う人は限られる？のかもしれんが、配列の練習としては良いのでは。

67 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 02:04:39.751 ID:xR6ODjNh0.net

馬鹿「歴史の勉強をしても役に立たない」
馬鹿「古文・漢文学んでも仕事に使えねーよ」
馬鹿「三角関数なんて意味ないし」

勉強したことを応用できない無能さを
よくも堂々と主張できるなｗｗｗｗ

恥ずかしくないのかｗｗｗｗ

68 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 02:08:36.974 ID:oBKW0VBG0.net

アルゴリズムができたので次はOpenCvを使って雑誌の数独をスキャンして自動的に解いてくれるプログラムを作りなさい
なお完成したプログラムはandroidアプリにして配布すること

69 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 02:13:49.032 ID:Sk9zl0Dr0.net

>>68
Javaとかいうめんどくささの塊言語はNG

70 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 02:21:42.948 ID:xb0Jz2mG0.net

個人的には数独の解析よりopencvでマス目と数字認識の方が遥かに楽だわ

71 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 02:23:20.936 ID:Sk9zl0Dr0.net

>>70
中の数字の認識はいくらでも分類器が転がってるからいいとして、マス目って何使えばいいの？パッと思いつかない。

72 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 02:23:21.318 ID:TbI1M0OW0.net

>>70
ただし字の汚い誰かが途中まで解いて放り投げたものでも認識できること

73 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 02:42:13.206 ID:RDr9JVMw0.net

で結局だれか書いたんか？

74 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 02:44:07.775 ID:Sk9zl0Dr0.net

>>73
書いたよ>>63、ケアレスミスでバグ起きて2時間かかったけど

75 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 02:53:52.891 ID:RDr9JVMw0.net

>>74 おけ

76 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 03:17:04.199 ID:Sk9zl0Dr0.net

すごく都合の良いページが転がっていた
http://docs.opencv.org/trunk/d7/d4d/tutorial_py_thresholding.html

77 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 03:18:21.327 ID:EbcNrU8R0.net

>>8
複数解なしは難しいと思う

78 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 03:19:30.829 ID:EbcNrU8R0.net

>>71
OpenCVに枠検出あるやろ、、たぶん

79 ：以下、＼(^o^)／でVIPがお送りします：2016/12/04(日) 04:38:01.849 ID:Sk9zl0Dr0.net

ホモグラフィー行列とかいう淫猥行列